No label defined (Q4040221)

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.