Since the 1950's, researchers in mathematical programming and operations research have developed increasingly sophisticated methods for the solution of optimization problems. Over time this work was extended from problems with continous variables to include problems with logical and integer variables. Meanwhile, researchers in artificial intelligence developed somewhat similar approaches to the solution of constraint programming or constraint satisfaction problems, beginning with problems involving logical variables and expanding to cover finite domains, integers, and continuous variables.
The two fields were beginning to address the same problems, sometimes with very similar methods. In the 1990's, interest began to develop in combining the two approaches. The First International Joint Workshop on AI and OR in 1995 was followed by an annual series of CP-AI-OR workshops that have brought together researchers from both sides. John Hooker has been one of the leading researchers in this area. His book presents a synthesis of the integer programming and constraint programming approaches. It is also the first textbook to introduce the two subjects within a common framework.
Hooker begins with a short introductory chapter that introduces a framework for constraint satisfaction and integer programming algorithms. These algorithms combine elements of branching search with constraint propagation or logical inference and relaxation or bounding techniques. For example, a simple branch and bound algorithm for integer programming might use a search strategy involving branching on the values of the integer variables together with the solution of linear programming relaxations to obtain bounds that can fathom nodes in the search tree.
In Chapter 2, Hooker examines search strategies, including branching on variables, constraint directed branching, and heuristic local search. In Chapter 3, Hooker examines inference strategies and constraint propagation techniques for various kinds of constraints including logical constraints, linear ineqaulties, and the all-different constraint. Relaxation techniques for various kinds of constraints, including cutting planes and Lagrangian duality are considered in Chapter 4. Chapter 5 is a dictionary of various types of constraints with brief descriptions of search, inference, and relaxation strategies and references for further reading. This chapter will be especially useful as a ready reference for developers of solution algorithms that use the different kinds of constraints.
The book includes numerous examples and exercises. There is also an extensive bibliography and index. Hooker has done a particularly good job of organizing the sometimes bewildering array of options within the framework. Although the present state of the art doesn't allow for the automatic creation of a specialized algorithm for a particular problem, the book will help readers to understand the algorithms used within various software packages and to make appropriate choices in implementing the search-infer-relax framework.
This book is highly recommended, both as a reference for researchers working at the intersection of constraint programming and integer programming and as a textbook for graduate level courses that attempt to introduce the two fields in a unified way.
Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.
Preface.- Introduction.- Search.- The solution process.- Branching search.- Constraint-directed search.- Local search.- Bibliographic notes.- Inference.- Completeness.- Inference duality.- Linear inequalities.- General inequality constraints.- Propositional logic.- 0-1 linear inequalities.- Integer linear inequalities.- The element constraint.- The all-different constraint.- The cardinality and Nvalues constraints.- The circuit constraint.- The stretch constraint.- Disjunctive scheduling.- Cumulative scheduling.- Bibliographic notes.- Relaxation.- Relaxation duality.- Linear inequalities.- Semicontinuous piecewise linear functions.- 0-1 linear inequalities.- Integer linear inequalities.- Lagrangean and surrogate relaxations.- Disjunctions of linear systems.- Disjunctions of nonlinear systems.- MILP modeling.- Propositional Logic.- The element constraint.- The all-different constraint.- The cardinality constraint.- The circuit constraint.- Disjunctive scheduling.- Cumulative scheduling.- Bibliographic notes.- Dictionary of constraints.- References.- Index.