Ellipsoidal approximation to polytopes and computational study of Lenstra's algorithm.

摘要

General 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 general integer programs while 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 has made it difficult to study the computational properties of Lenstra's algorithm.;To bridge the gap between theory and computational practice for Lenstra's algorithm, we study both the ellipsoidal approximation to polytopes and computational properties of Lenstra's algorithm in this thesis. We have developed a reliable and efficient algorithm for computing the maximum volume ellipsoid inscribing a given polytope. This algorithm effectively exploits the problem-specific structures and utilizes a primal-dual type, interior point method. We show that this algorithm has a sound theoretical foundation, and demonstrate that it performs considerably better than a number of other algorithms through extensive numerical experiments.;Using our ellipsoidal approximation algorithm as a subroutine, we have implemented a version of Lenstra's algorithm for general integer programming feasibility problems. At each node, the method uses ellipsoidal approximation and lattice basis reduction to find a "thin" direction of the polytope, and branches on hyperplanes, rather than on variables as in the traditional branch-and-bound method. In this procedure, it is guaranteed that the number of branches at each node is bounded and small. Our numerical results on small- to medium-sized test instances suggest that Lenstra's algorithm examine much fewer nodes than the traditional branch-and-bound method. However, there is a tradeoff between many nodes and fast reoptimization as in the traditional branch-and-bound method and fewer nodes but more time-consuming decisions on branching as in Lenstra's algorithm. Currently, the main bottle-neck in the performance of the algorithm lies at the step of lattice basis reduction. If this step is sufficiently improved, then Lenstra's algorithm, when combined with other techniques such as cutting planes, promises to be efficient for certain classes of difficult problems.