Cover -- Title Page -- Cpoyright Page -- Table of Contents -- Foreword -- Acknowledgements -- Chapter 1. Introduction -- 1.1. Overview of the book -- 1.1.1. Constraint programming -- 1.1.2. Ant colony optimization -- 1.1.3. Constraint programming with ant colony optimization -- Chapter 2. Computational Complexity -- 2.1. Complexity of an algorithm -- 2.2. Complexity of a problem -- 2.2.1. The P class -- 2.2.2. The NP class -- 2.2.3. NP-complete problems -- 2.2.4. NP-hard problems -- 2.2.5. Undecidable problems -- 2.2.6. Complexity of optimization problems -- 2.3. Where the most difficult instances can be found -- 2.3.1. Phase transition -- 2.3.2. Search landscape -- 2.4. Solving NP-hard problems in practice -- 2.4.1. Exploitation of particular cases -- 2.4.2. Approximation algorithms -- 2.4.3. Heuristics and metaheuristics -- 2.4.4. Structuring and filtering the search space -- PART I. CONSTRAINT PROGRAMMING -- Introduction to Part I -- Chapter 3. Constraint Satisfaction Problems -- 3.1. What is a constraint? -- 3.1.1. Definition of a constraint -- 3.1.2. Arity of a constraint and global constraints -- 3.2. What is a constraint satisfaction problem? -- 3.2.1. Complexity of CSPs -- 3.3. Optimization problems related to CSPs -- 3.3.1. Maximizing constraint satisfaction -- 3.3.2. Constrained optimization -- 3.4. The n-queens problem -- 3.4.1. Description of the problem -- 3.4.2. First CSP model -- 3.4.3. Second CSP model -- 3.4.4. Third CSP model -- 3.4.5. Influence of the model on the solution process -- 3.5. The stable marriage problem -- 3.5.1. Description of the problem -- 3.5.2. CSP model -- 3.6. Randomly generated binary CSPs -- 3.7. The car sequencing problem -- 3.7.1. Description of the problem -- 3.7.2. CSP model -- 3.8. Discussion -- Chapter 4. Exact Approaches -- 4.1. Construction of a search tree -- 4.2. Constraint propagation.

4.2.1. Forward checking -- 4.2.2. Maintaining arc consistency -- 4.3. Ordering heuristics -- 4.3.1. Heuristics for choosing variables -- 4.3.2. Heuristics for choosing values -- 4.3.3. Randomized restart -- 4.4. From satisfaction to optimization problems -- 4.5. Discussion -- Chapter 5. Perturbative Heuristic Approaches -- 5.1. Genetic algorithms -- 5.1.1. Basic principles -- 5.1.2. Using GAs to solve CSPs -- 5.2. Local search -- 5.2.1. Basic principles -- 5.2.2. Metaheuristics based on LS -- 5.2.3. Using LS to solve CSPs -- 5.3. Particle swarm optimization -- 5.3.1. Basic principles -- 5.3.2. Using PSO to solve CSPs -- 5.4. Discussion -- Chapter 6. Constructive Heuristic Approaches -- 6.1. Greedy randomized approaches -- 6.1.1. Basic principles -- 6.1.2. Using greedy randomized algorithms to solve CSPs -- 6.2. Estimation of distribution algorithms -- 6.2.1. Basic principles -- 6.2.2. Using EDAs to solve CSPs -- 6.3. Ant colony optimization -- 6.4. Discussion -- Chapter 7. Constraint Programming Languages -- 7.1. Constraint logic programming -- 7.2. Constraint programming libraries -- 7.3. Constraint-based local search -- 7.4. Discussion -- PART II. ANT COLONY OPTIMIZATION -- Introduction to Part II -- Chapter 8. From Swarm Intelligence to Ant Colony Optimization -- 8.1. Complex systems and swarm intelligence -- 8.2. Searching for shortest paths by ant colonies -- 8.3. Ant system and the traveling salesman problem -- 8.3.1. Pheromone structure -- 8.3.2. Construction of a Hamiltonian cycle by an ant -- 8.3.3. Pheromone updating step -- 8.3.4. Artificial versus real ants -- 8.4. Generic ACO framework -- 8.4.1. Pheromone structure and construction graph -- 8.4.2. Construction of combinations by ants -- 8.4.3. Improving combinations with local search -- 8.4.4. Pheromone updating step -- 8.4.5. Parameters of an ACO algorithm.

