# A Simplified Version of H. W. Lenstra's Integer Programming Algorithm and Some Applications

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-116.pdf

A very interesting algorithm has been recently suggested by H. W. Lenstra, Jr. [1] for solving integer programming problems. One part of that algorithm was further improved in [2]. The algorithm was shown to be polynomial in the length of the input, for a fixed number of variables. On the other hand the algorithm is impractical for a large number of variables and its implementation is not clear even for a small number of variables. We suggest here a few simplifications and improvements to that algorithm, making its implementation easy (though still impractical for a great number of variables). As a byproduct we show how to solve diophantine linear equations over the nonnegative integers. For a small number of variables (3 or 4) a practical and fast algorithm for solving such equation results.

BibTeX citation:

```@techreport{Paz:CSD-83-116,
Author = {Paz, A.},
Title = {A Simplified Version of H. W. Lenstra's Integer Programming Algorithm and Some Applications},
Institution = {EECS Department, University of California, Berkeley},
Year = {1983},
Month = {Aug},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6327.html},
Number = {UCB/CSD-83-116},
Abstract = {A very interesting algorithm has been recently suggested by H. W. Lenstra, Jr.  [1] for solving integer programming problems. One part of that algorithm was further improved in [2]. The algorithm was shown to be polynomial in the length of the input, for a fixed number of variables. On the other hand the algorithm is impractical for a large number of variables and its implementation is not clear even for a small number of variables. We suggest here a few simplifications and improvements to that algorithm, making its implementation easy (though still impractical for a great number of variables). As a byproduct we show how to solve diophantine linear equations over the nonnegative integers. For a small number of variables (3 or 4) a practical and fast algorithm for solving such equation results.}
}
```

EndNote citation:

```%0 Report
%A Paz, A.
%T A Simplified Version of H. W. Lenstra's Integer Programming Algorithm and Some Applications
%I EECS Department, University of California, Berkeley
%D 1983
%@ UCB/CSD-83-116
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6327.html
%F Paz:CSD-83-116
```