zbMATH — the first resource for mathematics

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.

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.)