Chapter 9. Intensification versus Diversification -- 9.2. ACO mechanisms for diversifying the search -- 9.3. Balancing intensification and diversification -- 9.4. Measures of diversification/intensification -- 9.4.1. The λ-branching factor -- 9.4.2. Resampling ratio -- 9.4.3. Similarity ratio -- Chapter 10. Beyond Static Combinatorial Problems -- 10.1.2. Solving multi-objective problems with ACO -- 10.2. Dynamic optimization problems -- 10.2.1. Definition of dynamic optimization problems -- 10.2.2. Solving dynamic optimization problems with ACO -- 10.3. Optimization problems over continuous domains -- 10.3.1. Definition of continuous optimization problems -- 10.3.2. Solving continuous optimization problems with ACO -- Chapter 11. Implementation Issues -- 11.1.2. Data structures associated with heuristic factors -- 11.1.3. Data structures associated with ants -- 11.2. Selection of a component with respect to probabilities -- 11.3. Implementation of a local search procedure -- 11.4. Computation of diversification/intensification measures -- 11.4.1. Resampling ratio -- 11.4.2. Similarity ratio -- PART III. CP WITH ACO -- Introduction to Part III -- Chapter 12. Sequencing Cars with ACO -- 12.2. A first pheromone structure for identifying good car sequences -- 12.2.1. Pheromone structure -- 12.2.2. Construction of a sequence by an ant -- 12.2.3. Pheromone laying step -- 12.3. A second pheromone structure for identifying critical cars -- 12.3.1. Pheromone structure -- 12.3.2. Construction of a sequence by an ant -- 12.3.3. Pheromone updating step -- 12.4. Combining the two pheromone structures -- 12.4.1. First pheromone structure -- 12.4.2. Second pheromone structure -- 12.4.3. Construction of a sequence by an ant -- 12.5. Comparison of the different ACO algorithms -- 12.5.1. Considered algorithms -- 12.5.2. Test suite -- 12.5.3. Parameter settings.

12.5.4. Experimental results -- 12.6. Comparison of ACO with state-of-the-art approaches -- 12.6.1. Considered approaches -- 12.6.2. IDWalk -- 12.6.3. VFLS -- 12.6.4. Experimental set-up -- 12.6.5. Experimental results -- 12.7. Discussion -- Chapter 13. Subset Selection with ACO -- 13.1. Subset selection problems -- 13.1.1. Maximum clique -- 13.1.2. Multidimensional knapsack -- 13.1.3. Maximum Boolean satisfiability -- 13.1.4. Maximum constraint satisfaction -- 13.1.5. Minimum vertex cover -- 13.1.6. Maximum common subgraph -- 13.1.7. Edge-weighted k-cardinality tree -- 13.2. Description of Ant-SSP -- 13.2.1. Construction of a combination by an ant -- 13.2.2. Pheromone laying step -- 13.3. Instantiations of Ant-SSP with respect to two pheromone strategies -- 13.3.1. The vertex pheromone strategy -- 13.3.2. The clique pheromone strategy -- 13.3.3. Comparison of the two strategies -- 13.4. Instantiation of Ant-SSP to solve CSPs -- 13.4.1. Heuristic factor -- 13.4.2. Local search -- 13.5. Experimental results -- 13.5.1. Randomly generated binary instances -- 13.5.2. Results on instances of the 2006 solver competition -- 13.6. Discussion -- Chapter 14. Integration of ACO in a CP Language -- 14.1. Framework for integrating ACO within a CP library -- 14.1.1. Pheromone strategy -- 14.1.2. Construction of assignments -- 14.1.3. Pheromone updating step -- 14.2. Illustration of ACO-CP on the car sequencing problem -- 14.2.1. CSP model -- 14.2.2. Variable ordering heuristic -- 14.2.3. Pheromone strategies -- 14.2.4. Heuristic factor -- 14.2.5. Experimental results -- 14.3. Discussion -- Chapter 15. Conclusion -- 15.1. Towards constraint-based ACO search -- 15.2. Towards a reactive ACO search -- Bibliography -- Index.