In this survey we address three of the principal algebraic approaches to integer programming. After introducing lattices and basis reduction, we first survey their use in integer programming, presenting among others Lenstra's algorithm that is polynomial in fixed dimension, and the solution of diophanine equations using basis reduction. The second topic concerns augmentation algorithms and test sets, including the role played by Hilbert and Gröbner bases in the development of a primal approach to solve a family of problems for all right-hand sides. Thirdly we survey the group approach of Gomory, showing the importance of subadditivity in integer programming and the generation of valid inequalities, as well the relation to the parametric problem cited above of solving for all right-hand sides.

The system Bx b is said to describe P , and each hyperplane fx 2 IR : B i x = big is called a cutting plane. One of the central questions in polyhedral combinatorics is to nd the cutting planes that describe P . This question is the subject of this chapter. We start with a section on books and collections of survey articles that treat polyhedral combinatorics in detail. x2 on integer programming by linear programming discusses general schemes by which all cutting planes are generated. We discuss the separation problem, the concepts of total unimodularity and total dual integrality, and give a reference to the computational complexity of deriving an explicit description of conv(X). For NP-hard problems, such as the knapsack, covering, packing, partitioning or mixed integer ow problems, one cannot expect to derive an explicit description of P . Then it is of interest to describe the associated polyhedra partially. Some articles on this issue are listed in x3. Our policy in selecting references has been as follows. We have chosen books that give a modern account of polyhedral combinatorics. The purpose of x2 is to review the most important theoretical results. When selecting problems for x3 we chose basic combinatorial structures that form substructures of a large collection of combinatorial optimization problems. Some prominent problems of this type are treated in separate chapters of this book, such as the traveling salesman problem, and the maximum cut problem, and are therefore not included here.