Discrete optimization algorithms with Pascal programs. (English) Zbl 0574.90057

Englewood Cliffs, New Jersey: Prentice-Hall, Inc. XII, 542 p. $ 60.75 (1983).
This book covers a great variety of standard problems in the area of integer and combinatorial programming. The authors’ objective was to present a book which can be used in two ways: as a supporting textbook in discrete optimization courses and as a software handbook containing 26 Pascal-programs for academic users and industrial practitioners.
The book is partitioned into four parts: Chapter 1 treats general linear programming, integer linear programming, 0-1 programming and the classical transportation problem. - In chapter 2 several exact and approximate approaches to the knapsack problem and two methods for the set-partitioning-problem are discussed. - Chapter 3 deals with optimization problems on networks presenting algorithms for the shortest path problem, the minimum spanning tree problem, the maximum flow problem, the minimum cost flow problem, the maximum-cardinality matching problem and the traveling salesman problem (exact and approximate algorithms). - Chapter 4 gives algorithms for the graph coloring problem and comprises the large field of scheduling problems. Every subchapter devoted to a certain problem is concluded by a list of problems and an annotated bibliography which can serve as the starting point for further reading. Thus the book is wellsuited for use as the basic textbook in a first computer-oriented course on discrete or combinatorial optimization.
Reviewer: U.Derigs


90C10 Integer programming
90B10 Deterministic network models in operations research
90B35 Deterministic scheduling theory in operations research
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
65K05 Numerical mathematical programming methods
90C35 Programming involving graphs or networks
68R10 Graph theory (including graph drawing) in computer science
90C05 Linear programming
90C09 Boolean programming
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
05C35 Extremal problems in graph theory