• About Us
  • Contact Us
  • Cookie policy (EU)
  • Home
  • Privacy Policy
  • Video
  • Write for us
Today Headline
  • HOME
  • NEWS
    • POLITICS
    • News for today
    • Borisov news
  • FINANCE
    • Business
    • Insurance
  • Video
  • TECHNOLOGY
  • ENTERPRISE
  • LIFESTYLE
    • TRAVEL
    • HEALTH
    • ENTERTAINMENT
  • AUTOMOTIVE
  • SPORTS
  • Travel and Tourism
  • HOME
  • NEWS
    • POLITICS
    • News for today
    • Borisov news
  • FINANCE
    • Business
    • Insurance
  • Video
  • TECHNOLOGY
  • ENTERPRISE
  • LIFESTYLE
    • TRAVEL
    • HEALTH
    • ENTERTAINMENT
  • AUTOMOTIVE
  • SPORTS
  • Travel and Tourism
No Result
View All Result
TodayHeadline
No Result
View All Result

Physics-inspired graph neural networks to solve combinatorial optimization problems

June 24, 2022
in Technology
0
0
SHARES
4
VIEWS
Share on FacebookShare on Twitter


Physics-inspired graph neural networks to solve combinatorial optimization problems

Visualization of sample solution to Maximum Cut benchmark problem instance G81, 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 most renowned examples of these problems are the traveling salesman, the bin-packing, and the job-shop scheduling problems.

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

“Our work was very much inspired by customer needs,” Martin Schuetz, one of the researchers who carried out the study, told TechXplore. “In our daily work at the Amazon Quantum Solutions Lab, we interact with many customers across various verticals on their journey to get quantum-ready, i.e., prepare for a future when this emerging technology will be commercially viable. Most customer use cases involve combinatorial optimization problems.”

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

Job-shop scheduling problems, on the other hand, occur in instances where a set of jobs or tasks must be performed and there is a limited set of resources/tools to perform these tasks. In these cases, one could be asked to find an optimal schedule that utilizes available tools to perform the tasks in as little time as possible.

As quantum technology is still in its early stages of development, researchers have been trying to develop optimization tools that do not fully rely on quantum computers, at least until these computers have become commercially viable. In their paper, Schuetz and his colleagues thus introduced an optimization technique based on GNNs inspired by physics.

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

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

“Our key idea is then to frame combinatorial optimization problems as unsupervised node classification tasks whereby the GNN learns color (in other words, spin or variable) assignments for every node,” Schuetz explained. “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 principled choice for the GNN’s loss function.”

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

The approach proposed by Schuetz and his colleagues has several advantages over other methods to tackle combinatorial optimization problems. Most notably, their method is highly scalable, which means that 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 relation between prototypical Ising spin Hamiltonians and the differentiable loss function with which we train the GNN, thereby providing one unifying framework for a broad class of combinatorial optimization problems and opening up the powerful toolbox of physics to modern deep-learning approaches,” Brubaker said. “Fusing concepts from physics with modern machine learning tooling, we propose a simple, generic and robust solver that does not rely on handcrafted loss functions.”

Remarkably, the approach devised by Schuetz and his 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 casts optimization problems as Ising Hamiltonians, it can also run natively on quantum hardware.

“We provide a unifying, interdisciplinary framework for optimization problems that incorporates insights from physics and tools from modern deep learning,” Schuetz explained. “With this framework we have a tool at our disposal 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 spin glasses.”

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

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


A new approach to tackle optimization problems using Boltzmann machines


More information:
Martin J. A. Schuetz et al, Combinatorial optimization with physics-inspired graph neural networks, Nature Machine Intelligence (2022). DOI: 10.1038/s42256-022-00468-6

© 2022 Science X Network

Citation:
Physics-inspired graph neural networks to solve combinatorial optimization problems (2022, May 25)
retrieved 23 June 2022
from https://techxplore.com/news/2022-05-physics-inspired-graph-neural-networks-combinatorial.html

