CS Paper Radar

Extending Tardos's Theorem to Separable Convex Quadratic Programming

Bin Cui, Hanqing Li, Xupeng Miao

cs.DS ·submitted 2026-10-05 22:24 UTC · v2
theory

Abstract

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.

Comment
13 pages, no figures. Substantially revised with a simplified algorithm and proofs. Title and author list updated

Closest papers

Nearest neighbours by meaning across the whole index.

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.65
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

Integer Programming with Polyhedral Constraints on the Image

cs.DS ·2026-11-12 ·Anubhav Dhar, Tim Randolph, Karol Węgrzycki
similarity 0.63
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

Multiplicative Weights for Mixed Block Constraints and Maximum Multicommodity Flow

cs.DS ·2026-11-01 ·Vladimir Kolmogorov
similarity 0.63
Abstract · 15 pages

We study multiplicative-weights (MWU) algorithms for block-separable feasibility problems containing both packing and covering constraints. Each iteration optimizes a weighted linear objective over one block, either chosen uniformly at random or visited in a fixed cyclic order. We show that the cyclic algorithm returns an $O(\varepsilon)$-approximate solution after $O(kρ\varepsilon^{-2}\log m)$ oracle calls where $k$ is the number of blocks and $ρ$ is the width of the oracle. The same holds for the randomized version with high probability. Previously, such bounds were shown when the coupling constraints have the same sign [Radzik'95; Villavicencio-Grigoriadis'96]. These analyses critically depended on monotonicity arguments that are not available in the mixed case. As an application, we obtain a deterministic $(1-\varepsilon)$-approximation for maximum multicommodity flow (M-MCF) using $O(k\varepsilon^{-2}\log m\log(km/\varepsilon))$ approximate single-commodity min-cost-flow calls. For planar graphs, and more generally for graph families admitting a near-linear-time min-cost-flow algorithm, this gives total running time $\widetilde O(km\varepsilon^{-2})$. Compared with the $O(km^{1+o(1)}\varepsilon^{-1})$ algorithm of [Chen-Graur-Sidford'25], this improves the dependence on $m$ for these graph families at the cost of a worse dependence on $\varepsilon$. Finally, we give an exponentiation-free finite-precision implementation of the cyclic algorithm. It represents each internal weight by a logarithmic-bit mantissa and exponent, while every price supplied to the block oracle is rational and has a polynomially bounded common denominator.

0.24

A Constructive FPT Algorithm for Integer Cone Optimization with Convex Costs

cs.DS ·2026-09-25 ·Klaus Jansen, Felix Ohnesorge, Björn Schumacher
similarity 0.62
Abstract

We give a deterministic fixed-parameter algorithm for integer cone optimization with convex costs. Given $τ$ rational polytopes in $\R^{d+k}$, we combine generators whose first $d$ coordinates are integral and whose remaining $k$ coordinates may be fractional. Each generator has a convex cost depending only on its integer coordinates. We minimize the total cost of nonnegative integer combinations subject to arbitrary rational linear constraints on the full typewise aggregates and generator counts. Our algorithm runs in time \[ 2^{τ\log(τ+1)\,2^{O(d)}}\cdot |I|^{O(1)}, \] where $|I|$ is the total binary input length. It constructs an optimal representation using at most $2^{2d+1}$ distinct generators per type. The number $k$ of continuous coordinates contributes only to the polynomial input factor. For a single generator type, the running time becomes $2^{2^{O(d)}}\cdot |I|^{O(1)}$. Applications include constructive FPT algorithms for Cone and Polytope Intersection, high-multiplicity bin packing, vector bin packing, and makespan minimization on uniform and unrelated machines. The double-exponential dependence on $d$ is tight for Point-in-Cone and both bin-packing problems assuming $\mathrm{NP}\nsubseteq\mathrm{SUBEXP}$. The mixed-integer formulation also yields additive EPTASs for makespan minimization, machine covering, and envy minimization on identical machines, and additive schemes fixed-parameter tractable in $1/\varepsilon+τ$ on uniform machines.

0.24

Hardness of integer linear feasibility with cyclic support

cs.DM math.OC ·2026-11-05 ·Marco Di Summa
theory similarity 0.62
Abstract

We prove that integer linear feasibility is strongly $NP$-complete even when the constraint matrix has exactly two nonzero entries in every row and column, with its support forming a single cycle. This holds already for monotone systems (one positive and one negative coefficient in each inequality) with nonzero coefficients of absolute value $2$ or $3$ and right-hand sides in $\{-1,0,1,2\}$. No variable bounds are supplied separately from the system. For systems in which each inequality involves at most two variables, this strengthens known hardness results by restricting all numerical data to fixed finite sets. For systems in which each variable occurs in at most two inequalities, this establishes, to the best of our knowledge, the first $NP$-hardness result for feasibility. We also give negative answers, unless $P=NP$, to questions on polynomial-time solvability of integer programs with bounded coefficients and bounded totally $Δ$-modular treewidth, and on fixed-parameter tractability of integer bound propagation with respect to coefficient and right-hand-side magnitudes.

0.24

Approximating the Chvátal--Gomory Closure of Capacity-Bounded Min-Closed Systems

cs.DS ·2026-09-28 ·Stefano Huber, Monaldo Mastrolilli
publishedtheory similarity 0.62
Abstract · 19 pages, a short version of this paper appears in the proceedings of ISAAC 2026

Optimizing over the {0, 1/2} rank-1 Chvàtal-Gomory (CG) closure of a binary integer linear program is NP-hard. While polynomial-time approximation schemes (PTAS) are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for k-slack bounded (capacity-bounded) min-closed systems, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k \ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q \le k \cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup[\tfrac1f,1]$, for any constant integer $f \ge 2$. This closure is contained in the {0, 1/2} rank-1 CG closure.Optimizing over the {0, 1/2} rank-1 CG closure of a binary integer linear program is NP-hard. While PTASes are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for \emph{$k$-slack bounded (capacity-bounded) min-closed systems}, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k \ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q \le k \cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup[\tfrac1f,1]$, for any constant integer $f \ge 2$.

0.61

Autoregressive Differentiable Method for Integer Programming

cs.LG math.OC ·2026-10-01 ·Ouns El Harzli, Yudong Cao
code/data similarity 0.61
Abstract

We introduce an autoregressive differentiable method to solve 0-1 integer programs. We fix an arbitrary order of the binary variables and we train a transformer to predict the next bit while remaining in the feasible set. Our method is first trained on feasible incumbents provided by any solver, thus allowing us to initialize the transformer in the feasible set. Our procedure then implements a Lagrangian penalty to penalize infeasible solutions, and the transformer is further trained to explore the feasible set using Gumbel-softmax activations on the relaxed objective. We have tested our method on non-convex instances of quadratic knapsack problem and demonstrated consistent improvement upon state-of-the-art open-source solvers for dense problems up to 10,000 binary variables. In particular, we empirically demonstrate a phenomenon akin to a tunneling effect where the effective change of variables from binary variable to the continuous weights of the transformer that the method implements enables crossing barriers in the relaxed objective landscape.

0.37

Canonical Truncation for Mixed-Integer and Combinatorial n-Fold Optimization

cs.DS ·2026-11-12 ·Klaus Jansen, Felix Ohnesorge, Björn Schumacher
similarity 0.61
Abstract

We consider a special block-structured integer program with $n$ blocks. Every block has a prescribed number of vectors that need to be selected while minimizing the objective $c^{\intercal}x + g(Ax)$, where $c$ is a rational cost vector, $A$ is an integral matrix with $d$ rows, and $g \colon \mathbb{Z}^d \to \mathbb{Q}\cup \{+\infty\}$ is an arbitrary function. We access $g$ via an oracle that minimizes $c^{\intercal}x + g(Ax)$ when all but $O(d)$ variables are fixed. Our algorithm runs in time $(ndΔ)^{O(d)}(Q + \text{poly}(|I|))$ where $Δ$ is the largest absolute value of an entry in $A$, $Q$ is the necessary time to evaluate the oracle for $g$ and $|I|$ is the size of the input. This model is a variation of the model studied by Dadush et al.~[IPCO 23]. Their model has only a single block but individual upper and lower bounds on the variables instead of prescribed block sums. For their model they present an algorithm with running time $t^d(dΔ)^{O(d^2)}Q$ where $t$ is the number of variables. We use our algorithm to solve mixed-integer linear programs with no upper bounds on the variables, a linear objective, and arbitrarily many constraints involving only fractional variables in time $(mΔ)^{O(m)}\text{poly}(|I|)$, where $m$ is the number of constraints involving integral variables and $Δ$ is the largest absolute value of coefficients of integral variables. This improves the dependence on $m$ in the exponent to asymptotically match the dependency in the integer setting. Further, we use our algorithm to generalize the parameterized algorithm for scheduling on uniformly related machines by Rohwedder~[ICALP 25] to obtain an algorithm for multiple knapsack with running time $w_{\max}^{O(d)}\text{poly}(|I|)$ where $w_{\max}$ is the maximum weight of an item and $d$ the number of different weights.

0.26