Sheet 6

Task 1

The two modeling tasks of Assignment 2 were taken from the CSP library CSPlib.org.

• 069: Balanced Nursing Workload Problem
• 082: Patient Transportation Problem

The two CP modeling approaches outlined in class are taken from these two articles:

P. Schaus, P. Van Hentenryck, and J.-C. Régin Scalable Load Balancing in Nurse to Patient Assignment Problems CPAIOR, 248-262, 2009

Quentin Cappart, Charles Thomas, Pierre Schaus, and Louis-Martin Rousseau A Constraint Programming Approach for Solving Patient Transportation Problems Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings 24, 490–506, 2018 Note: Publication Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) ISSN: 16113349

Task 2

Study the slides “Local Search Based Metaheuristics”, which introduce to the following algorithm templates (metaheuristics) for optimization heuristics:

1. Randomized Local Search
2. Guided Local Search
3. Simulated Annealing
4. Iterated Local Search
5. Tabu Search
6. Variable Neighborhood Search

Task 3

Consider the six templates defined above and the seven components of local search algorithms. Describe the instantiation of these elements on the vertex coloring problem where the task is to find a coloring that uses the least number of colors possible. Provide as much details as you can.