Obligatory Assignment 1, Autumn 2016 [pdf format] |
Let C be a set of courses that need to have an exam session scheduled. Let D be the set of integer numbers representing the days of the month that are available for scheduling exams. In the general case we will assume that the set D may contain holes. For each course c ∈ C we are given the duration dc of the exam expressed in number of days. Finally, we are given the enrollments of students to the courses, ie, a set Cs⊂ C for each student s. An exam schedule is an assignment of courses to days for the exam, that is, it is a function σ : C → 2D.
An exam schedule is feasible if it satisfies the following constraints:
You are given a starting package containing data on the exams for E15 at the Faculty of Science, SDU. An update with the data for E16 is expected during the assignment. Your task is to write a CP model to find feasible exam schedules, to implement the model in Gecode and to test it on the instances given.
A starting code package is available from:
it contains the parsers to read the input data and put them in a form that can be used for implementing the model.
Update on Tue Oct 4 18:16:26 CEST 2016:
The code has been updated to handle new data. The package
exams.tgz linked above contains the updated version. The package
contains only the files Input.h and Input.cpp that are changed.
The archive:
contains the new data files that you all have to use. To select the data files of E15 or E16 use the command line parameter, eg:
| 1 > ./xyz ../data/E16/ |
Remember to report results both for ALL_CRS set to 0 and
for ALL_CRS set to 1 (see below).
You should compile the program with the Makefile provided: from command
line type make. If something goes wrong it is most likely
because the path to the directory where your installation of Gecode and
Qt libraries are is wrong. Correct that in the Makefile following the
local gecode instructions or ask help to Marco.
In the class Input you find the data that you will need. In particular you have:
days is a vector that contains the integers representing the days.
crs_req, a map (a dictionary in Python jargon) with
courses C as keys and durations dc as values.
Initially, you should focus on scheduling only the courses from IMADA. Hence, in E15, there are
| 1 # courses: 20 # days: 21 |
Initially, try with a minimum separation of 4 days between the first day of two exams, ie, R=4. If no feasible solution can be found try decreasing R. If you succeed in scheduling IMADAs courses, then you should try to schedule all courses from the faculty. In order to have access to the full data, change in Input.h:
| 1 #define ALL_CRS 0 |
to
| 1 #define ALL_CRS 1 |
and then make clean and make.
You should now observe that the size of the problem becomes:
| 1 # courses: 75 # days: 21 |
To iterate through the elements of the data structures map and
unordered_map from the C++ Standard Library you can use any of
the following C++11 constructs:
| 1 for (pair<string, int> a: crs_req) { 2 cout<<"course "<<a.first <<" value "<< b.second<< endl; 3 } 4 5 for (auto a: crs_req) { 6 cout<<"course "<<a.first <<" value "<< b.second<< endl; 7 } 8 9 for_each(pa.crs_req.begin(), pa.crs_req.end(), [&] ( pair<string,int> s ) { 10 os<<s.first<<" "<<s.second<<"; "; 11 }); |
The last uses lambda functions. Alternatively you can use old C++ way via iterators:
| 1 unordered_map<string, int>::const_iterator pt; 2 for (pt = pa.crs_req.begin(); pt!=pa.crs_req.end(); pt++) 3 cout<<pt->first<<pt->second<<endl; |
For vectors, you have also usual indexing:
| 1 for (int i : pa.days) 2 cout << i; 3 4 for_each(pa.days.begin(), pa.days.end(), [&] ( int s ) { 5 os<<s<<" "; 6 }); 7 8 vector<int>::const_iterator pt; 9 for (pt = pa.days.begin(); pt!=pa.days.end(); pt++) 10 cout<<*pt; 11 12 for (int i=0; i<pa.days.size();i++) 13 cout<<pa.days[i]<<endl; |