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 May 30 in Nature Machine Intelligence, the researchers present HypOp, a framework that uses unsupervised learning and hypergraph neural networks to solve combinatorial optimization problems significantly faster than existing methods. HypOp 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. HypOp can also transfer what it learns from one problem to more effectively solve other, seemingly different problems. HypOp includes an additional fine-tuning step that allows it to find more accurate solutions than existing traditional methods.
This research was funded in part by the MURI AutoCombat project funded by the Department of Defense and the Army Research Office, and the NSF-funded TILOS AI Laboratory.
Distributed constrained combinatorial optimization using hypergraph neural networks
Nasimeh Heydaribeni, Xinrui Zhan, Ruisi Zhang, Farinaz Koushanfar, Department of Electrical and Computer Engineering, University of California, San Diego
Tina Eliassi-Rad, Northeastern University's Corey School of Computer Science
The code for HypOp is available here.
/Public Release. This material from the originating organization/author may be out of date and has been edited for clarity, style and length. Mirage.News does not take any organizational stance or position and all views, positions and conclusions expressed here are solely those of the authors. Read the full article here.
