Integer Programming with Polyhedral Constraints on the Image

arXiv:2611.17311 · cs.DS · Submitted 2026-11-12 · Read on arXiv

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

Where the paper says it

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

17311#pg4>. This formulation captures problems like Unbounded Knapsack with multiple budgets and Unbounded Subset Sum parameterized by the doubling constant <ref:2611. p. 2
Where the paper says it

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

17311#pg4>.

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

Where the paper says it

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

17311#pg5>. The inequalities defining P affect the runtime only polynomially through the encoding length L <ref:2611. p. 2
Where the paper says it

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.

17311#pg5>.

Techniques for Achieving Running Time

The algorithm relies on three main ingredients:

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

    Where 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>. 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. 4
    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 .

    17311#pg8>.

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

    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.

    17311#pg9>.

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

    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.

    17311#pg10>.

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

Where the paper says it

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

17311#pg16>. This suggests that the exponent of n must depend on m. p. 4
Where the paper says it

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 reduction from Multicolored Clique implies that an f(k)No(k)-time algorithm for k-Clique remains unknown, even after the recent refutation of ETH. p. 4
Where the paper says it

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.

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

Where the paper says it

Every candidate support set gives us a low-dimensional sub-instance. Solving each sub-instance with a generic integer programming algorithm (e.

17311#pg9>. The overall success probability is at least 2/3 due to the union bound over the candidate supports and residues <ref:2611. p. 7
Where the paper says it

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.

17311#pg16>.

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

Where the paper says it

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

17311#pg16>. The final step involves binary searching for an integer solution between the LP optimum and cTx0, requiring O(log L) calls, yielding the overall success probability <ref:2611. p. 5
Where the paper says it

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.

17311#pg16>.

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

Where the paper says it

This problem is well known to be NP-hard [8], which motivates algorithms for restricted parameter regimes. arXiv:2611.

17311#pg13>. This reduction leads to the complexity (d∆)O(d)f(C, m) poly(L), which simplifies to f(C, m)nO(m) poly(L)<ref:2611. p. 0
Where the paper says it

This problem is well known to be NP-hard [8], which motivates algorithms for restricted parameter regimes. arXiv:2611.

17311#pg14>. The proof for Corollary 2 uses Corollary 3 with m=1 <ref:2611. p. 2
Where the paper says it

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

17311#pg14>.

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

Where the paper says it

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 coefficient sets are completed to intervals, ensuring row doubling below two. p. 4
Where the paper says it

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.

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

Where the paper says it

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

1 and Claude Opus 5.5 <ref:2611. p. 0
Where the paper says it

This problem is well known to be NP-hard [8], which motivates algorithms for restricted parameter regimes. arXiv:2611.

17311#pg14>. The authors take responsibility for the correctness of the work and permit reviewers to upload this submission to generative AI services <ref:2611.17311#pg14>. The authors declare no competing interests relevant to the content of this article <ref:2611. p. 0
Where the paper says it

This problem is well known to be NP-hard [8], which motivates algorithms for restricted parameter regimes. arXiv:2611.

17311#pg14>.

References

The references listed are Chen, L., Mao, Y., Zhang, G.: Integer programming: An algorithm with exponent linear in the dimension. p. 0

Where the paper says it

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

arXiv preprint (2026), https://arxiv. p. 0
Where the paper says it

This problem is well known to be NP-hard [8], which motivates algorithms for restricted parameter regimes. arXiv:2611.

p. 0
Where the paper says it

This problem is well known to be NP-hard [8], which motivates algorithms for restricted parameter regimes. arXiv:2611.

org/abs/2610. p. 0
Where the paper says it

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.

and Dadush, D. p. 0
Where the paper says it

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.

, Eisenbrand, F. p. 0
Where the paper says it

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.

, Rothvoss, T. p. 1
Where the paper says it

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]).

p. 1
Where the paper says it

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]).

: From approximate to exact integer programming. p. 0
Where the paper says it

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.

Mathematical Programming 210, 223–241 (2025) and Dadush, D. p. 0
Where the paper says it

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.

, Léonard, A. p. 0
Where the paper says it

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.

, Rohwedder, L. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

, Verschae, J. p. 0
Where the paper says it

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.

: Optimizing low dimensional functions over the integers. p. 4
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 .

In: Del Pia, A., Kaibel, V. (eds.) Proceedings of IPCO. Lecture Notes in Computer Science, vol. 13904, pp. 115–126. Springer (2023) and Eisenbrand, F. p. 0
Where the paper says it

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.

