CS Paper Radar

Integer Programming with Polyhedral Constraints on the Image

Anubhav Dhar, Tim Randolph, Karol Węgrzycki

cs.DS ·submitted 2026-11-12 18:56 UTC · v1

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}$.

Closest papers

Nearest neighbours by meaning across the whole index.

Even Faster Algorithms for Bounded Integer Programming

cs.DS ·2026-11-18 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.75
Abstract

We study integer programs $\min\{\mathbf{c}^{T}\mathbf{x}: A\mathbf{x}=\mathbf{b},\mathbf{l}\le\mathbf{x}\le\mathbf{u},\mathbf{x}\in\mathbb{Z}^n\}$ with a fixed number $d$ of equality constraints and constraint coefficients of absolute value at most $N$. Chen, Mao, and Zhang recently solved such programs in almost $N^{2d}$ time. We show that any polynomial saving for $(\min,+)$-convolution carries over to this problem. If witnessed $(\min,+)$-convolution of arrays of length $m$ can be computed in $\tilde{O}(m^ρ)$ time with error probability $p$, then for every $\varepsilon>0$ bounded integer programming can be solved in $\tilde{O}\bigl(n+N^{(\max\{ρ,3/2\}+\varepsilon)d}\bigr)$ time with the same error probability $p$, up to polynomial factors in the encoding length and the cost of one linear program. A deterministic convolution algorithm yields a deterministic integer programming algorithm. Combined with recent truly subquadratic algorithms for $(\min,+)$-convolution, this gives a deterministic algorithm running in $\tilde{O}(n+N^{1.99986\,d})$ time and a randomized algorithm running in $\tilde{O}(n+N^{1.9602\,d})$ time, up to the same factors.

0.09

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

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

cs.DS ·2026-11-12 ·Klaus Jansen, Felix Ohnesorge, Björn Schumacher
similarity 0.71
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

Bounded Integer Programming in Almost $N^{2d}$ Time

cs.DS ·2026-10-19 ·Lin Chen, Yuchen Mao, Guochuan Zhang
theory similarity 0.70
Abstract

