##
**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.

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 |