Source-linked AI summary
Mixed-integer Quadratic Programming is in NP
Alberto Del Pia, Santanu S. Dey, Marco Molinaro
TL;DR
The paper addresses whether decision mixed-integer quadratic programming has efficiently representable yes-certificates. It proves that every feasible instance has a polynomial-size feasible solution, establishing NP membership and, together with NP-hardness, NP-completeness for decision MIQP and IQP. The guarantee is specific to the one-quadratic-inequality setting and is tight when more quadratic inequalities are allowed.
Problem
It was necessary to establish whether feasible mixed-integer quadratic programs always have polynomial-size solutions, extending known NP-membership results for quadratic programming and integer linear programming.
Method
The paper proves a polynomial complexity bound for a feasible point of every non-empty MIQP feasible set and uses that point as a certificate for yes-instances.
Results
The decision versions of MIQP and IQP are NP-complete.
Takeaways & Limitations
The result unifies classical NP-membership results for quadratic programming and integer linear programming within the mixed-integer quadratic framework.
Takeaways & Limitations
The polynomial-size guarantee is tight with respect to the number of quadratic inequalities; more general systems can require exponentially large feasible solutions or be undecidable.
Abstract
from arXiv · showhide
Mixed-integer quadratic programming is the problem of optimizing a quadratic function over points in a polyhedral set where some of the components are restricted to be integral. In this paper, we prove that the decision version of mixed-integer quadratic programming is in NP, thereby showing that it is NP-complete. This is established by showing that if the decision version of mixed-integer quadratic programming is feasible, then there exists a solution of polynomial size. This result generalizes and unifies classical results that quadratic programming is in NP and integer linear programming is in NP.
1 Introduction
The paper establishes that feasible mixed-integer quadratic programs have polynomial-size solutions, placing their decision versions, including integer quadratic programming, in NP and hence making them NP-complete. The result is tight with respect to allowing additional quadratic inequalities.
- 1 Introduction: MIQP optimizes a quadratic function over a polyhedral set with both integer and continuous components.Its decision form asks whether a feasible point satisfies the quadratic and polyhedral constraints.
- 1.1 Statement of result and discussion: Theorem 1 states that every non-empty MIQP feasible set contains a point whose encoding complexity is polynomially bounded by the instance complexity.The bound applies to the data H, c, d, A, and b through a polynomial function f(φ).
- 1.1 Statement of result and discussion: The decision versions of IQP and MIQP are NP-complete, generalizing results that quadratic programming and integer linear programming are in NP.IQP is the special case in which all variables are required to be integer.
- 1.1 Statement of result and discussion: A polynomial-length feasible point serves as a certificate for yes-instances, proving that decision MIQP and decision IQP lie in NP.The integer-only special case is IQP, and graph cut provides the NP-hardness connection used for IQP.
- 1.1 Statement of result and discussion: The polynomial-size feasible-solution guarantee is tight in the number of quadratic inequalities: with more general systems, feasible integral solutions can require exponential encoding length or become undecidable.The paper contrasts its one-quadratic-inequality result with negative results for systems containing many quadratic inequalities.
2 Preliminaries
The preliminaries establish notation and connect mixed-integer linear programming decompositions to polynomial-size certificates. This framework supports the result that decision MIP is in NP and is instrumental in the main proof.
- Quadratic programming is the MIQP special case with all variables continuous, while the continuous relaxation of the formulation is in NP.
- A simple pointed polyhedral cone has as many extreme rays as the dimension of the cone.
- A rational pointed polyhedron can be decomposed into finitely many polytopes and families of extreme rays whose generated cones are simple.
- The proof verifies the decomposition by expressing points through convex combinations and integer-cone components, then separating fractional and integer multipliers.
- The decomposition partitions mixed-integer linear sets into overlapping pieces that are affinely isomorphic to integer lattices.
- Vertices of the resulting polytopes can serve as certificates, proving that the decision version of MIP is in NP.
3 Proof of Theorem 1
The proof constructs a feasible mixed-integer solution of polynomial encoding size by decomposing the recession structure and analyzing quadratic behavior along its directions. It treats negative and non-negative recession optima separately, using boundedness and recursive cone refinement to obtain small-complexity witnesses.
- Reduction and cone normalization: A normalizing hyperplane and recursive decomposition refine each pointed recession cone into finitely many simple cones with small complexity.The construction proceeds by induction on cone dimension, preserving the required face properties and complexity bounds.
- Reduction and cone normalization: The proof reduces to pointed polyhedra by partitioning the feasible region with additional constraints of O(n) complexity.This preserves polynomially bounded instance complexity while allowing pointed-cone arguments.
- Negative recession optimum: When the recession quadratic optimum is negative, scaling a small-complexity recession direction eventually makes the quadratic value negative while preserving mixed-integer feasibility.The resulting point has F-small complexity after choosing an integer scaling beyond the larger root of the resulting concave polynomial.
- Non-negative recession optimum: When the recession optimum is non-negative, the decomposition and cone refinement reduce feasibility to behavior along individual directions in a simple cone.Directions with negative linear behavior yield a small-complexity feasible point after scaling.
- Non-negative recession optimum: If no direction has negative linear behavior, a small-complexity norm bound makes the relevant optimization problem attain a global optimum.The bound is independent of the selected point, and Theorem 3 then supplies an optimal solution of F-small complexity satisfying the quadratic constraint.