Integer Programming with Polyhedral Constraints on the Image
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Integer Programming with Polyhedral Constraints on the Image".
Jane: Here's the gist of the paper. Integer Programming with Polyhedral Constraints on the Image generalizes integer programming to settings where the image Ax is restricted to an explicitly given rational polyhedron P, solving min(cTx: Ax ∈ P, x ∈ Zn ≥0) in randomized time (d∆)O(d) poly(L), which matches best-known parameterized algorithms for integer programming Problem Generalization and Motivation The paper addresses the question of whether integer programming can be generalized without compromising its parameterized running time, motivated by applications where constraints are linear functions of multiple resources <ref:2611.17311#pg3>.
Tom: The authors generalize the resource constraint Ax = b to Ax ∈ P, where P is a polyhedron defined as P = g(y ∈ Rd: By ≤ b) for a given B ∈ Qr×d and b ∈ Qr <ref:2611.17311#pg4>.
Jane: This formulation captures problems like Unbounded Knapsack with multiple budgets and Unbounded Subset Sum parameterized by the doubling constant <ref:2611.17311#pg4>.
Tom: Core Theorem on IP-PC Theorem 1 states that IP-PC can be solved in randomized time (d∆)O(d) poly(L), with a success probability of at least 2/3 <ref:2611.17311#pg5>.
Paper summary: Tom: So, wrapping up on "Integer Programming with Polyhedral Constraints on the Image," the main point is they solved it in randomized time of d delta times polynomial in L, which matches our best existing algorithms for integer programming.
Jane: And they show that this method works even when we generalize the constraint Ax equals b to Ax being inside a rational polyhedron P defined by B and b.
Lu: The paper demonstrates how you can capture problems like Unbounded Knapsack with multiple budgets using this formulation, and it provides a concrete running time for the C-Unbounded Subset Sum problem as well.
Meng: For deployment, what this means is that we can tackle resource allocation scenarios where those resources have arbitrary linear limitations without immediately hitting an intractable complexity wall.
Tom: The authors show a success probability of at least two thirds, and they’ve already used this result to suggest new complexity bounds for C-ILP, even proving a lower bound related to W one not being FPT.
Jane: It really shows how these geometric constraints on the image can open up new avenues for finding exact integer solutions in problems that were previously too hard under those specific setups.
Conclusion: Tom: So, we've been looking at how they tackle integer programming when the image of that program is restricted to a specific shape, a rational polyhedron P.
Jane: That's right, and the title itself says "Integer Programming with Polyhedral Constraints on the Image." It sounds way more complicated than just regular integer programming.
Lu: The core idea is taking something like min c times x transpose subject to Ax being in that polyhedron P instead of just Ax equals some fixed vector b.
Meng: So, instead of finding a single exact point, we're looking for an integer point inside a whole region defined by linear inequalities. That sounds like it could be really useful for real-world resource planning where the constraints aren't perfectly fixed.
Tom: Exactly, and they show that this approach works in randomized time of d delta times polynomial in L, which is basically matching the best known algorithms for regular integer programming.
Jane: But what does that mean for someone just trying to understand it? It means you can take a problem with these complex geometric constraints and find an exact integer solution without the running time blowing up exponentially based on some complexity parameter L.
Lu: The method uses these techniques, like enumerating solutions with small supports and then using fast integer linear programming methods on scaled-down copies of the polyhedra.
Meng: From a deployment standpoint, that success probability of at least two thirds is pretty solid for a practical approach. It's not some theoretical proof; it’s how you actually get an answer reliably.
Jane: It suggests that problems with these specific image constraints, like multiple budgets in knapsack scenarios, are solvable in a way we didn't expect them to be.
Tom: And they even connect this to hardness results for things like the C-Unbounded Subset Sum problem, showing how much this structural change affects what’s possible.
Jane: It really opens up a new category of problems that were previously thought too hard because of the specific way the constraints are defined in those polyhedra.
Lu: We've seen how they use Freiman reductions to simplify some of these constraint sets, which shows how low-dimensional they can be for certain structures.
Meng: If this method holds up on real traffic data, it could mean we can optimize those complex resource allocations much faster than current methods allow.
Anubhav Dhar, Tim Randolph, Karol Węgrzycki
Max Planck Institute for Informatics · Saarland University · Harvey Mudd College
cs.DS
Submitted: 2026-11-12
Updated: 2026-11-12
Code: https://github.com/openai/math
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 91/100
The gist: Integer Programming with Polyhedral Constraints on the Image generalizes integer programming to settings where the image Ax is restricted to an explicitly given rational polyhedron P…
Key concepts
- Integer Programming with Polyhedral Constraints (IP-PC)
- This is the generalization of integer programming where the constraint Ax=b is replaced by Ax ∈ P, where P is a polyhedron defined by linear inequalities. The goal remains finding an integer solution x that minimizes cTx subject to this new polyhedral constraint.
- Polyhedron P
- P represents a set of points in space defined by a system of linear inequalities (By ≤ b). This structure allows the problem to handle resource constraints that are not fixed equalities but rather bounds or inequalities, such as multiple budgets in knapsack problems.
- Randomized Time (d∆)O(d) poly(L)
- This describes the running time complexity of the algorithm. It means the solution can be found quickly using randomization, with a runtime that is polynomial in the encoding length L and depends polynomially on other parameters like d and C.
- Freiman Reduction
- This technique transforms problems involving constraints defined by sets with small doubling into lower-dimensional problems. This reduction simplifies the structure of the polyhedron P, making it easier to solve using specialized algorithms that depend on the doubling constant C.
Terminology
Summary
Integer Programming with Polyhedral Constraints on the Image generalizes integer programming to settings where the image Ax is restricted to an explicitly given rational polyhedron P, solving min(cTx: Ax ∈ P, x ∈ Zn ≥0) in randomized time (d∆)O(d) poly(L), which matches best-known parameterized algorithms for integer programming
Problem Generalization and Motivation
The paper addresses the question of whether integer programming can be generalized without compromising its parameterized running time, motivated by applications where constraints are linear functions of multiple resources <ref:2611.17311#pg3>. The authors generalize the resource constraint Ax = b to Ax ∈ P, where P is a polyhedron defined as P = g(y ∈ Rd: By ≤ b) for a given B ∈ Qr×d and b ∈ Qr <ref:2611. p. 2 We can capture these situations by generalizing the resource constraint Ax = b
to Ax ∈ P, where P is a polyhedron (P = {y ∈ R
d
: By ≤ b} for a given
B ∈ Qr×d and b ∈ Qr
). Geometrically, this problem can be thought of as
optimization over the integer cone generated by the columns of A with an
additional polyhedral constraint (see Figure 1 for geometric intuition). The circled point minimizes cost over the feasible points. This formulation also naturally captures several other problems, including
Unbounded Knapsack with multiple budgets (Corollary 1) and Unbounded Subset
Sum parameterized by the doubling constant (Section 4).Where the paper says it
Where the paper says it
Core Theorem on IP-PC
Theorem 1 states that IP-PC can be solved in randomized time (d∆)O(d) poly(L), with a success probability of at least 2/3 <ref:2611.17311#pg5>. This result is asymptotically equivalent to the running time of the best existing algorithms for integer linear programming <ref:2611. p. 2 The inequalities defining P affect
the runtime only polynomially through the encoding length L. Note that this is
asymptotically equivalent to the running time of the best existing algorithms [5,7]. In other words, IP-PC is in randomized FPT with respect to the parameters
d (matrix height) and ∆ (matrix entry size). The inequalities defining P affect
the runtime only polynomially through the encoding length L.Where the paper says it
Where the paper says it
Techniques for Achieving Running Time
The algorithm relies on three main ingredients:
-
Enumerating solutions with small supports, using Theorem 2 to find a lexicographically minimal solution x∗ with support at most Γ = O(d log(d∆)) <ref:2611. p. 6
17311#pg8>. Lemma 1 constructs a family of candidate support sets S that guarantees containing the support of the lexicographically minimum solution for every image β <ref:2611. p. 4Where the paper says it
1 Enumerating Solutions with Small Supports Eisenbrand and Shmonin [4] proved that standard-form integer programs with finite optima admit sparse optimal solutions. We use the following closely related statement due to Rohwedder and Węgrzycki [16], which specifies the existence of a lexicographically minimal solution with a small support.
17311#pg8>.Where the paper says it
1 we use a result of Rohwedder and Węgrzycki [16], who build on Eisenbrand and Shmonin [4] to conclude that every bounded, feasible instance of IP-PC has a lexicographically minimum optimal solution x ∗ with support at most O(d log(d∆)). Instead of trying all possible small supports, we then take advantage of the fact that our polyhedral constraint applies to a low-dimensional image: we can enumerate a set of candidate supports guaranteed to contain the support of the lexicographically minimum solution for every image Ax ∈ Z d .
-
Fast Integer Linear Programming with Known Residues, which uses Corollary 4 to find an integer point in a translated, scaled-down copy of the polyhedron Q by guessing its residue modulo lZn <ref:2611. p. 7
17311#pg9>.Where the paper says it
We can use this algorithm to find an integer point by guessing the residue of a target integer point modulo ℓZ n. Corollary 4.
-
Removing Duplicate Columns, which uses Lemma 2 to reduce the number of variables n by bounding it by (2∆ + 1)d <ref:2611. p. 8
17311#pg10>.Where the paper says it
By Theorem 3 the running time is 2 O(n) · poly(L). 3 Removing Duplicate Columns Because duplicate columns of A can be safely removed, we can bound n by a function of ∆ and d without loss of generality.
Applications and Further Results
The paper presents several related problems:
>(Problem 1: IP-PC):
IP-PC is solved in randomized time (d∆)O(d) poly(L), with success probability at least 2/3 <ref:2611.17311#pg5>.
(Problem 2: K-PC):
Knapsack with Polyhedral Constraints (K-PC) can be solved in randomized time (d∆)O(d) poly(L), following from Theorem 1 by setting c = -p <ref:2611.17311#pg6>.
(Problem 3: C-USS):
C-Unbounded Subset Sum (C-USS) can be solved in randomized time f(C) · poly(L), where f is a computable function depending only on the doubling constant C <ref:2611.17311#pg7>.
(Problem 4: C-ILP):
C-Row-Doubling ILP (C-ILP) can be solved in randomized time f(C, m) nO(m) poly(L), where the dependence on n is polynomial in m <ref:2611.17311#pg11>.
Lower Bound Implications
The authors prove a lower bound for C-ILP, showing that under W[1]!= FPT, integer programming with m equations and row doubling at most two has no f(m) poly(L)-time algorithm <ref:2611. p. 0 For integer programs with m constraints
and bounded row doubling, we obtain an f(C, m) n
O(m) poly(L)-time
algorithm and show that the dependence on m in the exponent of n is
necessary under W[1] ̸= FPT. Keywords: Integer programming · Parameterized algorithms · Unbounded subset sum · Additive combinatorics
1 Introduction
Integer linear programming provides a framework for problems in combinatorial
optimization and the geometry of numbers [5]. The recently
claimed refutation of the Exponential Time Hypothesis (ETH) [12] would not
settle whether W[1] = FPT. We exclude algorithms that take f(m) poly(L) time
under W[1] ̸= FPT, even for row doubling at most two (Theorem 4), showing
that the exponent of n must depend on m. The recently
claimed refutation of the Exponential Time Hypothesis (ETH) [12] would not
settle whether W[1] = FPT. We exclude algorithms that take f(m) poly(L) time
under W[1] ̸= FPT, even for row doubling at most two (Theorem 4), showing
that the exponent of n must depend on m.Where the paper says it
Where the paper says it
Where the paper says it
Algorithm Summary
Algorithm 1, the threshold search variant, runs in total time (d∆)O(d) poly(L) <ref:2611.17311#pg16>. It combines enumerating candidate supports S with solving sub-instances using an approximate integer programming algorithm via a separation oracle for approximate ILP <ref:2611. p. 4 Every candidate support set gives us a low-dimensional sub-instance. Solving
each sub-instance with a generic integer programming algorithm (e. 2 Fast Integer Linear Programming with Known Residues
Every candidate support in the set S given by Lemma 1 corresponds to a
subproblem of dimension at most Γ. At this point, we could solve each subproblem
in time (log Γ)
O(Γ)
[15]; however, substituting the bound on Γ gives (d∆)
ω(d)
,
exceeding our target runtime.Where the paper says it
Where the paper says it
Proof Sketch Details
The proof of Theorem 1 involves constructing a dynamic programming table T indexed by support size s and image β, where T[s, β] stores the lexicographically minimum solution vector with an L1-norm at most s <ref:2611.17311#pg15>. This construction takes time (d∆)O(d) poly(L), leading to a total runtime of (d∆)O(d) poly(L) for the main loop <ref:2611. p. 9 Every table cell is indexed by an image in [−n
′
(ℓ − 1)∆ : n
′
(ℓ − 1)∆]
d by
construction, so |R| := |Tn′ | ≤ (2n
′
(ℓ − 1)∆ + 1)d
. Each table Tj−1 makes
|Tj−1| · ℓ ≤ |R|ℓ calculations to compute Tj , so the total process takes time
|R| · n
′
ℓ · poly(L). Our algorithms return only feasible points
and succeed with probability at least 2/3. For optimization, success means finding
an optimum or correctly reporting infeasibility or unboundedness.Where the paper says it
Where the paper says it
Freiman Reduction Details
For applications to sets with small doubling, the constructive Freiman reduction is used to transform row constraints into a low-dimensional problem <ref:2611.17311#pg13>. Lemma 4 constructs a matrix A ∈ Za×n≥0 and s ∈ Za such that A∞ ≤ h(C)n2/a and zj = sTAj for all j <ref:2611. p. 0 This problem is well
known to be NP-hard [8], which motivates algorithms for restricted parameter
regimes. arXiv:2611. This problem is well
known to be NP-hard [8], which motivates algorithms for restricted parameter
regimes. arXiv:2611. The circled point minimizes cost over the feasible points. This formulation also naturally captures several other problems, including
Unbounded Knapsack with multiple budgets (Corollary 1) and Unbounded Subset
Sum parameterized by the doubling constant (Section 4).Where the paper says it
Where the paper says it
Where the paper says it
Clique Hardness Argument
The lower bound for C-ILP is established by reducing from Multicolored Clique, where the reduction constructs an instance with m = 2k + 3 and n = O(kN2), and encoding length Ok(N3). This reduction shows that any f(m) poly(L)-time algorithm would solve Multicolored Clique in N O(1) time, contradicting the known hardness of k-Clique. p. 0 That
is, we solve min{c
Tx : Ax ∈ P, x ∈ Z
n
≥0}, where A ∈ Z
d×n
and P is an
explicitly given rational polyhedron. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ and
L is the binary input length. The recently
claimed refutation of the Exponential Time Hypothesis (ETH) [12] would not
settle whether W[1] = FPT. We exclude algorithms that take f(m) poly(L) time
under W[1] ̸= FPT, even for row doubling at most two (Theorem 4), showing
that the exponent of n must depend on m.Where the paper says it
Where the paper says it
Acknowledgments and Disclosure
The work acknowledges support from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) project number 559177164 <ref:2611.17311#pg14>. The authors state that the arguments were developed in collaboration with ChatGPT 6. p. 3 Parameter: C := |Z + Z|/|Z|. 6
Randolph and Węgrzycki developed an n
OC(1) log log log(n)
-time algorithm and
left open whether C-USS can be solved in time n
OC(1) (that is, whether C-USS is
in randomized XP). This problem is well
known to be NP-hard [8], which motivates algorithms for restricted parameter
regimes. arXiv:2611. This problem is well
known to be NP-hard [8], which motivates algorithms for restricted parameter
regimes. arXiv:2611.Where the paper says it
Where the paper says it
Where the paper says it
References
The references listed are Chen, L., Mao, Y., Zhang, G.: Integer programming: An algorithm with exponent linear in the dimension. p. 0 For integer programs with m constraints
and bounded row doubling, we obtain an f(C, m) n
O(m) poly(L)-time
algorithm and show that the dependence on m in the exponent of n is
necessary under W[1] ̸= FPT. Keywords: Integer programming · Parameterized algorithms · Unbounded subset sum · Additive combinatorics
1 Introduction
Integer linear programming provides a framework for problems in combinatorial
optimization and the geometry of numbers [5]. This problem is well
known to be NP-hard [8], which motivates algorithms for restricted parameter
regimes. arXiv:2611. This problem is well
known to be NP-hard [8], which motivates algorithms for restricted parameter
regimes. arXiv:2611. Integer Programming with Polyhedral Constraints
on the Image
Anubhav Dhar1,2
, Tim Randolph3(
)
, and Karol Węgrzycki1
1 Max Planck Institute for Informatics, Saarbrücken, Germany
adhar@mpi-sws. org, kwegrzyc@mpi-inf. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. Classical algorithms exploit two complementary restrictions on the input: few
variables (small n) or few constraints with bounded coefficients (small d and
∥A∥∞). For example, Lenstra’s algorithm [10] runs in polynomial time when
the number of variables is fixed (see also the recent breakthrough of Reis and
Rothvoss [15]). Classical algorithms exploit two complementary restrictions on the input: few
variables (small n) or few constraints with bounded coefficients (small d and
∥A∥∞). For example, Lenstra’s algorithm [10] runs in polynomial time when
the number of variables is fixed (see also the recent breakthrough of Reis and
Rothvoss [15]). 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 Ax must satisfy arbitrary additional linear constraints. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. 1 we use a result of
Rohwedder and Węgrzycki [16], who build on Eisenbrand and Shmonin [4] to
conclude that every bounded, feasible instance of IP-PC has a lexicographically
minimum optimal solution x
∗ with support at most O(d log(d∆)). Instead of
trying all possible small supports, we then take advantage of the fact that our
polyhedral constraint applies to a low-dimensional image: we can enumerate a set
of candidate supports guaranteed to contain the support of the lexicographically
minimum solution for every image Ax ∈ Z
d
. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. First, in Section 3. 1 we use a result of
Rohwedder and Węgrzycki [16], who build on Eisenbrand and Shmonin [4] to
conclude that every bounded, feasible instance of IP-PC has a lexicographically
minimum optimal solution x
∗ with support at most O(d log(d∆)). Dadush, Léonard, Rohwedder, and Verschae [3] consider the even
more general objective g(Ax) + c
Tx with arbitrary variable bounds. However, for
explicitly given A, these algorithms run in n
d
(d∆)
O(d
2
) poly(L) time, significantly
slower than the fastest known algorithms for integer linear programming [5,7]. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. For integer programs with few constraints, Papadimitriou [13]
gave a pseudopolynomial algorithm. Eisenbrand and Weismantel [5] used the
Steinitz lemma to obtain a running time of (d∆)
O(d) poly(L · ∥b∥), where ∆ =
∥A∥∞ ≥ 1 and L is the binary input length (see also [7] for a better dependence
on ∥b∥). Variations on this question have already attracted significant attention in the
literature. For example, Hunkenschröder, Pokutta, and Weismantel [6] generalized
the objective function to g(Ax), where g is a sharp, convex function given by
an oracle. Variations on this question have already attracted significant attention in the
literature. For example, Hunkenschröder, Pokutta, and Weismantel [6] generalized
the objective function to g(Ax), where g is a sharp, convex function given by
an oracle. 1 we use a result of
Rohwedder and Węgrzycki [16], who build on Eisenbrand and Shmonin [4] to
conclude that every bounded, feasible instance of IP-PC has a lexicographically
minimum optimal solution x
∗ with support at most O(d log(d∆)). Instead of
trying all possible small supports, we then take advantage of the fact that our
polyhedral constraint applies to a low-dimensional image: we can enumerate a set
of candidate supports guaranteed to contain the support of the lexicographically
minimum solution for every image Ax ∈ Z
d
. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. Integer Programming with Polyhedral Constraints
on the Image
Anubhav Dhar1,2
, Tim Randolph3(
)
, and Karol Węgrzycki1
1 Max Planck Institute for Informatics, Saarbrücken, Germany
adhar@mpi-sws. org, kwegrzyc@mpi-inf. For integer programs with m constraints
and bounded row doubling, we obtain an f(C, m) n
O(m) poly(L)-time
algorithm and show that the dependence on m in the exponent of n is
necessary under W[1] ̸= FPT. Keywords: Integer programming · Parameterized algorithms · Unbounded subset sum · Additive combinatorics
1 Introduction
Integer linear programming provides a framework for problems in combinatorial
optimization and the geometry of numbers [5]. Classical algorithms exploit two complementary restrictions on the input: few
variables (small n) or few constraints with bounded coefficients (small d and
∥A∥∞). For example, Lenstra’s algorithm [10] runs in polynomial time when
the number of variables is fixed (see also the recent breakthrough of Reis and
Rothvoss [15]). For example, Lenstra’s algorithm [10] runs in polynomial time when
the number of variables is fixed (see also the recent breakthrough of Reis and
Rothvoss [15]). For integer programs with few constraints, Papadimitriou [13]
gave a pseudopolynomial algorithm. 4 Knop, Pilipczuk, and Wrochna [9] proved a tight ETH-based lower bound excluding
2
o(d log d) poly(L)-time algorithms, even for 0/1 constraint matrices. A recent preprint
claims to refute ETH [12], so we use the weaker Almost-ETH assumption here. Integer Programming with Polyhedral Constraints
on the Image
Anubhav Dhar1,2
, Tim Randolph3(
)
, and Karol Węgrzycki1
1 Max Planck Institute for Informatics, Saarbrücken, Germany
adhar@mpi-sws. org, kwegrzyc@mpi-inf. Eisenbrand and Weismantel [5] used the
Steinitz lemma to obtain a running time of (d∆)
O(d) poly(L · ∥b∥), where ∆ =
∥A∥∞ ≥ 1 and L is the binary input length (see also [7] for a better dependence
on ∥b∥). Under the Almost-Exponential Time Hypothesis (see [11]), ILP requires
2
d
1−o(1) poly(L) time even when A ∈ {0, 1}
d×n (see [9]4
). 17311v1 [cs. DS] 12 Nov 2026 Eisenbrand and Weismantel [5] used the
Steinitz lemma to obtain a running time of (d∆)
O(d) poly(L · ∥b∥), where ∆ =
∥A∥∞ ≥ 1 and L is the binary input length (see also [7] for a better dependence
on ∥b∥). Under the Almost-Exponential Time Hypothesis (see [11]), ILP requires
2
d
1−o(1) poly(L) time even when A ∈ {0, 1}
d×n (see [9]4
). For example, Lenstra’s algorithm [10] runs in polynomial time when
the number of variables is fixed (see also the recent breakthrough of Reis and
Rothvoss [15]). For integer programs with few constraints, Papadimitriou [13]
gave a pseudopolynomial algorithm. Integer Programming with Polyhedral Constraints
on the Image
Anubhav Dhar1,2
, Tim Randolph3(
)
, and Karol Węgrzycki1
1 Max Planck Institute for Informatics, Saarbrücken, Germany
adhar@mpi-sws. org, kwegrzyc@mpi-inf. This result enables several applications, including exact algorithms for
integer programming and unbounded knapsack in which the consumed
resources Ax 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. This result enables several applications, including exact algorithms for
integer programming and unbounded knapsack in which the consumed
resources Ax 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. This result enables several applications, including exact algorithms for
integer programming and unbounded knapsack in which the consumed
resources Ax 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. This result enables several applications, including exact algorithms for
integer programming and unbounded knapsack in which the consumed
resources Ax 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. Integer Programming with Polyhedral Constraints
on the Image
Anubhav Dhar1,2
, Tim Randolph3(
)
, and Karol Węgrzycki1
1 Max Planck Institute for Informatics, Saarbrücken, Germany
adhar@mpi-sws. org, kwegrzyc@mpi-inf. Classical algorithms exploit two complementary restrictions on the input: few
variables (small n) or few constraints with bounded coefficients (small d and
∥A∥∞). For example, Lenstra’s algorithm [10] runs in polynomial time when
the number of variables is fixed (see also the recent breakthrough of Reis and
Rothvoss [15]). Integer Programming with Polyhedral Constraints
on the Image
Anubhav Dhar1,2
, Tim Randolph3(
)
, and Karol Węgrzycki1
1 Max Planck Institute for Informatics, Saarbrücken, Germany
adhar@mpi-sws. org, kwegrzyc@mpi-inf. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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 Ax 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) poly(L)-time
algorithm and show that the dependence on m in the exponent of n is
necessary under W[1] ̸= FPT. Keywords: Integer programming · Parameterized algorithms · Unbounded subset sum · Additive combinatorics
1 Introduction
Integer linear programming provides a framework for problems in combinatorial
optimization and the geometry of numbers [5]. org, kwegrzyc@mpi-inf. de
2 Saarland University, Saarbrücken, Germany
3 Harvey Mudd College, Claremont, CA, USA
trandolph@g. We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. First, in Section 3. 1 we use a result of
Rohwedder and Węgrzycki [16], who build on Eisenbrand and Shmonin [4] to
conclude that every bounded, feasible instance of IP-PC has a lexicographically
minimum optimal solution x
∗ with support at most O(d log(d∆)). We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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. For example, Lenstra’s algorithm [10] runs in polynomial time when
the number of variables is fixed (see also the recent breakthrough of Reis and
Rothvoss [15]). For integer programs with few constraints, Papadimitriou [13]
gave a pseudopolynomial algorithm. This result enables several applications, including exact algorithms for
integer programming and unbounded knapsack in which the consumed
resources Ax 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. Classical algorithms exploit two complementary restrictions on the input: few
variables (small n) or few constraints with bounded coefficients (small d and
∥A∥∞). For example, Lenstra’s algorithm [10] runs in polynomial time when
the number of variables is fixed (see also the recent breakthrough of Reis and
Rothvoss [15]). First, in Section 3. 1 we use a result of
Rohwedder and Węgrzycki [16], who build on Eisenbrand and Shmonin [4] to
conclude that every bounded, feasible instance of IP-PC has a lexicographically
minimum optimal solution x
∗ with support at most O(d log(d∆)). We present a randomized algorithm
running in time (d∆)
O(d) poly(L) in this regime, where ∆ := ∥A∥∞ 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- Page 1 ---
Integer Programming with Polyhedral Constraints on the Image generalizes integer programming to settings where the image Ax is restricted to an explicitly given rational polyhedron P, solving min(cTx: Ax ∈ P, x ∈ Zn ≥0) in randomized time (d∆)O(d) poly(L), which matches best-known parameterized algorithms for integer programming
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Generalize integer programming to settings where images are restricted to an explicitly given rational polyhedron P, solving min(c Tx: Ax in P, x in Z n >= 0) in randomized time (d∆) O(d) poly(L). This enables exact algorithms for integer programming and unbounded knapsack problems with arbitrary linear constraints.
-
Develop a randomized fixed-parameter algorithm for Unbounded Subset Sum parameterized by the doubling constant C, solving it in randomized time f(C) poly(L). This resolves an open problem concerning the doubling constant parameterization of Unbounded Subset Sum.
-
Create a randomized algorithm for Knapsack with Polyhedral Constraints (K-PC), solving max(p Tx: Ax in P, x in Z n >= 0) in randomized time (d∆) O(d) poly(L). This extends the results from IP-PC to maximization problems under polyhedral constraints.
-
Achieve a fixed-parameter tractable algorithm for C-Row-Doubling ILP (C-ILP), solving min(c Tx: Mx = 0) with row doubling at most C in randomized time f(C, m) n O(m) poly(L). This leverages Freiman compression to reduce the problem dimension based on the row doubling constant.
-
Implement a Monte Carlo algorithm for Unbounded Subset Sum parameterized by the doubling constant C, solving it in time f(C) poly(L). This provides a concrete algorithmic solution for problems where the underlying set has significant additive structure captured by C.
Abstract
We generalize integer programming to the setting in which the image A x is restricted to an explicitly given rational polyhedron P. That is, we solve c T x:A x in P, x in Z at least 0 n, where A in Z d times n and P is an explicitly given rational polyhedron. We present a randomized algorithm running in time (dΔ) O(d) poly(L) in this regime, where Δ:= |A| infinity 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 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) poly(L) -time algorithm and show that the dependence on m in the exponent of n is necessary under not equal to.
Sources
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time