Sakarovitch, Michel Optimisation combinatoire. Méthodes mathématiques et algorithmiques. I: Graphes et programmation linéaire. II: Programmation discrète. (French) Zbl 0652.90085 Enseignement des Sciences, 31 & 32. Paris: Hermann. XIII, 250 p. & XIII, 270 p.; FF 164.00 chacun (1984). These two volumes constitute an excellent “vue d’ensemble” of the basic concepts and the most important tools and models of combinatorial optimization. The first volume is entirely dedicated to the introduction of what constitutes the fundamental tools of combinatorial optimization in the view of the author. The section on graphs presents the basic notions and certain algorithmic aspects of trees, network flows, Euler and Hamilton cycles, matchings and coverings, together with a special chapter on the data representation of graphs and trees. The section on linear programming follows the by now classical approach to duality theory, simplex method and variants, and the transportation problem. It is in the second volume that the more specific models and methods of combinatorial programming are developed. There are chapters on shortest paths and network scheduling, maximum flow, minimal cost flow and the transportation problem, branch-and-bound methods and Lagrangian relaxation, cutting planes and polyhedral methods, dynamic programming and heuristics. In order to be self-contained this volume contains a recapitulation of the basic definitions and results of the first volume. The chapter on algorithmic complexity, written in a more or less informal style but with great didactic skill, serves as a good introduction to the specificity of discrete optimization problems. Most concepts are illustrated by examples. The algorithms are given in a structured informal, Algol-like language, with a distinct and well- justified preference for clarity over performance. Contrary to a remark in the preface, this is not a reference manual for workers in the field but a fairly comprehensive textbook for a two- semester graduate course. The numerous exercises of different degrees of difficulty will be equally helpful for students and teachers. Cited in 12 Documents MSC: 90C27 Combinatorial optimization 90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming 90C35 Programming involving graphs or networks 90B10 Deterministic network models in operations research 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) 90C39 Dynamic programming 90C10 Integer programming 05C05 Trees 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 90C05 Linear programming 90B35 Deterministic scheduling theory in operations research 68Q25 Analysis of algorithms and problem complexity Keywords:graphs; trees; network flows; Euler and Hamilton cycles; matchings; coverings; branch-and-bound; Lagrangian relaxation; cutting planes; polyhedral methods; heuristics; discrete optimization × Cite Format Result Cite Review PDF