Discrete Nonlinear Optimization: Modeling and Solutions via Novel Hardware and Decomposition Algorithms
Category
Published on
Abstract
Optimization problems arise in different areas of Logistics, Manufacturing, 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 (arXiv:2207.13630).
We will also cover different approaches to formulating and 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.
Bio
David E. Bernal Neira is an Assistant Professor at the Davidson School of Chemical Engineering and a visiting Scientists in quantum computing at the Quantum Artificial Intelligence Laboratory at NASA and the Research Institute of Advanced Computer Science (RIACS) of the Universities Space Research Association (USRA). He works in theory, algorithms, and software for nonlinear discrete optimization and its applications to Process Systems Engineering. He also complemented such algorithm development by studying the usage of quantum algorithms got nonlinear combinatorial optimization. He developed and co-taught the course on Quantum Integer Programming and Machine Learning, which has already been taught for four years at Carnegie Mellon University (where he is the Adjunct Professor in Operations Management and Quantum Computing at the Tepper School of Business) and replicated in several institutes worldwide.
David currently works on developing and benchmarking quantum and Physics-inspired methods for optimization and chemistry.
Sponsored by
Cite this work
Researchers should cite this work as follows:
Time
Location
Physics 242, Purdue University, West Lafayette, IN