Unsplittable Multi-Commodity Flow Problem via Quantum Computing
Miguel Pineda Martín, Sébastien Martin · 2023
Quantum computing is a promising area to tackle optimization problems. Several algorithms are derived from this paradigm. One interesting method is called Quantum Approximate Optimization Algorithm (QAOA) where the goal is to solve a Quadratic Unconstrained Binary Optimization. This method is heuristic in practice but can converge on an optimal solution with enough time and a computer with enough resources. In this paper, we focus on the unsplittable multi-commodity flow problem and we propose a dedicated algorithm using QAOA as a sub-routine. Thanks to well-known methods, cutting plane, column generation, and Lagrangian relaxation, we propose a framework to solve this problem based on QAOA.