Physics-inspired graphical neural networks for solving combinatorial optimization problems

Physics-inspired graphical neural networks for solving combinatorial optimization problems

Visualization of an example solution to the Maximum Cut G81 benchmark problem instance, from the Gset dataset. Credit: Schuetz, Brubaker & Katzgraber.

Combinatorial optimization problems are complex problems with a discrete but large set of possible solutions. Some of the best-known examples of these problems are the traveling salesman, bin-packing, and workshop scheduling problems.

Researchers at the Amazon Quantum Solutions Lab, part of the AWS Intelligent and Advanced Computer Technologies Labs, recently developed a new tool for solving combinatorial optimization problems, based on graphical neural networks (GNNs). The approach developed by Schuetz, Brubaker and Katzgraber, published in Intelligence of natural machinescould be used to optimize a variety of real-world problems.

“Our work was very much driven by customer needs,” Martin Schuetz, one of the researchers who conducted the study, told TechXplore. “In our day-to-day work at the Amazon Quantum Solutions Lab, we interact with many customers in various verticals on their journey to become quantum-ready, which means preparing for a future where this emerging technology will be commercially viable. Most customer use cases involve a combination of optimization issues.”

In the context of consumer services, combinatorial optimization problems can take many different forms. Two notable examples of these problems are portfolio optimization problems in finance and shop scheduling tasks in manufacturing. The term portfolio optimization refers to the process by which one selects the best portfolio or asset allocation for a specific situation from a set of available portfolios.

Job shop scheduling issues, on the other hand, occur in cases where a set of jobs or tasks need to be performed and there is a limited set of resources/tools to complete those tasks. In these cases, one might be asked to find an optimal schedule that uses the available tools to complete the tasks in as little time as possible.

As quantum technology is still in its early stages of development, researchers have tried to develop optimization tools that do not rely entirely on quantum computers, at least until such computers have become commercially viable. In their paper, Schuetz and his colleagues thus introduced a physics-inspired GNN-based optimization technique.

“Given their inherent scalability, physics-inspired GNNs can be used today to approximate (large-scale) combinatorial optimization problems with quantum-native models, while helping our customers become quantum-ready. using the mathematical representation that quantum devices understand,” says Brubaker.

The approach developed by Schuetz and his colleagues first identifies the Hamiltonian (i.e. the cost function) that encodes the specific optimization problems one is trying to solve. Then, it associates the corresponding decision variables with the nodes of a graph.

“Our key idea then is to frame combinatorial optimization problems as unsupervised node classification tasks in which the GNN learns the color (in other words, spin or variable) assignments for each node” , explained Schuetz. “To this end, the GNN is iteratively trained via a custom loss function that encodes the specific optimization problem of interest, in a one-to-one correspondence with the original Hamiltonian, thus providing a choice of principle for the GNN loss function.”

Once the GNN was trained, the team projected the final values ​​for the soft node assignments it produced to the hard class assignments. This ultimately allowed them to approximately solve large-scale combinatorial optimization problems.

The approach proposed by Schuetz and colleagues has several advantages over other methods for solving combinatorial optimization problems. Most notably, their method is highly scalable, meaning it could be used to computationally optimize complex problems with hundreds of millions of nodes.

“Our GNN optimizer is based on a direct and general mathematical relationship between the prototypical Ising spin Hamiltonians and the differentiable loss function with which we train the GNN, thus providing a unifying framework for a broad class of combinatorial optimization problems. and opening up the powerful physics toolbox to modern deep learning approaches,” said Brubaker. “By fusing concepts from physics with modern machine learning tools, we deliver a simple, generic, and robust solver that does not rely on homemade loss functions.”

Remarkably, the approach designed by Schuetz and colleagues can approximately solve optimization problems without the need for training labels, which are a key requirement for all supervised learning methods. As the technique has optimization problems like Ising Hamiltonians, it can also run natively on quantum hardware.

“We provide a unifying, interdisciplinary framework for optimization problems that integrates insights from physics and the tools of modern deep learning,” Schuetz explained. “With this framework, we have at our disposal a tool that is broadly applicable to canonical NP-hard problems; prominent examples include maximum cut, minimum vertex cover, maximum independent set problems, as well as Ising’s spin glasses.”

In the future, the new GNN-based method introduced by this team of researchers could be used to solve a variety of complex and real-world optimization problems. As it is inherently scalable, Amazon Quantum Solutions Lab and AWS plan to offer it to their customers as a tool that could ease their transition to quantum technologies. In fact, their technique could allow customers to address both problems related to specific use cases in a native quantum modeling framework, both at small scale and at an industry-relevant scale.

“In the future, we will continue to pursue conceptual, theoretical and more applied research questions. On the one hand, we have several ideas on how to improve and extend the capabilities of the proposed GNN optimizer, and on the other hand, there are many applied use cases that we can try to solve with this new tool. We will continue to use customer feedback to help guide and prioritize our research program,” said Katzgraber.

A new approach to solving optimization problems using Boltzmann machines

More information:
Martin JA Schuetz et al, Combinatorial optimization with physics-inspired graphical neural networks, Intelligence of natural machines (2022). DOI: 10.1038/s42256-022-00468-6

© 2022 Science X Network

Quote: Physics-Inspired Graph Neural Networks for Solving Combinatorial Optimization Problems (2022, May 25) Retrieved May 25, 2022 from -networks-combinatorial.html

This document is subject to copyright. Except for fair use for purposes of private study or research, no part may be reproduced without written permission. The content is provided for information only.

Leave a Reply