Multi-period combinatorial optimization on Qiskit Aqua

[andrea-simonetto]

Abstract

Currently, we have some initial implementations of how to solve combinatorial optimization problems in Qiskit, see for example: https://github.com/Qiskit/qiskit-iqx-tutorials/blob/master/qiskit/advanced/aqua/optimization/max_cut_and_tsp.ipynb

Here we consider the Travel Salesman Problem (TSP), a notoriously hard combinatorial problem.

The idea is to extend the TSP formulation above to a multi-period setting, where you are interested in finding best routes for several days at once (every day the weights of the graph change) . If the routes for each day are independent, then the problem can be trivially parallelized. However, a more interesting case is when the routes have couplings over multiple days (e.g., if you visit a city today, you can't visit it tomorrow, or there is a cost that forces you to keep a certain solution for more days, etc..).

Formulating the problem is not so complicated, but solving it on quantum is (because of variables scale with the number of days you are considering). The idea here is to use some decomposition approaches (e.g., Gauss-Seidel) to solve the multi-period TSP iteratively (and in a parallel fashion) maintaining the qbit requirements to the same as the single day one.

In a nutshell/ aim

Making the current quantum computers solve larger-scale optimization problems via decomposition approaches.

Members

-

-

• IBM Coach: @andrea-simonetto

Deliverable

A Jupyter notebook describing the proposed solution for one or multiple formulations of the multi-period TSP problem.

GitHub repo

tbd

[cicacica]

this sounds very interesting

[JansenZZ]

Very interesting!

[ghost]

I am interested!