This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no
part may be reproduced without the written permission. The content is provided for information purposes only.

Previous Post

Florida records 24 meningococcal disease cases and 6 deaths among gay and bisexual men

Next Post

“Patriotic” Jubilee Books For Schools Made Abroad Due To Lack Of UK Printers

Related Posts

An AI system trained to find an equitable policy for distributing public funds in an online game
Technology

An AI system trained to find an equitable policy for distributing public funds in an online game

Illustration of the game and...

Read more
Study finds toxicity in the open-source community varies from other internet forums
Technology

Study finds toxicity in the open-source community varies from other internet forums

Credit: Pixabay/CC0 Public Domain Trolls,...

Read more
A model that allows robots to follow and guide humans in crowded environments
Technology

A model that allows robots to follow and guide humans in crowded environments

The agent introduced by the...

Read more
Supernumerary virtual robotic arms can feel like part of the body
Technology

Supernumerary virtual robotic arms can feel like part of the body

In this diagram of the...

Read more
Researchers use GPUs to evaluate human brain connectivity
Technology

Researchers use GPUs to evaluate human brain connectivity

The image shows the superior...

Read more
Load More
Next Post

“Patriotic” Jubilee Books For Schools Made Abroad Due To Lack Of UK Printers

  • Trending
  • Comments
  • Latest
I’m a recent widow. I’m building a house on my son’s and daughter-in-law’s land. Do I have legal ownership? What if they decide to sell, divorce, or die before me?

I’m a recent widow. I’m building a house on my son’s and daughter-in-law’s land. Do I have legal ownership? What if they decide to sell, divorce, or die before me?

Flight Attendant Escorts Abandoned Senior Dog Cross-Country To His New Forever Family

Flight Attendant Escorts Abandoned Senior Dog Cross-Country To His New Forever Family

How old is Simon Cowell’s son Eric and who is his mother?

How old is Simon Cowell’s son Eric and who is his mother?

Six times actors really romped in sex scenes that make 365 DNI look tame

Six times actors really romped in sex scenes that make 365 DNI look tame

Kamala Harris visits scene of July 4 parade shooting

Kamala Harris visits scene of July 4 parade shooting

Prosecutor Calls for Assault Weapons Ban After Highland Park Shooting

Prosecutor Calls for Assault Weapons Ban After Highland Park Shooting

Could battery swapping replace EV charging?

Could battery swapping replace EV charging?

Etiquette expert William Hanson’s 10 do’s and don’ts for using festival toilets

Etiquette expert William Hanson’s 10 do’s and don’ts for using festival toilets

About Us

Todayheadline the independent news and topics discovery
A home-grown and independent news and topic aggregation . displays breaking news linking to news websites all around the world.

Follow Us

Latest News

Kamala Harris visits scene of July 4 parade shooting

Kamala Harris visits scene of July 4 parade shooting

Prosecutor Calls for Assault Weapons Ban After Highland Park Shooting

Prosecutor Calls for Assault Weapons Ban After Highland Park Shooting

Kamala Harris visits scene of July 4 parade shooting

Kamala Harris visits scene of July 4 parade shooting

Prosecutor Calls for Assault Weapons Ban After Highland Park Shooting

Prosecutor Calls for Assault Weapons Ban After Highland Park Shooting

Could battery swapping replace EV charging?

Could battery swapping replace EV charging?

  • Real Estate
  • Education
  • Parenting
  • Cooking
  • NFL Games On TV Today
  • Travel and Tourism
  • Home & Garden
  • Pets
  • Privacy & Policy
  • Contact
  • About

© 2021 All rights are reserved Todayheadline

No Result
View All Result
  • Real Estate
  • Education
  • Parenting
  • Cooking
  • NFL Games On TV Today
  • Travel and Tourism
  • Home & Garden
  • Pets
  • Privacy & Policy
  • Contact
  • About

© 2021 All rights are reserved Todayheadline

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In

Add New Playlist

Posting....