CS Paper Radar

Two-Stage Mixed-Integer Quadratic Programming in Polynomial Time

Alberto Del Pia

cs.CC math.OCcs.DS ·submitted 2026-11-10 23:39 UTC · v1

Abstract

Lenstra showed that mixed-integer linear programming can be solved in polynomial time when the number of integer variables is fixed and the number of continuous variables is arbitrary. Mixed-integer quadratic programming (MIQP) can be solved in polynomial time when the total number of variables is fixed. However, since MIQP is NP-hard already without integer variables, the analog of Lenstra's result fails unless P = NP. Hence, polynomial-time algorithms for MIQP with an arbitrary number of continuous variables must exploit additional structure. We study MIQPs with two-stage structure, which underlies Benders decomposition and two-stage stochastic programming. A few linking variables, including all integer variables, are coupled with many blocks of continuous variables that interact only through them, both in the constraints and in the objective. We give a polynomial-time algorithm for MIQP with an arbitrary quadratic objective when the number of linking variables and the block size are fixed, while the number of blocks, and hence the number of variables, is arbitrary. The case with no blocks is MIQP in fixed dimension. None of our assumptions can be dropped. Unless P = NP, the number of linking variables and the block size must both be fixed, the blocks cannot interact or contain integer variables, and large blocks cannot be allowed even if their objective is linear. Unless FPT = W[1], the exponent of the running time must depend on both the number of linking variables and the block size.

Closest papers

Nearest neighbours by meaning across the whole index.

Extending Tardos's Theorem to Separable Convex Quadratic Programming

cs.DS ·2026-10-05 ·Bin Cui, Hanqing Li, Xupeng Miao
theory similarity 0.61
Abstract · 13 pages, no figures. Substantially revised with a simplified algorithm and proofs. Title and author list updated

For an integer equality matrix $A\in\mathbb{Z}^{r\times m}$ of binary encoding length $\langle A\rangle$, Tardos's theorem solves linear programs using $\operatorname{poly}(r,m,\langle A\rangle)$ rational arithmetic operations and comparisons, independently of the right-hand side and objective coefficients. We extend this guarantee to continuous separable convex quadratic programming over $Ax=b$, $x\ge0$: the operation count is independent of the right-hand side, linear costs, and all nonnegative quadratic weights. The algorithm returns an exact optimal primal-dual pair or a certificate of infeasibility or unboundedness. All intermediate rational numbers have encoding lengths polynomial in the total input length. As an application, we obtain a strongly polynomial algorithm for continuous multicommodity flow with shared capacities and quadratic costs of aggregate arc flow, independently of demands, capacities, and cost coefficients. Objective compression and continuous-integer proximity yield a local solver returning a point close to an optimum. We relax nonnegativity on coordinates with zero optimal dual slack, minimize the largest remaining coordinate, and optimize over the relaxed coordinates. A descent LP over the recession cone provides a complementary bound. Circuit decomposition combines these bounds into a scale ensuring that each local call reveals a new coordinate. At most $m$ calls, followed by two LPs, recover an exact optimum and its dual certificate.

0.20

On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs

cs.CC math.OC ·2026-09-09 ·Sergey S. Ketkov, Oleg A. Prokopyev
theory similarity 0.60
Abstract

Exact algorithms for solving mixed-integer bilevel linear programs (MIBLPs) typically rely on sequences of lower and upper bounds that converge to the optimal value. These procedures are commonly initialized using the single-level relaxation (SLR), obtained by omitting the follower's optimality condition and solving the resulting single-level optimization problem. In this paper, we investigate whether, for broad classes of MIBLPs, the resulting standard bounds admit uniform improvements that can be computed within the same computational complexity regime. For pure continuous bilevel linear programs, we show that, unless $P = NP$, neither the SLR-based lower bound nor its associated upper bound can be uniformly improved in polynomial time, even for the class of min-max problems. We then extend this analysis to the class of pure integer min-max bilevel linear programs under the assumption that the polynomial hierarchy does not collapse. First, we show that the continuous relaxation of the SLR admits no uniform polynomial-time computable improvement. We then prove that neither the SLR itself nor its associated upper bound admits a uniform improvement by a polynomial-time algorithm with access to a mixed-integer linear programming (MILP) oracle. Importantly, this rules out uniform improvements by iterative MILP-based approaches, including cutting-plane-based and decomposition algorithms. Overall, our results demonstrate that the SLR-based bounds are, in a complexity-theoretic sense, unimprovable systematically within their natural computational regimes.

0.24

Mixed-integer dual network problems are solvable in strongly polynomial time

cs.DS math.OC ·2026-11-10 ·Giacomo Zambelli
similarity 0.58
Abstract

In this paper we show that mixed-integer linear programming is solvable in strongly polynomial time if the constraint matrix is totally unimodular with at most two nonzero entries in every row. This is done by reducing the problem to an instance of minimization of an $L$-convex function.

0.27

Integer Quadratic Programming is W[1]-Hard Parameterized by the Number of Variables

cs.CC cs.DSmath.OC ·2026-08-18 ·Anton Herrmann
highly cited similarity 0.58
Abstract

We show that Integer Quadratic Programming is W[1]-hard parameterized by the number of variables. Thus, under standard complexity assumptions, Integer Quadratic Programming cannot be solved in f(n)|I|^{O(1)} time for any computable function f where |I| is the size of the encoding and n is the number of variables.

0.47

Parametrize Integer Programming by Packing Imbalanced Circuits

cs.DS math.OC ·2026-11-08 ·Yuheng Shi
similarity 0.58
Abstract

