(61ac) Discrete Nonlinear Optimization: Modeling and Solutions Via Novel Hardware and Decomposition Algorithms

Optimization problems arise in different areas of Logistics, Manufacturing, and Process Systems Engineering (PSE), and Energy Systems Engineering, and solving these problems efficiently is essential for addressing important industrial applications.

Quantum computers have the potential to efficiently solve challenging nonlinear and combinatorial problems. However, available quantum computers cannot efficiently address practical problems; they are limited to small sizes and do not handle constraints well. In this talk and tutorial, we present the modeling strategy of problems as Mixed-Integer Nonlinear Programs (MINLP), explain some of the approaches that quantum computers use to solve Quadratic Unconstrained Binary Optimization (QUBO) problems, and propose hybrid classical-quantum algorithms to solve a class of MINLP, mixed-binary quadratically constrained programs (MIQCP) and apply decomposition strategies to break them down into QUBO subproblems that can be solved by quantum computers.

We will first consider a suite a software designed to automatically transform MINLP problems, usually used by the PSE and Operations Research (OR) communities to model optimization problems, into the QUBO formalism. The code is open-source and its performance surpasses currently available commercial tools. https://github.com/psrenergy/ToQUBO.jl

We will then go into one of the proposed decomposition approaches, whose implementation is also openly available and which in terms of performance surpasses well known MIP solvers in addressing archetypical problems such as the max-clique problem. Details of that work can be found https://arxiv.org/abs/2207.13630. This approach is based on a copositve optimization reformulation of the optimization problems, integrated within a cutting plane algorithm. The overall algorithm provides optimality convergence guarantees, yet it is robust to suboptimal solutions of the QUBO problems, which are usually provided by the hardware-based approaches (e.g., Quantum Annealing) to QUBO.

We will also cover different approaches to solving Quadratic Unconstrained Binary Optimization (QUBO) problems through unconventional computation methods, including but not limited to Quantum algorithms, and discuss how these approaches lead to algorithms able to outperform classical solution approaches. We complete this picture with analysis code provided to compare these methods and help in the challenging solver hyperparameter optimization task. https://github.com/usra-riacs/stochastic-benchmark