Integer programming.

*(English)*Zbl 0930.90072
Wiley-Interscience Series in Discrete Mathematics and Optimization. Chichester: Wiley (ISBN 0-471-28366-5). xx, 264 p. (1998).

This book is about ways to solve optimization problems with dicrete or integer variables. Chapter 1 introduces the reader to various integer programming problems and their formulation, and introduces the important distinction between good and bad formulations. Chapter 2 explains how it is possible to prove that feasible solutions are optimal or close to optimal. Chapters 3-5 study integer programs that are easy. The problems and algorithms are interesting in their own right, but also because the algorithmic ideas can often be adapted so as to provide good feasible solutions for more difficult problems. In addition, these easy problems must often be solved repeatedly as subproblems in algorithms for the more difficult problems. It is examined when linear programs automatically have integer solutions, which is in particular the case for network flow problems. The greedy algorithm for finding an optimal tree, the primal-dual algorithm for assignment problem, and a variety of dynamic programming algorithm are presented and their running times examined. Chapter 6 informally addresses the question of the apparent difference in difficulty between the problems presented in Chapter 3-5 that can be solved rapidly, and the “difficult” problems treated in the rest of the book. The fundamental branch-and-bound approach is presented in Chapter 7. Certain features of commercial integer programming systems based on branch-and-bound are discussed. Chapter 8 and 9 discuss valid inequalities and cutting planes. Examples of the cuts, and also the routines to find cuts that are being added to the latest systems are given. In Chapter 10 and 11 two important ways of decomposing integer programs are presented. The first is by Lagrangian relaxation and the second by column generation. Chapter 12 presents the basic ideas of various modern local search metaheuristics, introduces briefly the wost-case analysis of heuristics, and also discusses how an integer programming system can be used heuristically to find solutions of reasonable quality for highly intractible integer programs. Finally, Chapter 13 tries to give a better idea of how theory and practice converge when confronted with the choice of an appropriate algorithm, and the question of how to improve a formulation, or how to use a commercial mixed integer programming system effectively.

Reviewer: Guojun Li (Jinan)