Integer optimization by local search. A domain-independent approach.

*(English)*Zbl 0934.90053
Lecture Notes in Computer Science 1637. Lecture Notes in Artificial Intelligence. Berlin: Springer. xix, 137 p. (1999).

The core idea of the presented approach is to find some new and improved tools for handling integer linear programs using ideas from constraint programming combined with heuristic concepts from combinatorial optimization. This monograph – which is based on the doctoral thesis of the author – is divided into eight chapters.

In the first chapter the necessary definitions for integer programs and heuristics are given. Also the concept of integer local search is outlined. Integer local search generalizes local search for propositional satisfiability (SAT), known from CP, to linear integer optimization. In the second chapter some successful frameworks for combinatorial optimization are discussed, i.e. integer linear programming (ILP), finite domain constraint programming (CP) and local search.

The third chapter is the core chapter of this monograph. Here local search for integer constraints is developed. To this for WSAT(OIP) is introduced, a domain-independent method that generalizes the Walksat procedure of Selman, Kautz and Cohen for propositional satisfiability. WSAT(OIP) operates on over-constrained integer programs (OIP). OIPs are feasibility problems with hard and soft constraints. Therefore instead of integrality – like in branch and bound procedures for ILP – feasibility is relaxed. It is shown that under very mild assumptions OIP is a special case of ILP. Several coupling techniques with linear programming are presented for computing bounds on the optimal solution. Also related work on local search for integer programming and constraint satisfaction is discussed. Unfortunately the interesting relation between OIP and multi-criteria optimization (especially goal programming) is missing.

After this theoretical part, the following chapters concentrate on case studies in which the power of WSAT(OIP) is demonstrated empirically. Chapter \(4\) gives an overview of the selected problems and explains why they are chosen. In Chapter \(5\) time-tabling and sports scheduling problems are discussed. These are examples for complicated \(0\)-\(1\) feasibility problems. For both problems experimental results are compared with previously reported results in the literature. The outcome is that WSAT(OIP) can compete with the existing solution approaches in terms of quality of the solutions produced and time required to obtain them. However, by adding redundant constraints the local search could be speeded up, which is similar to the behavior of branch and cut approaches. Chapter \(6\) deals with covering and assignment problems, which are examples of \(0\)-\(1\) optimization problems. Especially the radar surveillance covering and the course assignment problem is investigated. Again experimental results are compared to existing approaches. As a result WSAT(OIP) was able to outperform CPLEX on some of the largest test problems. The last chapter on case studies deals with capacitated production planning. Also here WSAT(OIP) is superior to CPLEX on the given data.

The book ends with a chapter describing limitations of the presented approach and possible extensions. It should also be mentioned that the author not only implemented WSAT(OIP), but he also provides an interface to the well known modeling language AMPL.

In the first chapter the necessary definitions for integer programs and heuristics are given. Also the concept of integer local search is outlined. Integer local search generalizes local search for propositional satisfiability (SAT), known from CP, to linear integer optimization. In the second chapter some successful frameworks for combinatorial optimization are discussed, i.e. integer linear programming (ILP), finite domain constraint programming (CP) and local search.

The third chapter is the core chapter of this monograph. Here local search for integer constraints is developed. To this for WSAT(OIP) is introduced, a domain-independent method that generalizes the Walksat procedure of Selman, Kautz and Cohen for propositional satisfiability. WSAT(OIP) operates on over-constrained integer programs (OIP). OIPs are feasibility problems with hard and soft constraints. Therefore instead of integrality – like in branch and bound procedures for ILP – feasibility is relaxed. It is shown that under very mild assumptions OIP is a special case of ILP. Several coupling techniques with linear programming are presented for computing bounds on the optimal solution. Also related work on local search for integer programming and constraint satisfaction is discussed. Unfortunately the interesting relation between OIP and multi-criteria optimization (especially goal programming) is missing.

After this theoretical part, the following chapters concentrate on case studies in which the power of WSAT(OIP) is demonstrated empirically. Chapter \(4\) gives an overview of the selected problems and explains why they are chosen. In Chapter \(5\) time-tabling and sports scheduling problems are discussed. These are examples for complicated \(0\)-\(1\) feasibility problems. For both problems experimental results are compared with previously reported results in the literature. The outcome is that WSAT(OIP) can compete with the existing solution approaches in terms of quality of the solutions produced and time required to obtain them. However, by adding redundant constraints the local search could be speeded up, which is similar to the behavior of branch and cut approaches. Chapter \(6\) deals with covering and assignment problems, which are examples of \(0\)-\(1\) optimization problems. Especially the radar surveillance covering and the course assignment problem is investigated. Again experimental results are compared to existing approaches. As a result WSAT(OIP) was able to outperform CPLEX on some of the largest test problems. The last chapter on case studies deals with capacitated production planning. Also here WSAT(OIP) is superior to CPLEX on the given data.

The book ends with a chapter describing limitations of the presented approach and possible extensions. It should also be mentioned that the author not only implemented WSAT(OIP), but he also provides an interface to the well known modeling language AMPL.

Reviewer: Stefan Nickel (Kaiserslautern)

##### MSC:

90C10 | Integer programming |

90C09 | Boolean programming |

90B90 | Case-oriented studies in operations research |

90C27 | Combinatorial optimization |

90C90 | Applications of mathematical programming |

90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |