Linear and integer programming: Theory and practice.

Publication date 28 August 2001

Published in Pure and Applied Mathematics, Marcel Dekker (Search for Journal in Brave)

branch-and-bound cutting-plane decomposition sensitivity duality integer programming interior path method linear network methods linear programming mathematical modelling simplex method

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Linear programming (90C05) Integer programming (90C10) Mixed integer programming (90C11) Interior-point methods (90C51) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Applications of mathematical programming (90C90)

Review text

This book is intended to be a textbook introducing graduate students of operations research, management sciences, and engineering into the field of linear and integer programming. For a review of the first ed. (New York, Dekker 1996) see Zbl 0885.90080.NEWLINENEWLINENEWLINEAs most books for beginners in this field, in Chapter 1 the basic concepts of linear programming are sensibly explained. Chapter 2 is devoted to Dantzig's simplex method and the revised simplex algorithm. Duality and optimality for linear programming are introduced in Chapter 3, while in Chapter 4 one analyses thoroughly the sensitivity of the linear model to data changes. Chapter 5 deals with the interior path method. Unavoidably, mathematics is more involved here as anywhere else in the book. In Chapter 6 one discusses classical solution techniques for integer and mixed linear problems: branch-and-bound, Gomory's cuting-plane method, Bender's decomposition. The author takes the opportunity to give also a short overview of the theory of logical variables. Chapter 7 is devoted to linear network models. Here is introduced the network simplex method and are touched upon the transportation problem, minimum cost flow, and assignement problem. Typical network algorithms (e.g. for traveling salesman problem or Dijkstra's shortest path algorithm) are mentioned in an appendix. A very short Chapter 8 aims to introduce students to computational complexity of several fundamental algorithms: simplex, interior path method, branch-and-bound. Chapter 9 alone occupies one quarter of the text. Here one finds 8 case studies of what author considers to be an art -- designing mathematical models. The steps are explained with many details, the pitfalls are discussed at length, and a number of advanced techniques for linear programming (e.g. column generation, multicriteria decision making, goal programming, and game theory) are covered to a certain extent.NEWLINENEWLINENEWLINEEach chapter ends with a variable number of exercises. For most of them there are given hints, answer or complete solution. Three appendices are devoted to linear algebra, convexity and graph theory, respectively. The book comes with a diskette containing an implementation of Karmarkar's interior point method. NEWLINENEWLINENEWLINEThe whole layout of the book is clearly designed bearing in mind the target audience. All notions are introduced by means of examples, which emphasize the practical aspects of the concepts. The theoretical level is kept as elementary as possible. Statements of the results emerge from preceding explanations, their proofs are typed in small fonts, which indicates that students with diverse intentions can skip them. NEWLINENEWLINENEWLINEThe strong point of this textbook is the emphasis on well understandable examples. The great variety of applications considered in exposition convey knowledge, lead to individual questions and insights, is extremely valuable for all teachers, and motivate the student for further investigation.

Recommendations

Cited in

(30)

This page was built for publication: Linear and integer programming: Theory and practice.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2736040)