We study the standard form Integer Programming problem (IP) parametrized by the imbalanced circuit packing number. This number is $0$ if and only if $A$ can be transformed to a totally unimodular matrix by row operations, in which case (IP) is solvable in polynomial time. We show that if the constraint matrix represents a graphic matroid, (IP) is fixed-parameter tractable when parametrized by the imbalanced circuit packing number of the matrix. The proof combines an Erdős-Pósa property for edge-colored non-monochromatic cycles with a reduction to mixed-integer programming using few integer variables. In contrast, by a reduction from the parity potential problem, we show NP-completeness of feasibility of (IP) when the constraint matrix represents a cographic matroid, even if kernel of the constraint matrix is $2$-regular and imbalanced circuits pairwise intersect.

0.27

Integer Programming with Polyhedral Constraints on the Image

cs.DS ·2026-11-12 ·Anubhav Dhar, Tim Randolph, Karol Węgrzycki
similarity 0.58
Abstract

We generalize integer programming to the setting in which the image $A \mathbf{x}$ is restricted to an explicitly given rational polyhedron $P$. That is, we solve $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}\in P, \mathbf{x}\in\mathbb{Z}_{\geq 0}^n\}$, where $A\in\mathbb{Z}^{d\times n}$ and $P$ is an explicitly given rational polyhedron. We present a randomized algorithm running in time $(dΔ)^{O(d)}\operatorname{poly}(L)$ in this regime, where $Δ:= \|A\|_\infty$ and $L$ is the binary input length. This running time matches that of the best-known parameterized algorithms for integer programming, due to Eisenbrand and Weismantel and to Jansen and Rohwedder, and improves on the $O(d^2)$ exponent achieved by Dadush, Léonard, Rohwedder, and Verschae in a more general setting. This result enables several applications, including exact algorithms for integer programming and unbounded knapsack in which the consumed resources $A\mathbf{x}$ must satisfy arbitrary additional linear constraints. We also obtain a randomized fixed-parameter algorithm for Unbounded Subset Sum parameterized by the doubling constant, resolving an open problem of Randolph and Węgrzycki. For integer programs with $m$ constraints and bounded row doubling, we obtain an $f(C,m)n^{O(m)}\operatorname{poly}(L)$-time algorithm and show that the dependence on $m$ in the exponent of $n$ is necessary under $\mathsf{W[1]}\ne\mathsf{FPT}$.

0.24

Real-Time Nonlinear Mixed-Integer Model Predictive Control With Horizon-Tail Relaxations

eess.SY math.OC ·2026-11-06 ·Armin Nurkanović
code/data similarity 0.57
Abstract · Code available at: https://github.com/nosnoc/advanced-minmpc

Model predictive control (MPC) of nonlinear systems with discrete decisions leads to mixed-integer nonlinear programs (MINLPs) whose combinatorial complexity often prevents real-time deployment. In this paper, we propose a decomposition-based MPC method that reorders and reduces computations to shorten the delay between receiving a state measurement and applying the control input. Before the measurement arrives, we solve a continuous relaxation of the MINLP at a predicted state and construct a mixed-integer quadratic program (MIQP). Once the measured state is available, we solve the MIQP that reconstructs the discrete controls and simultaneously performs one sequential quadratic programming step toward the corresponding nonlinear solution. To reduce the combinatorial complexity in the horizon length, we either fix the integer controls or relax their integrality over the prediction horizon tail, while retaining an integer-feasible first control input. We derive error bounds relating the nonlinear objective values obtained with the horizon-tail approximations to the optimal value of the original mixed-integer problem. In a data center cooling example, the proposed method reduces mean feedback computation time by 94% relative to a state-of-the-art MINLP method with a total closed-loop cost difference of less than 1%.

0.36

4-Block Integer Programming is in FPT

cs.CC ·2026-09-22 ·Martin Koutecký, Alexandra Lassota, Koen Ligthart
similarity 0.57
Abstract · 23 pages, 0 figures

Integer programming is a fundamental and important NP-hard problem. This motivated extensive efforts in studying several tractable subclasses. One of the most important, unresolved complexity questions is the parameterized complexity of 4-block IPs, a natural class characterized by having a diagonal matrix with small blocks after deleting few rows and columns. Over the years, significant progress has been made in improving algorithms for 4-block IPs, but the question whether such IPs can be solved in FPT time, parameterized by the block dimensions and largest matrix coefficient, has remained open. This question is repeatedly highlighted, most recently by Koutecký [IPEC 2025] and by Eisenbrand and Rothvoss [SODA 2026]. We resolve this question in the positive by providing an FPT time algorithm. Our algorithm can optimize non-linear, separable convex objective functions, and can be extended to broader classes of constraint matrices (such as tree-fold or multi-stage) and allows appending few ``global'' columns to it, and it allows coefficients unbounded by the parameters in those columns. It is known that tractability cannot be extended further in any of those directions. The key structural property that we establish is that a function $f\colon\mathbb Z^n\to\mathbb R$ that is integer midpoint convex, i.e., $f(x)\le\tfrac12f(x-p)+\tfrac12f(x+p)$ for all $x,p\in\mathbb Z^n$, can be extended to a convex function on the set $2d\mathbb Z^n\cap L$ if $L$ is a linear subspace of dimension $d$. This closes the gap in a recent work by Ligthart [arXiv 2606.30330, 2026], which allows us to extend the previous algorithm that solves 4-block integer programs with a single global variable to incorporate any parameterized number of global variables. As an example, we apply our algorithm to solve an open problem posed by Boehmer and Koana [ACM Trans. Algorithms, 2024] in Max-Min Fair Matching.

0.40