<p>Here are a couple of points regarding the practical implications of Lenstra-type results, and possible implementations in CPLEX, Gurobi, etc. One of the key steps in most of such algos for IP is branching on "good" or "thin" directions, i.e., hyperplanes along which the width of the polytope is not too large (polynomial in variables and size of data). But <a href="http://epubs.siam.org/action/showAbstract?page=2181&amp;volume=20&amp;issue=5&amp;journalCode=sjope8" rel="noreferrer">Mahajan and Ralphs</a> (preprint <a href="http://www.optimization-online.org/DB_HTML/2008/10/2119.html" rel="noreferrer">here</a>) showed that the problem of selecting an <i>optimal</i> disjunction is NP-complete. So, it would appear hard to create practically efficient implementations of this class of algos.</p>

<p>Most of the algos implemented in packages such as CPLEX could be classified as branch-and-cut methods. This family of techniques <i>typically</i> work well on IP instances that are feasible, and are often able to find near-optimal solutions. But the focus of Lenstra-type algos are on worst case IP instances that are infeasible to start with, and the goal is to <i>prove</i> their integer infeasibility (and they study the complexity of this task). AFAIK, there are no class of problems with practical relevance that fit this description. So, CPLEX/Gurobi folks would probably not implement Lenstra-type algos any time soon.</p>

CC BY-SA 3.0
2013-02-19T22:54:36.323Z
2013-02-19T22:54:36.323Z
kbala
<p>The current fastest algorithm is actually linear in the length of the integer linear program for every fixed value of $n$. In his PhD thesis, <a href="http://www.ii.uib.no/~daniello/papers/PhdThesis_Daniel.pdf#page=33" rel="noreferrer">Lokshtanov (2009)</a> nicely summarizes the results by Lenstra (1983), Kannan (1987), and Frank &amp; Tardos (1987) by the following theorem.</p>

<blockquote>
  <p>Integer Linear Programming can be solved using $O(n^{2.5n+o(n)} \cdot L)$
  arithmetic operations and space polynomial in $L$. Here $L$ is the
  number of bits in the input and $n$ the number of variables in the
  integer linear program.</p>
</blockquote>

<p>Thus, the problem is fixed-parameter linear parameterized by the number of variables.</p>

<p>1) Yes, Integer Linear Programming is "still" NP-complete. The running time of the theoretical result above depends only linearly on the number of constraints, so it scales nicely in the number of constraints. However I know of no actual implementation of this algorithm.</p>

<p>2) Yes, making the variables take binary values is straightforward as you observed.</p>

<p><strong>Update.</strong> The dependence on $L$ can actually be improved in the running time for Integer Linear Programming. Based on <a href="http://dx.doi.org/10.1145/201019.201036" rel="noreferrer">Clarkson (1995)</a> and <a href="http://dx.doi.org/10.1007/978-3-540-39658-1_20" rel="noreferrer">Eisenbrand (2003)</a> (see the comments below) one can obtain an algorithm with running time $$O(2^nnm + 8^n n \sqrt{m \log m} \log m + n^{2.5n+o(n)}s\log m)$$
where $m$ is the number of constraints and $s$ is the maximum number of bits required to encode a constraint or the objective function.</p>

