DM826 - Modeling and Solving Constrained Optimization Problems
Obligatory Assignment 1, Spring 2012
[pdf format]
|
Deadline: 1st March 2011 at noon.
We consider the following problem in project assignment. A set of
project topics P={1,…,n} are offered to a set of
students S={1,…,s}. For each topic i a limited number
of teams ti can be created. If a team for topic i is created, the
number of students assigned to it must be between a minimum and maximum
bound, li and ui, respectively. Each student s ∈ S provides a
ranking of a subset of project topics, denoted by an ordered subsequence
of projects r(s)=(p(1),…,p(q)), p(i) ∈ P, 1≤
i≤ q≤ n. Moreover
students can register in groups of at most ℓ students, if
they want to be assigned to the same team. That is, students are
partitioned in groups, G={G1,…,Gm}, ∪i Gi =
S, Gi ∩ Gj=∅, ∀ i≠ j and |Gi| ∈
[1..ℓ]. Students in the same group Gi have the same preference
list, r(s1)=r(s2) for all s1, s2 ∈ Gi.
We wish to find an assignment of students to project teams, σ : S
→ [1..∑j∈ Ptj] such that each student is assigned to exactly
one project from his/her rank sequence, team bounds and group
requirements are satisfied and the assignment is fair and
efficient.
1 Your tasks
Make sure you have read all this document including the section
Practicalities before starting to work.
Describe the formulations and experiments requested in the points below
in a short report (max 3 pages). Do not describe the problem. Submit the
report together with the file models.py. Do not submit the
instances or the scripts made available. Submit in the BlackBoard
system an archive containing the report and the python file. Name the
archive with your CPR number (all 10 digits without dash).
There is not a predefined score for each point but point 1 is the most
important as from its correctness depends most of the remaining work.
- Formulate the problem as a constraint satisfaction problem and
solve it in gecode. In the report describe the model and specify the
branching choices used. Then report a table as the following filled in
with the computational statistics of the experiments.
- Some students like “farma” students should be preferably
assigned to projects from their area. Is it possible to satisfy this
requirement in a strict way? If it is not, implement a model that
takes care of satisfying this requirement as best as possible.
- So far we did not take into account the preferences of the
students. Now we wish to find an assignment that is as fair as
possible. Rank sequences can be transformed in a value matrix V∈
[0,1,…,Δ]2, where each element vij represents the
value that the student i puts on being assigned to project topic
j. If a project topic j is not in the priority list of the student
i, vij is set to zero. A value Δ is set for the projects
that are ranked first.
To determine the efficiency of an assignment σ that satisfies
all constraints expressed we use the vector v→=(v1,σ(1),…,vs,σ(s)) and the distribution of
students over ranks δ→=(δΔ,…,δ1),
where δi=1..Δ=|{s∈ S ∣ vs,σ(s)=i}|. For
two feasible assignments σ1 and σ2 it is then possible
to define two kinds of preference relations: lexicographic and
weighted. The former compares lexicographically the two vectors δ→1 and δ→2, the latter assigns a weight to each
rank, w: [1,…,Δ] → ℤ0+ and computes ∑s
w(vs,σ(s))=∑i =1..Δw(i)δi. Both relations
define a strict weak order organized in such a way that the best
efficiency is achieved by the feasible assignment that maximizes over
one of these relations.
The fairness criterion aims at ensuring that no student
benefits at the expenses of others. Taking only efficiency into
account it is possible to create examples where the overall
satisfaction is high to the disadvantage of a few students. A way to
take fairness into account is by searching for the assignment that
maximizes the worst preference, that is, maxmin{vs,σ(s)
|s∈ S}. This is also known as the maximin criterion.
Describe how you update your model from the previous points and
compare the solution quality with those from the previous
points. Report the comparison in a table like the one below (tip:
import the data in Gnumeric and export as a LaTex table): Report
computational statistics in the same fashion as for the table of the
first point.
2 Practicalities
This assignment is best 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 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.
