Computational Experience with Lenstra's Algorithm

Integer programming is an important mathematical approach for many decision-making problems. In this field, a major theoretical breakthrough came in 1983 when H. W. Lenstra, Jr. proposed a polynomial-time algorithm for a general integer programming feasibility problem where the number of variables is fixed. Two key ingredients of Lenstra's algorithm are ellipsoidal approximation of polytopes andlattice basis reduction. However, the lack of practically efficient algorithms and software for the ellipsoidal approximation of polytopes had made it difficult to study the computational properties of Lenstra's algorithm. In this paper, using a newly developed ellipsoidal approximation algorithm as a subroutine, we have implemented a version of Lenstra's algorithm for the general integer programming feasibility problem. Our numerical results on small- to medium-sized test instances indicate that Lenstra's algorithm often examines far fewer nodes than the traditional branch-and-bound approach. Currently, the main bottle-neck in the performance of the algorithm lies in the step of lattice basis reduction