CC BY-SA 3.0
2013-02-18T19:02:38.843Z
Ah, thanks for the term "fixed-parameter linear". That's what Lenstra's paper is about. See also: https://en.wikipedia.org/wiki/Parameterized_complexity
Bernhard Kausler
CC BY-SA 3.0
2013-02-18T20:17:00.037Z
just an obvious observation: for $n$ binary variables the bruteforce algorithms takes $O(n2^n m)$ time, so that case is trivial.
Sasho Nikolov
CC BY-SA 3.0
2013-02-18T23:12:15.397Z
For the optimization version of ILP: if it takes $T(n,m,s)$ time to solve a problem with rational coefficients and with $n$ variables, $m$ constraints, and $s$ bits per constraint, then ILP can be done in $O(2^n m + (\log m)T(n, f(n),s)$ operations on $O(s)$-bit rationals, where $f(n)$ is (I think) at worst $n^{O(n)}$; this is based on Eisenbrand's paper: http://www2.math.uni-paderborn.de/fileadmin/Mathematik/AG-Eisenbrand/publications/ip_llncs.pdf .
Ken Clarkson
CC BY-SA 3.0
2013-02-18T23:19:50.707Z
...sorry, make that $O(2^n n m+(\log m)T(n,f(n),s))$ expected (Las Vegas) time.
Ken Clarkson
CC BY-SA 3.0
2013-02-19T03:26:04.930Z
This doesn't change the basic facts of your answer, but another relevant reference is K. L. Clarkson. Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42(2):488–499, 1995, doi:10.1145/201019.201036.
David Eppstein
CC BY-SA 3.0
2013-02-19T10:31:55.020Z
@KenClarkson and David: Thank you for the additional references. Does anybody know the dependence on $n$ of these algorithms? Is it the same as for the result I mentioned, $n^{2.5 n + o(n)}$?
Serge Gaspers
CC BY-SA 3.0
2013-02-20T18:37:04.700Z
The bound on the expected number of arithmetic operations from Clarkson's paper is $O(2^nnm+8^nn\sqrt{m\log^2 m}+n^{O(n)}L\log m)$. He doesn't give the constant in the last term's exponent. The emphasis is less on improving the $n^{O(n)}$ term and more on reducing the dependence on $m$.
David Eppstein
CC BY-SA 3.0
2013-02-20T20:27:18.907Z
My paper is buggy for ILP: in base cases for "small" $m$, I referred to ILP algorithms for feasibility, when I should've referred to algorithms solving optimization. Eisenbrand's paper notes this and gives results for the base case; however, I couldn't figure out the exact dependence on $n$ in his paper. You could just plug the $O(n^{2.5n+o(n)} L)$ result into the $T(n,f(n),s)$ part of what I claimed, where $f(n)=4^n$, and so $L=4^n s$. (Sorry, I was confused about what $f(n)$ should be.) The upshot, ignoring that middle term, is something like $O(2^nnm+n^{2.5n+o(n)}(\log m) s)$ operations.
Ken Clarkson
CC BY-SA 4.0
2023-07-11T00:22:41.533Z
@SergeGaspers What is the size of word in each operation? Is it $O(log n)$?
Turbo
CC BY-SA 4.0
2023-07-11T00:41:01.907Z
I mean $O(log s)$?
Turbo
CC BY-SA 4.0
2024-05-20T11:57:33.430Z
Reis and Rothvoss (https://arxiv.org/abs/2303.14605) present a faster ILP algorithm.
Erel Segal-Halevi
CC BY-SA 3.0
2013-02-18T13:50:59.873Z
2013-02-21T06:23:02.073Z
2013-02-21T06:23:02.073Z
Serge Gaspers
<p>The famous 1983 paper by H. Lenstra <em><a href="http://www.jstor.org/stable/3689168">Integer Programming With A Fixed Number Of Variables</a></em> states that integer programs with a fixed number of variables are solvable in time polynomial in the length of the data.</p>

<p>I interpret that as follows.</p>

<ol>
<li>Integer programming in general still is NP-complete but if my typical problem size at hand (say about 10.000 variables, an arbitrary number of constraints) is feasible in practice then I could construct an algorithm that scales polynomially in the number of constraints but not in the number of variables and constraints.</li>
<li>The result is also applicable for binary programming since I can force any integer to 0-1 by adding an appropriate constraint.</li>
</ol>

<p>Is my interpretation correct?</p>

<p>Does this result have any practical implications? That is, is there an implementation available or is it used in popular solvers like CPLEX, Gurobi, or Mosek?</p>

<p>Some quotes from the paper:</p>

<blockquote>
  <p>This length may, for our purposes, be defined to be n · m · log(a +
  2), where a denotes the maximum of the absolute values of the
  coefficients of A and b. Indeed, no such polynomial algorithm is
  likely to exist, since the problem in question is NP-complete</p>
  
  <p>[...]</p>
  
  <p>It was conjectured [5], [10] that for any fixed value of n there
  exists a polynomial algorithm for the solution of the integer linear
  programming problem. In the present paper we prove this conjecture by
  exhibiting such an algorithm. The degree of the polynomial by which
  the running time of our algorithm can be bounded is an exponential
  function of n.</p>
</blockquote>

CC BY-SA 3.0
2013-02-18T15:15:39.240Z
*"I could construct an algorithm that scales polynomially in the number of **constraints or variables** but not in the number of variables and constraints."* Interesting point/question -- so far we have seen this to be true for constraints (holding the number of variables fixed), but maybe it would be interesting to ask if it could true for variables (holding the number of constraints fixed) as well? Intuitively it feels like it should not be true, else IP would be polytime in general, but I'm not sure.
usul
CC BY-SA 3.0
2013-02-18T18:55:59.237Z
In section 4 of the paper Lenstra states that "the integer linear programming problem with a fixed value of m is polynomially solvable." (m is the number of contraints) This follows as a corollary of the main result. This section is not clear to me. On a second thought maybe he assumes fixed n AND m; meaning it is polynomial in "a" (the maximum of the absolute values of the coefficients of A and b). (I removed the "or variables" part from my question above as a consequence).
Bernhard Kausler
CC BY-SA 3.0
2013-02-18T23:15:02.983Z
@usul: it is true and it does not imply that IP is polytime. it just means there is one algorithm that takes exponential time in $n$ and polynomial in $m$ and another that takes exponential time in $m$ and polynomial in $n$
Sasho Nikolov
<co.combinatorics><linear-programming><integer-programming>
Integer programming with a fixed number of variables
Bernhard Kausler
# Integer programming with a fixed number of variables

(Asked by: username_0 on 2013-02-18)

The famous 1983 paper by H. Lenstra *[Integer Programming With A Fixed Number Of Variables](http://www.jstor.org/stable/3689168)* states that integer programs with a fixed number of variables are solvable in time polynomial in the length of the data.

I interpret that as follows.

1. Integer programming in general still is NP-complete but if my typical problem size at hand (say about 10.000 variables, an arbitrary number of constraints) is feasible in practice then I could construct an algorithm that scales polynomially in the number of constraints but not in the number of variables and constraints.
2. The result is also applicable for binary programming since I can force any integer to 0-1 by adding an appropriate constraint.

Is my interpretation correct?

Does this result have any practical implications? That is, is there an implementation available or is it used in popular solvers like CPLEX, Gurobi, or Mosek?

Some quotes from the paper:

> This length may, for our purposes, be defined to be n · m · log(a +
> 2), where a denotes the maximum of the absolute values of the
> coefficients of A and b. Indeed, no such polynomial algorithm is
> likely to exist, since the problem in question is NP-complete
>
> [...]
>
> It was conjectured [5], [10] that for any fixed value of n there
> exists a polynomial algorithm for the solution of the integer linear
> programming problem. In the present paper we prove this conjecture by
> exhibiting such an algorithm. The degree of the polynomial by which
> the running time of our algorithm can be bounded is an exponential
> function of n.

**Tags:** co.combinatorics, linear-programming, integer-programming

> **Comments:**
> **username_1**: *"I could construct an algorithm that scales polynomially in the number of **constraints or variables** but not in the number of variables and constraints."* Interesting point/question -- so far we have seen this to be true for constraints (holding the number of variables fixed), but maybe it would be interesting to ask if it could true for variables (holding the number of constraints fixed) as well? Intuitively it feels like it should not be true, else IP would be polytime in general, but I'm not sure.  
> **username_0**: In section 4 of the paper Lenstra states that "the integer linear programming problem with a fixed value of m is polynomially solvable." (m is the number of contraints) This follows as a corollary of the main result. This section is not clear to me. On a second thought maybe he assumes fixed n AND m; meaning it is polynomial in "a" (the maximum of the absolute values of the coefficients of A and b). (I removed the "or variables" part from my question above as a consequence).  
> **username_2**: @username_1: it is true and it does not imply that IP is polytime. it just means there is one algorithm that takes exponential time in $n$ and polynomial in $m$ and another that takes exponential time in $m$ and polynomial in $n$  

---

## 2 answers

### Answer by username_4 on 2013-02-18. Score: 24 | Accepted answer

The current fastest algorithm is actually linear in the length of the integer linear program for every fixed value of $n$. In his PhD thesis, [Lokshtanov (2009)](http://www.ii.uib.no/~daniello/papers/PhdThesis_Daniel.pdf#page=33) nicely summarizes the results by Lenstra (1983), Kannan (1987), and Frank & Tardos (1987) by the following theorem.

> Integer Linear Programming can be solved using $O(n^{2.5n+o(n)} \cdot L)$
> arithmetic operations and space polynomial in $L$. Here $L$ is the
> number of bits in the input and $n$ the number of variables in the
> integer linear program.

Thus, the problem is fixed-parameter linear parameterized by the number of variables.

1) Yes, Integer Linear Programming is "still" NP-complete. The running time of the theoretical result above depends only linearly on the number of constraints, so it scales nicely in the number of constraints. However I know of no actual implementation of this algorithm.

2) Yes, making the variables take binary values is straightforward as you observed.

**Update.** The dependence on $L$ can actually be improved in the running time for Integer Linear Programming. Based on [Clarkson (1995)](http://dx.doi.org/10.1145/201019.201036) and [Eisenbrand (2003)](http://dx.doi.org/10.1007/978-3-540-39658-1_20) (see the comments below) one can obtain an algorithm with running time $$O(2^nnm + 8^n n \sqrt{m \log m} \log m + n^{2.5n+o(n)}s\log m)$$
where $m$ is the number of constraints and $s$ is the maximum number of bits required to encode a constraint or the objective function.

> **Comments:**
> **username_0**: Ah, thanks for the term "fixed-parameter linear". That's what Lenstra's paper is about. See also: https://en.wikipedia.org/wiki/Parameterized_complexity  
> **username_2**: just an obvious observation: for $n$ binary variables the bruteforce algorithms takes $O(n2^n m)$ time, so that case is trivial.  
> **username_5**: For the optimization version of ILP: if it takes $T(n,m,s)$ time to solve a problem with rational coefficients and with $n$ variables, $m$ constraints, and $s$ bits per constraint, then ILP can be done in $O(2^n m + (\log m)T(n, f(n),s)$ operations on $O(s)$-bit rationals, where $f(n)$ is (I think) at worst $n^{O(n)}$; this is based on Eisenbrand's paper: http://www2.math.uni-paderborn.de/fileadmin/Mathematik/AG-Eisenbrand/publications/ip_llncs.pdf .  
> **username_5**: ...sorry, make that $O(2^n n m+(\log m)T(n,f(n),s))$ expected (Las Vegas) time.  
> **username_6**: This doesn't change the basic facts of your answer, but another relevant reference is K. L. Clarkson. Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42(2):488–499, 1995, doi:10.1145/201019.201036.  
> **username_4**: @KenClarkson and David: Thank you for the additional references. Does anybody know the dependence on $n$ of these algorithms? Is it the same as for the result I mentioned, $n^{2.5 n + o(n)}$?  
> **username_6**: The bound on the expected number of arithmetic operations from Clarkson's paper is $O(2^nnm+8^nn\sqrt{m\log^2 m}+n^{O(n)}L\log m)$. He doesn't give the constant in the last term's exponent. The emphasis is less on improving the $n^{O(n)}$ term and more on reducing the dependence on $m$.  
> **username_5**: My paper is buggy for ILP: in base cases for "small" $m$, I referred to ILP algorithms for feasibility, when I should've referred to algorithms solving optimization. Eisenbrand's paper notes this and gives results for the base case; however, I couldn't figure out the exact dependence on $n$ in his paper. You could just plug the $O(n^{2.5n+o(n)} L)$ result into the $T(n,f(n),s)$ part of what I claimed, where $f(n)=4^n$, and so $L=4^n s$. (Sorry, I was confused about what $f(n)$ should be.) The upshot, ignoring that middle term, is something like $O(2^nnm+n^{2.5n+o(n)}(\log m) s)$ operations.  
> **username_7**: @SergeGaspers What is the size of word in each operation? Is it $O(log n)$?  
> **username_7**: I mean $O(log s)$?  
> **username_8**: Reis and Rothvoss (https://arxiv.org/abs/2303.14605) present a faster ILP algorithm.  

---

### Answer by username_3 on 2013-02-19. Score: 6

Here are a couple of points regarding the practical implications of Lenstra-type results, and possible implementations in CPLEX, Gurobi, etc. One of the key steps in most of such algos for IP is branching on "good" or "thin" directions, i.e., hyperplanes along which the width of the polytope is not too large (polynomial in variables and size of data). But [Mahajan and Ralphs](http://epubs.siam.org/action/showAbstract?page=2181&volume=20&issue=5&journalCode=sjope8) (preprint [here](http://www.optimization-online.org/DB_HTML/2008/10/2119.html)) showed that the problem of selecting an *optimal* disjunction is NP-complete. So, it would appear hard to create practically efficient implementations of this class of algos.

Most of the algos implemented in packages such as CPLEX could be classified as branch-and-cut methods. This family of techniques *typically* work well on IP instances that are feasible, and are often able to find near-optimal solutions. But the focus of Lenstra-type algos are on worst case IP instances that are infeasible to start with, and the goal is to *prove* their integer infeasibility (and they study the complexity of this task). AFAIK, there are no class of problems with practical relevance that fit this description. So, CPLEX/Gurobi folks would probably not implement Lenstra-type algos any time soon.


---

