Mixed-Integer Quadratic Optimization: Algorithms and Complexity
Abstract
The goal of the proposed research is to advance the design and the analysis of algorithms for Mixed-Integer Quadratic Programming (MIQP). The relevance of MIQP is twofold: on one hand, many important applications can be modeled as MIQPs, and on the other hand, MIQP is a prototypical Mixed-Integer Nonlinear Programming (MINLP) problem, as it captures the critical elements of those models, but in the simplest possible way. In particular, MIQP subsumes Mixed-Integer Linear Programming (MILP). Over the past 60 years, the field of MILP has achieved great success from a theoretical, computational, and applied point of view. Such a level of maturity has not been reached when one considers MIQP. The objective of the proposed research is to close this gap on a theoretical level. Specifically, the goals are: (i) Design exact and approximation algorithms thatrun in polynomial time for important classes of MIQP problems; (ii) Design cutting plane algorithms for wide classes of MIQP problems; (iii) Employ our novel techniques to advance algorithm design across different fields. The success of this project will shed light on the fundamental limits of computation in MIQP, and will expose large classes of MIQP problems that can be solved efficiently within those limits. The novel techniques proposed will significantly enhance the mathematical toolkit used by researchers for the design and analysis of algorithms for MIQP problems. Moreover, this work ll lay the foundations for the design of solution methods for the more general class of MINL problems. The success of this project could also lead to resolving some fundamental open questions regarding computational complexity such as: (1) Does there exist a fully polynomial-time approximations scheme for MIQP, provided that the number of integer variables and the number of egative eigenvalues of the objective function are fixed? (2) Does there exist a polynomial-time exact algorithm for MIQP in fixed dimension? The proposed algorithmic frameworks are specifically designed for discrete problems featuring quadratic functions, and the generality of this setting akes them applicable to a wide variety of problems in different fields. Examples of problems hat can be attacked with the proposed techniques include feature selection problems in machinelearning, combinatorial optimization problems involving quadratic functions, and breaking cryptographic protocols in cryptanalysis. seminal work in algorithms for MILP is the key component that led to the development of highly efficient and robust solvers for MILP that are used by thousands of organizations for solvinglarge scale optimization problems. In spite of their significant impact in a variety of fields, there exist a multitude of important applications that cannot be formulated as MILP problems. A large number of these applications, in areas such as operations research, engineering, computer science, physics, biology, finance, and economics, can be modeled as MIQPs. The proposed researchwill yield the first efficient algorithms with theoretical guarantees for a wide array of applications, and will serve as the basis for the design of the next-generation of direct approaches in specific application domains. Like in the MILP case, the novel algorithmic techniques proposed could have a significant impact in our ability to enhance state-of-the-art solvers that will eventually solve real-world MIQP problems. A variety of DOD and Navy-relevant problems in resource allocation can be formulated as or approximated by MIQP, including many arising in mission planning, command and control, and logistics. Due to our inability to solve MIQP problems efficiently, in most cases the key featuresof MIQP problems are relaxed in order to make the problem tractable. The successful resolution of the proposed research could lead to efficient algorithms that can solve a number of these problems that are currently out of reach.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 23, 2019
- Source ID
- N000141912322
Entities
People
- Alberto Del Pia
Organizations
- Office of Naval Research
- United States Navy
- University of Wisconsin System