Introduction
Integer Linear Programming (ILP) is a staple of optimization, but moving to quadratic functions makes the problem significantly more explosive. While ILP is solvable in polynomial time for a fixed number of variables, Integer Quadratic Programming (IQP)—where the objective function can include terms like $x_1^2$ or $x_1x_2$—is NP-hard even in its simplest forms. This paper, presented at AAAI-19, provides a fine-grained map of the "islands of tractability" for IQP, identifying specific restrictions on coefficients, domains, and variable interaction structures that allow for efficient solutions.
Methods: Structural Representations
The authors use Parameterized Complexity to analyze IQP, looking at parameters $k$ such as the maximum coefficient or the "width" of the variable interaction graph. They introduce several key graph representations to capture these interactions:
- Primal Graph: Variables are connected if they appear together in a constraint.
- Mixed Primal Graph: Extends the primal graph by adding edges between variables that appear together in a quadratic term in the objective function.
- Incidence Graph: A bipartite graph connecting variables to the constraints they appear in.
The core algorithmic technique involves Dynamic Programming on Tree Decompositions. For instances with "thin" structures (low treewidth or treedepth), the authors develop algorithms that prune the problem down to a manageable size before applying specialized solvers.
Key Tractability Results
The paper establishes four main "Settings" where IQP becomes tractable. A crucial finding is that the objective function in IQP acts as a "constraint in disguise," meaning tractability requires restricting both the constraints and the objective function.
- Bounded Coefficients: If coefficients and the "arity" (number of variables in a term) of the objective are small, IQP is Fixed-Parameter Tractable (FPT) when parameterized by the treedepth of the primal graph.
- Bounded Domain: If the range of values variables can take is small, IQP is FPT when parameterized by the treewidth of the mixed primal graph.
- Hybrid Restrictions: A "best of both worlds" setting where some variables have bounded domains and others have bounded coefficients. This is also FPT using a specialized hybrid graph.
- Unary IQP: If the entire instance is encoded in unary, the problem is in XP (solvable in polynomial time for any fixed treewidth) when parameterized by the mixed incidence treewidth.
Insights and Future Work
The authors demonstrate that Mixed Graphs are essential; quadratic terms cannot be ignored when building interaction graphs. Furthermore, they found that for problems with bounded coefficients, standard treewidth is insufficient; the stricter treedepth parameter is required to maintain efficiency.
While these results provide a theoretical foundation, the algorithms are primarily classification results with high constant factors. Future work will investigate whether the "arity" restriction in the bounded coefficient setting can be lifted and if IQP can ever be as "easy" as ILP under the same structural restrictions.
Summary updated