Theory of linear and integer programming. Repr.

*(English)*Zbl 0970.90052
Chichester: Wiley. xi, 471 p. (1998).

For a review of the original (Wiley, 1986) see Zbl 0665.90063.

This book is a comprehensive exposition of the theory of linear and integer programming and is complementing the more practically oriented books. It is intended for graduate students as an introduction and for researchers who need a thorough reference work. The author has been able to collect the necessary basic theory and the main results in the field. The historical remarks make the book valuable as a reference for readers interested in mathematical history.

The book is divided into four main parts and a brief general introduction. In the introductionary part some notations and basic principles from linear algebra, matrix theory, graph theory, and Euclidean geometry are described. In addition, a brief overview of complexity theory is given.

The first main part of the book is concerned with results from linear algebra needed for solving linear and integer programs. The emphasis is on some less well-known facts on sizes and complexity in linear algebra. Here especially the Gaussian elimination method is discussed.

The second main part consists of three chapters and deals with lattices and linear Diophantine equations. In the first chapter of this part the theoretical results based mainly on the works of Hermite and Minkowski on lattices and linear Diophantine equations are reviewed. Especially the Hermite normal form of a matrix is presented. The second chapter is concerned with the Euclidean algorithm for finding the g.c.d., which can be used to get polynomial time algorithms for solving one linear Diophantine equation. Also the extension to systems of linear Diophantine equations is described. The last chapter of this part is devoted to the continued fraction methods for approximating a real number by rational numbers of low denominator. In addition, Lovasz’s basic reduction method for lattices is discussed.

Part three, entitled “Polyhedra, linear inequalities, and linear programming” consists of nine chapters. In the first chapter of this part the fundamental results due to Farkas, Minkowski, Caratheodory and Weyl are reviewed. These results constitute the basis for working on polyhedra, linear inequalities and linear programming. The second chapter is devoted to the geometric structure of polyhedra. Topics include faces, facets, vertices, extremal rays, the characteristic cone, and the decomposition of polyhedra. The third chapter deals with polarity and with blocking and anti-blocking polyhedra. In the fourth chapter the theoretical complexity of linear inequalities and linear programming is discussed. The basic simplex method for linear programming is presented in the fifth chapter. Further methods, like the primal-dual methods, the Fourier-Motzkin elimination method and the relaxation method are treated in the sixth chapter. In the seventh chapter the Ellipsoid method and Khachiyan’s polynomial time algorithm is presented, while in the eighth chapter the Ellipsoid method is extended to allow applications to combinatorial optimization problems. The last chapter of part three briefly discusses Karmarkar’s polynomial-time algorithm, Tardos’ work on strongly polynomial algorithms and Megiddo’s linear-time algorithm for linear programming in fixed dimensions.

The last part of the book is about integer linear programming and consists also of nine chapters. In the first chapter of this part a general introduction to integer linear programming is given and some polyhedral aspects of integer linear programming are discussed. The second chapter shows that integer linear programming belongs to NP. Also some sensitivity and proximity results are given. The third chapter deals with the complexity status of integer linear programming (ILP). It is shown that ILP is NP-complete. Also Lenstra’s algorithm is described which is for each fixed number of variables a polynomial-time method. In Chapter four fundamental properties and examples of totally unimodular matrices are presented, and the fifth chapter gives a polynomial-time algorithm for recognizing total unimodularity. The sixth chapter contains some further theory related to total unimodularity. In Chapter seven the theory of total dual integrality introduced by Edmonds and Giles is discussed. We get that certain ILPs have integral optimum solutions if their duals have integral optimum solutions. In the eighth chapter the theory of cutting planes based on work of Gomory and Chvatal is presented. The last chapter surveys some further methods in integer linear programming, like branch and bound methods, Lagrangean relaxation and Benders decomposition.

An excellent bibliography is at the end of the book. However, since the book was first published in 1986 some of the newer developments in the area are missing in the bibliography as well as in the main text.

This book is a comprehensive exposition of the theory of linear and integer programming and is complementing the more practically oriented books. It is intended for graduate students as an introduction and for researchers who need a thorough reference work. The author has been able to collect the necessary basic theory and the main results in the field. The historical remarks make the book valuable as a reference for readers interested in mathematical history.

The book is divided into four main parts and a brief general introduction. In the introductionary part some notations and basic principles from linear algebra, matrix theory, graph theory, and Euclidean geometry are described. In addition, a brief overview of complexity theory is given.

The first main part of the book is concerned with results from linear algebra needed for solving linear and integer programs. The emphasis is on some less well-known facts on sizes and complexity in linear algebra. Here especially the Gaussian elimination method is discussed.

The second main part consists of three chapters and deals with lattices and linear Diophantine equations. In the first chapter of this part the theoretical results based mainly on the works of Hermite and Minkowski on lattices and linear Diophantine equations are reviewed. Especially the Hermite normal form of a matrix is presented. The second chapter is concerned with the Euclidean algorithm for finding the g.c.d., which can be used to get polynomial time algorithms for solving one linear Diophantine equation. Also the extension to systems of linear Diophantine equations is described. The last chapter of this part is devoted to the continued fraction methods for approximating a real number by rational numbers of low denominator. In addition, Lovasz’s basic reduction method for lattices is discussed.

Part three, entitled “Polyhedra, linear inequalities, and linear programming” consists of nine chapters. In the first chapter of this part the fundamental results due to Farkas, Minkowski, Caratheodory and Weyl are reviewed. These results constitute the basis for working on polyhedra, linear inequalities and linear programming. The second chapter is devoted to the geometric structure of polyhedra. Topics include faces, facets, vertices, extremal rays, the characteristic cone, and the decomposition of polyhedra. The third chapter deals with polarity and with blocking and anti-blocking polyhedra. In the fourth chapter the theoretical complexity of linear inequalities and linear programming is discussed. The basic simplex method for linear programming is presented in the fifth chapter. Further methods, like the primal-dual methods, the Fourier-Motzkin elimination method and the relaxation method are treated in the sixth chapter. In the seventh chapter the Ellipsoid method and Khachiyan’s polynomial time algorithm is presented, while in the eighth chapter the Ellipsoid method is extended to allow applications to combinatorial optimization problems. The last chapter of part three briefly discusses Karmarkar’s polynomial-time algorithm, Tardos’ work on strongly polynomial algorithms and Megiddo’s linear-time algorithm for linear programming in fixed dimensions.

The last part of the book is about integer linear programming and consists also of nine chapters. In the first chapter of this part a general introduction to integer linear programming is given and some polyhedral aspects of integer linear programming are discussed. The second chapter shows that integer linear programming belongs to NP. Also some sensitivity and proximity results are given. The third chapter deals with the complexity status of integer linear programming (ILP). It is shown that ILP is NP-complete. Also Lenstra’s algorithm is described which is for each fixed number of variables a polynomial-time method. In Chapter four fundamental properties and examples of totally unimodular matrices are presented, and the fifth chapter gives a polynomial-time algorithm for recognizing total unimodularity. The sixth chapter contains some further theory related to total unimodularity. In Chapter seven the theory of total dual integrality introduced by Edmonds and Giles is discussed. We get that certain ILPs have integral optimum solutions if their duals have integral optimum solutions. In the eighth chapter the theory of cutting planes based on work of Gomory and Chvatal is presented. The last chapter surveys some further methods in integer linear programming, like branch and bound methods, Lagrangean relaxation and Benders decomposition.

An excellent bibliography is at the end of the book. However, since the book was first published in 1986 some of the newer developments in the area are missing in the bibliography as well as in the main text.

Reviewer: Stefan Nickel (Kaiserslautern)