Ant Colony Optimization and Constraint Programming
Publication Date: April 2010 Hardback 256 pp.
Ant colony optimization is a metaheuristic - or very generally a form of “black-box” problem-solving algorithm - which has been successfully applied to a wide range of combinatorial optimization problems. This book describes the ant colony metaheuristic and examines its efficacy for solving some difficult combinatorial problems, with a specific focus on constraint programming.
The book is organized into three parts. The first part introduces constraint programming, which provides high level features to declaratively model problems by means of constraints. It describes the main existing approaches for solving constraint satisfaction problems, including complete tree search approaches and metaheuristics, and shows how they can be integrated within constraint programming languages. The second part describes the ant colony optimization metaheuristic and illustrates its capabilities on different constraint satisfaction problems. Finally, the third part shows how the ant colony metaheuristic may be integrated within a constraint programming language, thereby combining the expressive power of constraint programming languages to describe problems in a declarative way, and the solving power of ant colony optimization, as a means of efficiently solving these problems.
Foreword, Pascal Van Hentenryck.
2. Computational Complexity.
Part 1. Constraint Programming.
3. Constraint Satisfaction Problems.
4. Exact Approaches.
5. Perturbative Heuristic Approaches.
6. Constructive Heuristic Approaches.
7. Constraint Programming Languages.
Part 2. Ant Colony Optimization.
8. From Swarm Intelligence to Ant Colony Optimization.
9. Intesification versus Diversification.
10. Beyond Static Combinatorial Problems.
11. Implementation Issues.
Part 3. CPO with ACO.
12. Sequencing Cars with ACO.
13. Subset Selection with ACO
14. Integration of ACO in a CP Language
About the Authors
Christine Solnon is Associate Professor at the University of Lyon 1 and a member of the LIRIS laboratory. She is Vice-President of the AFPC, the French association for constraint programming.