We study integer programs in standard form $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}=\mathbf{b},\mathbf{l}\leq\mathbf{x}\leq\mathbf{u},\ \mathbf{x}\in\mathbb{Z}^n\}$, where $A\in\mathbb{Z}^{d\times n}$, all entries of $\mathbf{b},\mathbf{c},\mathbf{l},\mathbf{u}$ are integers, and every variable bound is finite. Let $N$ be an upper bound on the absolute values of the entries of $A$, and $c_{\max}$ one on the absolute values of the costs. For every fixed $d$ and every fixed $\varepsilon>0$ we give a deterministic algorithm running in time \[ T_{\textrm LP}+O_d(n)+O_{d,\varepsilon}\bigl(N^{2d+\varepsilon}\log^2(c_{\max}+2)\bigr), \] where $T_{\textrm LP}$ is the time to solve one linear programming relaxation exactly. Prior to our work, the best known running time for bounded variables was $N^{O(d^2)}$ [Eisenbrand \& Weismantel'20], and it has been a fundamental open problem whether the exponent $O(d^2)$ can be improved to one linear in $d$. We answer this question affirmatively, with the exponent $2d+\varepsilon$.

0.16

Satisfiability and freezing in random integer programs

cs.DM math.PRmath.CO ·2026-10-08 ·Dylan J. Altschuler, Ruben Ascoli, Will Perkins
similarity 0.65
Abstract · Minimal AI usage. Comments welcome. 49 pages

We study a model of a random centrally symmetric polytope and ask about the existence of points in the polytope with non-zero, integer coordinates. Our main results are the location of a sharp threshold for the existence of these integer points, a characterization of the typical empirical distribution of their coordinates, and showing that near the feasibility threshold these integer points are almost always totally isolated --- at linear Hamming distance to the nearest other integer point in the polytope. The behavior of these random integer programs is related to that of the symmetric binary perceptron (the case when coordinates of points are $\pm 1$-valued). The lack of symmetry in the set of potential solutions leads to new questions and phenomena, such as the distribution of the coordinate sizes in typical solutions, and requires the development of new information-theoretic techniques to deal with higher-dimensional optimization problems arising in the method of moments.

0.24

$\ell_p$-Norm Maximization over Zonotopes Is W[1]-Hard

cs.CC cs.CG ·2026-08-16 ·Yang Cao, Haoran Qi, Hanzhi Wang
theory similarity 0.65
Abstract

We study $\ell_p$-norm maximization over zonotopes given by rational generators, with input length $L$. For fixed $p=a/b>1$, the exact Turing baseline runs in $n^{O(d)}b^{O(d)}\mathrm{poly}(L)$ time, but fixed-parameter tractability in the ambient dimension $d$ was open [FGHS25]. We prove W[1]-hardness and, under the Exponential Time Hypothesis (ETH), exclude $ρ_p(d)L^{o(d)}$ time, even for $5$-sparse generators, by encoding binary CSP constraints with normalized positive cap generators. We also give a deterministic $(1-\varepsilon)$-approximation with $\varepsilon^{-(d-1)/2}$ dependence and, among algorithms with fixed-degree polynomial dependence on $L$, rule out $(1/\varepsilon)^{o(d)}$ dependence under ETH. Support-function duality transfers the results to positive-output two-layer ReLU networks.

0.42

0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problems

cs.CC math.OCcs.DM ·2026-10-07 ·Alberto Del Pia
similarity 0.65
Abstract

A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. In 1973, Chvátal asked whether 0/1 integer programs over polytopes of bounded Chvátal rank can be solved in polynomial time. For polyhedra of bounded Chvátal rank, integer feasibility is in NP $\cap$ coNP, so it is unlikely to be NP-hard. We answer Chvátal's question negatively already in its most restricted form: for Chvátal rank one, for integer feasibility, and even for the SAT polytopes of formulas whose clauses have at most three literals. Our answer holds under either of two standard assumptions from lattice-based cryptography. First, a polynomial-time algorithm for integer feasibility on such SAT polytopes of Chvátal rank one would solve bounded distance decoding with polynomial factors in deterministic polynomial time, contradicting the conjectured hardness of approximating lattice problems within polynomial factors. Second, assuming the hardness of learning with errors, an average-case analog of bounded distance decoding, the problem is also hard on average, for a polynomial-time samplable distribution of formulas. This also gives negative answers to related questions of Cornuéjols, Lee, and Li. We first prove these results for parallelepipeds, where they rest on an elementary sufficient condition: a polyhedron has Chvátal rank at most one if its width is less than one along every row of some unimodular matrix. For our parallelepipeds, such a matrix exists but is hard to find. For SAT polytopes, we represent candidate lattice vectors by their residues modulo small integers, and binary arithmetic on additional 0/1 variables checks that these vectors lie in the lattice.

0.27

Subexponential Algorithms for Total Search Problems in the Dense Pigeonhole Regime

cs.DS cs.CC ·2026-10-18 ·Jadwiga Czyżewska, Karolina Drabik, Marek Sokołowski, Karol Węgrzycki
theory similarity 0.64
Abstract

The class $\mathsf{PPP}$ captures fundamental total search problems, for which a solution is guaranteed to exist by the pigeonhole principle and the main challenge is to find it. We ask whether problems in this class admit significantly faster algorithms in the \emph{dense regime}. More concretly, we study \emph{binary collision Short Integer Solution} (SIS): given a matrix $A\in\mathbb{Z}_q^{n\times m}$ with $m>n\log q$, the goal is to find distinct $\underline{\mathbf{x}},\underline{\mathbf{y}}\in\{0,1\}^m$ with $A\underline{\mathbf{x}}=A\underline{\mathbf{y}}\pmod q$. Brute-force enumeration can be used to find a collision in $q^{\mathcal{O}(n)} \operatorname{poly}(|I|)$ time, and no significantly faster algorithm for that problem is known. We present an algorithm running in time $q^{o(n)}\cdot\operatorname{poly}(|I|)$ whenever the density parameter $δ:= m/(n\log q)$ is $ω(1)$.\footnote{All logarithms are in base $2$, and $|I|$ is the binary input length.} Building on reductions of Sotiraki et al.~(FOCS~2018), we obtain corresponding algorithms for dense variants of weak constrained SIS, Equal Vector Sums, Minkowski, and Blichfeldt. Our algorithm adapts techniques of Bhati et al.~(FOCS~2026), who gave a subexponential algorithm for Equal Sums in the dense regime and proved a tight conditional lower bound. Their conditional lower bound easily transfers to SIS and shows that the running time of our algorithms is essentially optimal.

0.11