Advanced AI-based techniques to solve complex combinatorial optimization problems at scale

A framework based on advanced AI techniques can solve complex, computationally intensive problems faster and more scalable than state-of-the-art methods, according to research led by engineers at the University of California, San Diego.

In a paper published in 2010, Nature Machine IntelligenceThe researchers presented HypOp, a framework that uses unsupervised learning and hypergraph neural networks to solve combinatorial optimization problems significantly faster than existing methods, and can also solve certain combinatorial problems that traditional methods cannot solve effectively.

“In this paper, we take on the difficult challenge of tackling one of the most important combinatorial optimization problems in many areas of science and engineering,” said Nasimeh Heydaribeni, corresponding author of the paper and a postdoctoral researcher in UC San Diego's Department of Electrical and Computer Engineering. She is part of the research group of Professor Farinaz Khushanfar, co-director of the Center for Machine Intelligence, Computing and Security at UC San Diego's Jacobs School of Engineering. Professor Tina Eliassi-Rad of Northeastern University also collaborated with the UC San Diego team on the project.

An example of a relatively simple combinatorial problem would be determining how many and what types of goods should be stored in a particular warehouse in order to minimize the amount of gasoline used to deliver the goods.

HypOps can be applied to a variety of challenging real-world problems, including drug discovery, chip design, logic verification, and logistics, all of which are combinatorial problems with a wide range of variables and constraints that are extremely difficult to solve because for these problems the size of the underlying search space for finding potential solutions grows exponentially, rather than linearly, with the size of the problem.

HypOp can solve these complex problems in a more scalable way by using novel distributed algorithms that allow multiple computational units on a hypergraph to solve the problem in parallel more efficiently.

HypOp introduces a new problem embedding that leverages hypergraph neural networks with higher-order connections than traditional graph neural networks to better model the problem constraints and solve them more efficiently. It also allows for the transfer of learning from one problem to more effectively solve other seemingly different problems. HypOp includes an additional fine-tuning step, which allows it to find more accurate solutions than existing traditional methods.

The code for HypOp is available here.

Below, the University of California, San Diego research team behind the paper expands on their findings for a wider audience through a short Q&A session.

The press release also states that HypOp can transfer learn from one type of problem objective to help solve other cost functions more effectively: For those of you who aren't tech-savvy, is there anything more to say about this phenomenon in relation to the broader discussion of how AI is empowering researchers to solve problems and make discoveries that wouldn't have been possible otherwise?

HypOp's ability to transfer learn from one problem to help solve other problems is a great example of how AI is bringing about a paradigm shift in research and discovery. This capability, called transfer learning, allows AI systems to entrust the knowledge gained from solving one problem to new, related problems with different cost functions, making them more versatile and efficient.

For non-technical experts, consider how human expertise works. For example, learning piano gives you a comprehensive musical foundation that allows you to learn guitar faster and more effectively. Transferable skills include knowledge of music theory, reading comprehension, understanding of rhythm, finger dexterity, and hearing. These skills collectively improve the learning experience, leading to faster and better learning of guitar for someone who already knows how to play piano. In comparison, a novice music learner has a much longer learning curve.

The synergy between human intelligence and AI will increase researchers' abilities to address complex, interdisciplinary challenges and drive progress in ways never before imagined – which is one of the reasons we're so excited about HypOp's advancements and contributions.

There's a lot of discussion in many circles about using machine learning and artificial intelligence to help researchers discover things faster or make discoveries that wouldn't be possible otherwise. For people who don't understand all the technical details of your new paper, how impactful do you think this new approach, HypOp, will be in terms of how AI can be used in problem solving and research?

The overall concept is that by learning the right problem structure, we can significantly improve the quality and speed of combinatorial optimization problems. HypOp's specific methodology has the potential to have a profound impact on how AI is applied in problem solving and research. By leveraging Hypergraph Neural Networks (HyperGNNs), HypOp extends the capabilities of traditional graph neural networks to scalably address higher-order constrained combinatorial optimization problems. This advance is crucial because many real-world problems involve complex constraints and interactions that go beyond the simple pairwise relationships suggested thus far.

The code for HypOp is available online. Do you think we'll see the code being used to solve combinatorial optimization problems anytime soon? Or is more work needed before the code can be used?

Yes, you can use HypOp open source code immediately to solve large scale combinatorial optimization problems.

What problems can HypOp solve that can't be solved in other ways?

HypOp can solve large-scale optimization problems with general objective functions and constraints. Most existing solvers can only solve problems with specific objective functions, such as linear or quadratic functions, and can only model pairwise constraints. Moreover, HypOp leverages distributed training techniques, making it scalable to practical problem instances.

What are the next steps in your research for HypOp?

We are focused on extending the generalization and scalability of HypOps by designing other advanced AI techniques that can learn from working on small problem instances and generalize to larger problem cases.