Integer Lattices
George L. Nemhauser, Laurence A. Wolsey · 1988
This chapter discusses the basic problem which is: The Linear Equation Integer Feasibility Problem. It describes the euclidean algorithm to find gcd(a1, a2). The chapter establishes the connection between the euclidean algorithm and the continued fraction expansion of a rational number a1/a2. It introduces some basic properties of the lattice L(A) and develops a canonical representation of L(A), called the Hermite normal form, and sketch a polynomial-time algorithm for finding the Hermite normal form. The chapter also introduces an alternative representation of L(A ) called a reduced basis, which can also be obtained in polynomial time. It presents a polynomial algorithm to find gcd(a, b) where a and b are integers satisfying a > b > 0.