Event Details

Mathematical techniques for solving mixed integer programs using a quantum computer

Mixed integer programming (MIP) is a field where the application of quantum computers is expected to bring significant performance improvements. In order to solve a MIP on a quantum computer, it is necessary to perform mathematical transformations to reformulate the problem into a quadratic unconstrained binary optimisation (QUBO) problem. While such transformations are effective for integer programs with equality constraints, the existence of inequalities and continuous variables in MIPs can result in extremely large QUBO formulations. Various types of decomposition can be performed to separate the "mixed" part of the problem from the "integer" part---the latter which can be solved as a QUBO and, thus, on a quantum computer.

This talk will provide an introduction to the transformations from MIP to QUBO and describe the application of Lagrangian relaxation, Dantzig-Wolfe reformulation and Benders' decomposition. We will show that the use of decomposition techniques provides many opportunities for solving MIPs in classical/quantum hybrid computing environments.