, Shmonin, G. p. 4
Where the paper says it

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∆)).

: Carathéodory bounds for integer cones. p. 1
Where the paper says it

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

Operations Research Letters 34(5), 564–568 (2006) and Eisenbrand, F. p. 0
Where the paper says it

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.

, Weismantel, R. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

: Proximity results and faster algorithms for integer programming using the Steinitz lemma. p. 1
Where the paper says it

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∥).

ACM Transactions on Algorithms 16(1), 5:1–5:14 (2020) and Hunkenschröder, C. p. 1
Where the paper says it

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.

, Pokutta, S. p. 1
Where the paper says it

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.

, Weismantel, R.: Minimizing a low-dimensional convex function over a high-dimensional cube. p. 4
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 .

SIAM Journal on Optimization 33(2), 538–552 (2023) and Jansen, K. p. 0
Where the paper says it

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.

, Rohwedder, L.: On integer programming, discrepancy, and convolution. p. 0
Where the paper says it

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.

Mathematics of Operations Research 48(3), 1481–1495 (2023) and Karp, R.M.: Reducibility among combinatorial problems. p. 0
Where the paper says it

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

In: Miller, R.E., Thatcher, J.W., (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press (1972) and Lenstra, Jr. p. 1
Where the paper says it

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]).

, H.W.: Integer programming with a fixed number of variables. p. 1
Where the paper says it

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.

Mathematics of Operations Research 8(4), 538–548 (1983) and Manurangsi, P.: Almost-polynomial ratio Almost-ETH-hardness of approximating densest k-subgraph. p. 1
Where the paper says it

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.

arXiv preprint (2026), https://arxiv.org/abs/1611. p. 0
Where the paper says it

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.

05991v3, revised October 27, 2026 and OpenAI: The exponential time hypothesis is false. p. 1
Where the paper says it

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

OpenAI Math Release preprint (2026), https://github. p. 0
Where the paper says it

17311v1 [cs. DS] 12 Nov 2026

com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper. p. 1
Where the paper says it

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

pdf and Papadimitriou, C. p. 1
Where the paper says it

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.

H.: On the complexity of integer programming. p. 0
Where the paper says it

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.

Journal of the ACM 28(4), 765–768 (1981) and Randolph, T. p. 0
Where the paper says it

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.

, Węgrzycki, K. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

: Parameterized algorithms on integer sets with small doubling: Integer programming, subset sum and k-SUM. p. 0
Where the paper says it

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.

In: Proceedings of ESA. Leibniz International Proceedings in Informatics, vol. p. 0
Where the paper says it

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.

308, pp. 96:1–96:19 and Reis, V. p. 1
Where the paper says it

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]).

, Rothvoss, T.: The subspace flatness conjecture and faster integer programming. p. 0
Where the paper says it

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.

In: Proceedings of FOCS. pp. 974–988 IEEE (2023) and Rohwedder, L. p. 0
Where the paper says it

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.

, Węgrzycki, K.: Space-efficient algorithm for integer programming with few constraints. p. 0
Where the paper says it

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.

In: Megow, N., Basu, A. (eds.) Proceedings of IPCO. Lecture Notes in Computer Science, vol. 15620, pp. 442–451 Springer (2025) and Tao, T., Vu, V.H.: Additive combinatorics, vol. p. 0
Where the paper says it

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

105 Cambridge University Press (2006). p. 0
Where the paper says it

org, kwegrzyc@mpi-inf. de 2 Saarland University, Saarbrücken, Germany 3 Harvey Mudd College, Claremont, CA, USA trandolph@g.

The paper also references Chen et al., Dadush et al. p. 0
Where the paper says it

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.

, Eisenbrand & Shmonin, Hunkenschröder et al. p. 4
Where the paper says it

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∆)).

, Jansen & Rohwedder, Karp, Lenstra Jr. p. 0
Where the paper says it

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.

, Manurangsi, OpenAI and Papadimitriou. p. 1
Where the paper says it

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.

The paper also references Randolph & Węgrzycki. p. 0
Where the paper says it

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.

The paper also references Reis & Rothvoss. p. 1
Where the paper says it

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]).

The paper also references Rohwedder & Węgrzycki again. p. 4
Where the paper says it

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∆)).

The paper also references Dadush et al. p. 0
Where the paper says it

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.

again.

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

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

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

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

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

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