1983 · 425 citations · 5 references
Mathematical ProgrammingComputational Complexity TheoryEngineeringComputational ComplexityAlgebraic ComplexityP Versus Np ProblemGomory-chvátal TheoryDiscrete MathematicsCoding TheoryCombinatorial OptimizationInteger Programming ProblemInteger OptimizationComputer ScienceProblem ReductionInteger ProgrammingTheory Of ComputingRelated Lattice ProblemsLattice (Order)Mixed Integer OptimizationTime ComplexityEnumeration Technique
Integer programming seeks an integer vector satisfying linear inequalities; Lenstra’s 1981 algorithm proved polynomial‑time solvability for fixed dimension but with high complexity, prompting the need for faster methods. The authors present a new algorithm that achieves a running time of O(n^9 n L log L) to accelerate integer programming. The algorithm reduces n‑dimensional problems to polynomially many (n−1)-dimensional ones by computing a more orthogonal lattice basis than Lenstra’s and then applying enumeration to solve the reduced problems.
The integer programming problem is: Given m×n and m×l matrices A and b respectively of integers, find whether, there exists an all integer n×l vector x satisfying the m inequalities A×≤b. In settling an important open problem, Lenstra (1981) showed in an elegant way that when n, the number of dimensions is fixed, there is a polynomial-time algorithm to solve this problem. His algorithm achieves a running-time of 0(cn3•p(length of data)) where p is some polynomial and c a constant independent of n. Since such an algorithm has several important applications - cryptography (Shamir (1982)), diophantine approximations (Lagarias (1982)), coding theory (Conway and Sloane (1982), etc. it is important to improve the running time. We present an algorithm here that has a running time of 0(n9nL log L) where L is the length of the input. Whereas Lenstra's algorithm in the worst case reduces an n-dimensional problem to cn2−(n−) dimensional problems, our algorithm effectively reduces an n-dimensional problem to at most polynomially many (n−1) dimensional problems, thus achieving our time bound. The algorithm we propose, first finds a “more orthogonal” basis for a lattice (see the next section for the definition of a lattice) than those of Lenstra (1981) and Lenstra, Lenstra and Lovasz (1982), but in time 0(ndn poly (length of input)). It then uses an enumeration technique to solve integer programming and related problems.
5