David Bernal: Discrete nonlinear optimization: Modeling and solutions via novel hardware and decomposition algorithms

Date: 2023-07-05

Time: 11:00 - 12:00

Zoom link: https://kva-se.zoom.us/j/9217561880


David Bernal, Purdue University


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. 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.