Personal tools
You are here: Home Publications Computational Experience with Lenstra's Algorithm
Document Actions

Liyan Gao and Yin Zhang (2002)

Computational Experience with Lenstra's Algorithm

Rice University, Department of Computational and Applied Mathematics, 6100 Main Street, Houston, TX 77005.

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 and lattice 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.

by admin last modified 2007-12-10 21:06
« September 2010 »
Su Mo Tu We Th Fr Sa
1234
567891011
12131415161718
19202122232425
2627282930
 

Powered by Plone

LACSI Collaborators include:

Rice University LANL UH UNM UIUC UNC UTK