DM826 - Modeling and Solving Constrained Optimization Problems
Obligatory Assignment 2, Spring 2012 [pdf format]

This assignment is a continuation of Assignment 1. It assumes the problem definition as reached in Task 3 of Assignment 1 (hence it includes all elements defined at Task 1, Task 2 and Task 3 and it considers the optimization of the worst preference in the assignment (fairness criterion).

The assignment consists of the following tasks.

1. Implement a branching rule that branches on the opening of a team.
2. Implement a model that uses set variables.
3. If you finished the two previous tasks you can consider the following free tasks:
   • Study the effect of the number of threads. Experimentally determine which is the improving factor achievable. (read first sec. 7.3 of [B3].)
   • Study the effect of the parameters “recomputation distance” and “adaptive recomputation distance” (read first sec. 7.2 of [B3])
   • Implement a random restart strategy for the cases where the search does not finishes within the time limit.

Use Table 1 as a skeleton for your comparisons and make sure that you report and comment your conclusions. You should use instances that allow to see differences. You can create challenging instances with the help of Table 2. For example, for the year 2012 a challenging instance can be the constraint satisfaction problem that asks to find a feasible solution that does not assign any student to their sixth preference.

You have to deliver a written report and a script file models.py containing your implementation. Restrict your written report to max 3 pages.

---

Table 1: Data for the comparisons.

---

---

Table 2: Results from a minmax approach followed by weighted sum or lexicographic (leximin) optimization.

---

Practicalities

(This section has remained the same as in Assignment 1. In the data it has been added the year 2012.)

This assignment is to be carried out in GECODE. All scripts mentioned below can be found at http://www.imada.sdu.dk/~marco/DM826/Resources/. Download and uncompress the archive dm826-ass1.tgz

• You should use gecode-python version 0.25 (be-aware that it has been updated on the February 22). This version includes the possibility to print out the statistics that are required in the assignment and to halt the search with some parameters.
• For the computational experiments use the input data of the years 2008, 2009, 2010, 2010, 2011, 2012 that you find in the directory data
• Write your models in models.py
• For reading the data import the module load_data written in load_data.py.
• For checking solutions, use the function implemented in main.py.
• Always impose in your experiments a time limit of 600 seconds.
• Facilities for printing a solution are given in main.py.
• Submit only the file models.py. It will be copied in a directory containing the same files as those provided with the assignment and it will be run on a linux environment.

Tips: print the data to understand how things are organized; use the solution checker in main.py to cross check your implementation.