<p>The original algorithm of Lenstra (from 1983) has not been implemented AFAIK. Certainly, no open-source code is known to be available. </p>

<p><a href="http://pubsonline.informs.org/doi/abs/10.1287/moor.17.3.751" rel="noreferrer">Lovasz and Scarf</a> proposed (in 1992) a generalized basis reduction algo that also solves IP in fixed dimensions, but avoids the ellipsoidal approximations required by Lenstra's algorithm. An implementation of this algo was reported in 1993 by <a href="http://pubsonline.informs.org/doi/pdf/10.1287/ijoc.5.2.206" rel="noreferrer">Cook, Rutherford, Scarf, and Shallcross</a> (this paper is available in <a href="https://www.researchgate.net/publication/4776890_An_Implementation_of_the_Generalized_Basis_Reduction_Algorithm_for_Integer_Programming" rel="noreferrer">ResearchGate</a>).</p>

<p>One of the key steps in Lenstra's algorithm uses basis reduction (BR) to locate "thin directions" for the polytope. Branching on such a direction produces only a small (i.e., polynomial number) of subproblems. In a series of papers, Aardal and coauthors essentially applied this BR step to help solve (using standard MIP solvers) otherwise hard-to-solve IP instances (see, e.g., <a href="http://pubsonline.informs.org/doi/abs/10.1287/moor.25.3.427.12219" rel="noreferrer">this paper</a> and <a href="http://pubsonline.informs.org/doi/abs/10.1287/moor.1040.0099" rel="noreferrer">this paper</a>). <a href="http://www.sciencedirect.com/science/article/pii/S1572528609000048" rel="noreferrer">We</a> (also see <a href="https://arxiv.org/abs/0807.1317" rel="noreferrer">arXiv</a>) have studied a similar, but arguably simpler and more general, approach (full disclosure: self-citation here!) to solve IP feasibility problems: apply BR to the constraint matrix $A$ of the IP feasibility problem (of the form $\{\mathbf{l} \leq A \mathbf{x} \leq \mathbf{u}, \mathbf{x} \in \mathbb{Z}^n\}$), and use standard techniques to solve the resulting reformulated IP feasibility problem. The BR could be performed using standard software tools such as <a href="http://www.shoup.net/ntl/" rel="noreferrer">NTL</a>.</p>

CC BY-SA 3.0
2017-10-02T03:08:22.247Z
would you also know https://mathoverflow.net/questions/282456/under-what-conditions-does-an-integer-programming-problem-run-in-polynomial-time?
Turbo
CC BY-SA 3.0
2017-10-13T18:14:12.220Z
I must mention that while Lenstra-type algos might not be implemented in their original form, Barvinok's lattice-point counting algo (improvements of the same) has indeed been implemented - see https://www.math.ucdavis.edu/~latte/
kbala
CC BY-SA 3.0
2018-02-12T08:45:26.947Z
this also looks like sufficient correct? if we know how to count can't we use binary search and is there such a binary search algorithm?
Turbo
CC BY-SA 3.0
2018-03-17T23:17:37.643Z
what is the complexity of Lovasz/Scarf. Is there any open source software available for any implementation of fixed fimension poly time integer programming algorithm?
Turbo
CC BY-SA 3.0
2017-09-27T06:48:52.330Z
2017-09-27T06:48:52.330Z
kbala
<p>Have any fixed parameter integer programming algorithms described in  <a href="https://cstheory.stackexchange.com/questions/16530/integer-programming-with-a-fixed-number-of-variables">Integer programming with a fixed number of variables</a> been implemented? Is there a reference code that researchers can use? </p>

<ds.algorithms><reference-request><soft-question><integer-programming><software>
Have fixed parameter integer program algorithms ever been implemented for research use?
Turbo
# Have fixed parameter integer program algorithms ever been implemented for research use?

(Asked by: username_0 on 2017-09-20)

Have any fixed parameter integer programming algorithms described in [Integer programming with a fixed number of variables](https://cstheory.stackexchange.com/questions/16530/integer-programming-with-a-fixed-number-of-variables) been implemented? Is there a reference code that researchers can use?

**Tags:** ds.algorithms, reference-request, soft-question, integer-programming, software


---

## 1 answers

### Answer by username_1 on 2017-09-27. Score: 5

The original algorithm of Lenstra (from 1983) has not been implemented AFAIK. Certainly, no open-source code is known to be available.

[Lovasz and Scarf](http://pubsonline.informs.org/doi/abs/10.1287/moor.17.3.751) proposed (in 1992) a generalized basis reduction algo that also solves IP in fixed dimensions, but avoids the ellipsoidal approximations required by Lenstra's algorithm. An implementation of this algo was reported in 1993 by [Cook, Rutherford, Scarf, and Shallcross](http://pubsonline.informs.org/doi/pdf/10.1287/ijoc.5.2.206) (this paper is available in [ResearchGate](https://www.researchgate.net/publication/4776890_An_Implementation_of_the_Generalized_Basis_Reduction_Algorithm_for_Integer_Programming)).

One of the key steps in Lenstra's algorithm uses basis reduction (BR) to locate "thin directions" for the polytope. Branching on such a direction produces only a small (i.e., polynomial number) of subproblems. In a series of papers, Aardal and coauthors essentially applied this BR step to help solve (using standard MIP solvers) otherwise hard-to-solve IP instances (see, e.g., [this paper](http://pubsonline.informs.org/doi/abs/10.1287/moor.25.3.427.12219) and [this paper](http://pubsonline.informs.org/doi/abs/10.1287/moor.1040.0099)). [We](http://www.sciencedirect.com/science/article/pii/S1572528609000048) (also see [arXiv](https://arxiv.org/abs/0807.1317)) have studied a similar, but arguably simpler and more general, approach (full disclosure: self-citation here!) to solve IP feasibility problems: apply BR to the constraint matrix $A$ of the IP feasibility problem (of the form $\{\mathbf{l} \leq A \mathbf{x} \leq \mathbf{u}, \mathbf{x} \in \mathbb{Z}^n\}$), and use standard techniques to solve the resulting reformulated IP feasibility problem. The BR could be performed using standard software tools such as [NTL](http://www.shoup.net/ntl/).

> **Comments:**
> **username_0**: would you also know https://mathoverflow.net/questions/282456/under-what-conditions-does-an-integer-programming-problem-run-in-polynomial-time?  
> **username_1**: I must mention that while Lenstra-type algos might not be implemented in their original form, Barvinok's lattice-point counting algo (improvements of the same) has indeed been implemented - see https://www.math.ucdavis.edu/~latte/  
> **username_0**: this also looks like sufficient correct? if we know how to count can't we use binary search and is there such a binary search algorithm?  
> **username_0**: what is the complexity of Lovasz/Scarf. Is there any open source software available for any implementation of fixed fimension poly time integer programming algorithm?  

---

