Mixed-Integer Quadratic Optimization: Algorithms and Complexity

Mixed-integer quadratic programming (MIQP) is the simplest yet arguably the most important class of mixed-integer nonlinear programming (MINLP) that contains two major sources of difficulties: discrete decision variables and nonlinearity in the objective function. Not only many important applications can be naturally modeled as MIQPs, but a variety of more general MINLPs can be reformulated as or approximated by this class of problems. In particular, MIQP subsumes two widely studied classes of optimization problems: mixed-integer linear programming (MILP), and quadratic programming (QP). Research efforts over several decades have led to the design of efficient exact and approximation algorithms for some important classes of MILP and QP problems. Such a level of maturity has not been reached when one considers MIQP. For these problems, very few efficient algorithms are known. The primary objective of the proposed research is to close this gap by studying structural properties of MIQP problems, and by designing innovative exact and approximation algorithms for MIQP with desirable theoretical guarantees. The main goals of the proposed project are: (1) Identify which classes of MIQPs can be solved efficiently, and which not; (2) Design exact and approximation algorithms for important subclasses of MIQP; (3) Characterize the class of optimization problems that can be modeled as MIQP, possibly in a different space. By leveraging on the extensive MILP and QP literature, for the first time novel directions are proposed for extending a variety of powerful MILP and QP methods to the vastly different MIQP setting.