Theory of linear and integer programming.

*(English)*Zbl 0665.90063
Wiley-Interscience Series in Discrete Mathematics. A Wiley-Interscience Publication. Chichester: John Wiley & Sons Ltd. XII, 471 p.; $ 71.95 (1986).

Many important books exist on linear and integer linear programming. Consequently a prospective reader would like to know what is special about the book under review. The author says: “The emphasis of this book is on the more theoretical aspects, and it aims at complementing the more practically oriented books.” This is a suitable characterization, but the reviewer thinks we have at hand a more comprehensive publication. The author has written the book of linear and integer programming. A reference work has now appeared.

If we have a question in the field of linear and integer programming, this book will give an answer or will show us the way to an answer. The author describes new connections between several mathematical questions, proves many interesting results, mentions lots of surprising historical facts, and leads us through the theory and algorithms of linear and integer linear programming.

To detail the general statements, several subjects treated in the book are as follows: problems, algorithms, complexity; theory of lattices; theory and algorithms for linear Diophantine equations; fundamental concepts and results on polyhedra, linear inequalities, and linear programming; blocking and antiblocking polyhedra; the simplex method and its complexity (with Borgwardt’s analysis of the average running time of the simplex method); ellipsoid method; further polynomial results in linear programming (e.g. Karmarkar’s and Megiddo’s methods); estimates in integer linear programming (i.l.p.); complexity of i.l.p. (including Lenstra’s algorithm for i.l.p. problems in fixed dimension); totally unimodular matrices; integral polyhedra and total dual integrality; cutting planes (with results on the number of cutting planes and the length of cutting plane proofs); further methods in i.l.p. (e.g. branch and bound, Lagrangian relaxation, Benders’ decomposition).

This encyclopaedic book is distinguished by its high scientific level and its concentrated manner. The reviewer is thoroughly convinced that every reader will be fascinated and stimulated by this publication. Intensive use of the book will be the thanks to the author. Theory of linear and integer programming is a classic work in optimization.

If we have a question in the field of linear and integer programming, this book will give an answer or will show us the way to an answer. The author describes new connections between several mathematical questions, proves many interesting results, mentions lots of surprising historical facts, and leads us through the theory and algorithms of linear and integer linear programming.

To detail the general statements, several subjects treated in the book are as follows: problems, algorithms, complexity; theory of lattices; theory and algorithms for linear Diophantine equations; fundamental concepts and results on polyhedra, linear inequalities, and linear programming; blocking and antiblocking polyhedra; the simplex method and its complexity (with Borgwardt’s analysis of the average running time of the simplex method); ellipsoid method; further polynomial results in linear programming (e.g. Karmarkar’s and Megiddo’s methods); estimates in integer linear programming (i.l.p.); complexity of i.l.p. (including Lenstra’s algorithm for i.l.p. problems in fixed dimension); totally unimodular matrices; integral polyhedra and total dual integrality; cutting planes (with results on the number of cutting planes and the length of cutting plane proofs); further methods in i.l.p. (e.g. branch and bound, Lagrangian relaxation, Benders’ decomposition).

This encyclopaedic book is distinguished by its high scientific level and its concentrated manner. The reviewer is thoroughly convinced that every reader will be fascinated and stimulated by this publication. Intensive use of the book will be the thanks to the author. Theory of linear and integer programming is a classic work in optimization.

Reviewer: Jürgen Köhler (MR 88m:90090)

##### MSC:

90C10 | Integer programming |

90C05 | Linear programming |

90-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming |