×

Optimisation combinatoire. Méthodes mathématiques et algorithmiques. I: Graphes et programmation linéaire. II: Programmation discrète. (French) Zbl 0652.90085

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.

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