Linear programming and network flows. 4th ed. (English) Zbl 1200.90002

Bazaraa, Mokhtar S.; Jarvis, John J.; Sherali, Hanif D.

Hoboken, NJ: John Wiley & Sons (ISBN 978-0-470-46272-0/hbk). xiv, 748 p. (2010).

This book addresses linear programming and network flows. Both the general theory and characteristics of these optimization problems, as well as effective solution algorithms, are presented. Computationally effective interior point algorithms in the class of Karmarkar’s projective interior point algorithm, including affine scaling methods, primal-dual path-following procedures, and predictor-corrector techniques, are also discussed. The book can be used both as reference and as textbook for advanced undergraduate students and first-year graduate students in the fields of industrial engineering, management, operation research, computer science, mathematics and other engineering disciplines that deal with the subjects of linear programming and network flows. Following the introductory first chapter, the second chapter presents basic results on linear algebra and convex analysis.
The remainder of the book is organized into two parts: linear programming and networks flows. The linear programming part consists of Chapters 3 to 8. In Chapter 3 the simplex method is developed in detail, and in Chapter 4 the initiation of the simplex method and the problem of degeneracy, cycling and stalling are discussed. Chapter 5 deals with some specializations of the simplex method and optimality conditions. In Chapter 6 the duality and sensitivity analysis is discussed. Chapter 7 introduces the decomposition principle and large-scale optimization. Chapter 8 discusses the complexity of the simplex algorithm and presents polynomial-time algorithms. The part on network flows consists of Chapters 9 to 12. In Chapter 9 the authors study the principal characteristics of network structured linear programming problems and discuss the specialization of the simplex algorithm to solve these problems. Chapter 10 deals with transportation and assignment problems. Chapter 11 presents the out-of-kilter algorithm. Chapter 12 covers special topics of the maximal flow problem, the shortest path problem, the multicommodity minimal-cost flow problem, and a network synthesis or design problem.

Reviewer: Paulo Mbunga (Kiel)

MSC:

90-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90C05	Linear programming
90B10	Deterministic network models in operations research

Keywords:

linear programming; network flows; simplex method; duality; sensitivity analysis; decomposition principle; polynomial-time algorithms; interior point methods; out-of-kilter algorithm; transportation problems; assignment problems

Citations:

Zbl 1061.90085; Zbl 0722.90042; Zbl 1060.90688