Integer and combinatorial optimization.

*(English)*Zbl 0652.90067
Wiley-Interscience Series in Discrete Mathematics and Optimization. New York etc.: Wiley. xiv, 763 p. £70.00 (1988).

Integer and combinatorial optimization has developed to an important field in its own right with strong relations to mathematics, computer science, engineering, management science or economics. In contrast to “continuous” optimization, some or all variables of an integer or combinatorial optimization problem are restricted to values which belong to a discrete set. Consequently, appropriate methods are required for their solution.

This book surveys the important “discrete” concepts, that have been developed during the last years. Its emphasis is on the mathematics of discrete optimization. The different topics are organized as follows:

Part I is devoted to the foundations of integer and combinatorial optimization: its scope, linear programming, graphs and networks, polyhedral theory, computational complexity, polynomial-time algorithms for linear programming and integer lattices.

Part II covers general integer programming: the theory of valid inequalities, strong valid inequalities and facets for structured integer programs, duality and relaxation, general algorithms, special-purpose algorithms and their applications.

Part III surveys combinatorial optimization: integral polyhedra, matching, matroid and submodular function optimization.

This book is beautifully written. It is outstanding for its comprehensive, detailed and up-to-date presentation of the important subjects of the field. We particularly appreciate the discussion of separation, basis reduction and of the theory of valid inequalities, topics that have rarely been treated in a comparable textbook. We recommend the book ft the bounds for the expectation behave monotonically by applying the obtained inequality to smaller and smaller subintervals. As this requires the evaluation of conditional probabilities and expectations, we replace the given distribution by a discrete one resulting from sampling, and determine the sampling size that keeps the statistical error negligible. Finally we conclude with the application to SLP recourse problems and state some computational results illustrating the effort for solving recourse problems.

This book surveys the important “discrete” concepts, that have been developed during the last years. Its emphasis is on the mathematics of discrete optimization. The different topics are organized as follows:

Part I is devoted to the foundations of integer and combinatorial optimization: its scope, linear programming, graphs and networks, polyhedral theory, computational complexity, polynomial-time algorithms for linear programming and integer lattices.

Part II covers general integer programming: the theory of valid inequalities, strong valid inequalities and facets for structured integer programs, duality and relaxation, general algorithms, special-purpose algorithms and their applications.

Part III surveys combinatorial optimization: integral polyhedra, matching, matroid and submodular function optimization.

This book is beautifully written. It is outstanding for its comprehensive, detailed and up-to-date presentation of the important subjects of the field. We particularly appreciate the discussion of separation, basis reduction and of the theory of valid inequalities, topics that have rarely been treated in a comparable textbook. We recommend the book ft the bounds for the expectation behave monotonically by applying the obtained inequality to smaller and smaller subintervals. As this requires the evaluation of conditional probabilities and expectations, we replace the given distribution by a discrete one resulting from sampling, and determine the sampling size that keeps the statistical error negligible. Finally we conclude with the application to SLP recourse problems and state some computational results illustrating the effort for solving recourse problems.

##### MSC:

90C10 | Integer programming |

90-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming |

90C27 | Combinatorial optimization |

90B10 | Deterministic network models in operations research |

52Bxx | Polytopes and polyhedra |

05B35 | Combinatorial aspects of matroids and geometric lattices |

90C35 | Programming involving graphs or networks |

90C05 | Linear programming |

68Q25 | Analysis of algorithms and problem complexity |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |