Project details

Combinatorial optimization using Ising model

Published by: Multinational Electronic Company

Status: CLOSED


Application domain: Information Technology

Budget (EUR): UP TO 15000

Project description

Recently, an approach using the Ising model has attracted attention. In such approach, a problem to solve is converted into another combinatorial optimization problem called ground-state search of the Ising model.
Methods which convert many practical problems into Ising model must be established.
Although such methods are known for some problems, further improvement is needed. One of the major technical issues is that the ground-state search of the converted Ising model is hard to solve accurately.
For example, a conversion method for a Traveling Salesman Problem (TSP) is already known. The method uses N^2 spins to express N-city problem. The ground-state of converted Ising model corresponds to an optimal solution of original problem. However, it is very difficult to find the ground-state or even sufficiently low energy state by algorithms based on local search because there are deep valley in the energy landscape of the Ising model. As a consequence, accurate solution of the original problem cannot be achieved.
In this project, we seek for the solution to overcome such issue.

Project goal

We call for the method to solve TSPs within a certain time limit using the ground-state search of the Ising model.
In this project, the ground-state search have to be performed by a "simulated annealing" algorithm.
Primary goal: algorithm design to convert the problem into the Ising model
Secondary goal: new techniques such as improving cooling schedule of a "simulated annealing" are welcome.