DM841 (E21) - Heuristics and Constraint Programming for Discrete Optimization

Exam Timetabling

The problem description is the same as in the Assignment 3 and it will not be reported here. There, some freedom was left in the formulation of the criteria to optimize. Preferably, the same formulation that you have chosen there should be used in this assignment such that the numerical results can be compared. If for some reason you want to change formulation you should argue why you have done so in the report and preferably ask the teacher for approval early in the process. If you are tackling this case for the first time then you are free to choose the formulation that you deem the best.

Input Data

Initially, the instances are the ones from Assignment 3.

Specifically, there are five different instances of different size and difficulty:

The instances and details on their format can be found in Assignment 3.

We should expect heuristic algorithms to be able to find fast good results on the largest instances, hence more instances of the largest type will be soon made available.

Three new instances are available data.tgz.

Your Tasks

1. Design and implement one or more construction heuristics.

2. Design and implement one or more iterative improvement algorithms. They must terminate in a local optimum.

3. Design and implement metaheuristic algorithms. They can use as components the elements from points 1. and 2. used either as black boxes or modified according to the metheuristic principles.

4. Undertake an experimental analysis where you compare the algorithms from points 1. and 2. and configure the algorithms from point 3. to perform best on average on instances of the largest type. Overall never exceed one minute of running time for a single run of an algorithm.

5. Describe the work done in a report of at most 10 pages. The report must at least contain a description of the best algorithm designed and the experimental analysis conducted. The level of detail must be such that it makes it possible for the reader to reproduce your work.

6. Include in the report a table with the results obtained on the given instances by the best algorithm.

7. Submit your work making sure that the code provided will execute the best algorithm with a time limit of one minute when run from command line as follows:

   python3 src/main.py -s 1 -o OUTPUT_FILE -t 60 INSTANCE_FILE
   

   and reports in OUTPUT_FILE the best solution found in the format explained below. The parameters -s and -t are for the random see and the time limit in seconds, respectively.

Remarks

Remark 1 Make sure and give evidence that the results obtained by the algorithms in the point 3. above are better then those obtained in point 1. and 2.

Remark 2 The metaheuristics designed in point 3. can be any among those encountered in the lectures. More specifically, you can choose one or more algorithm templates among those from the groups treated in class:

• stochastic local search and local search based metaheuristics
• construction based metaheuristics
• population based metaheuristics

A few, well thought algorithms are better than many naive ones. However, it is expected that you compare a few alternatives.

Remark 3 You should be able to indicate in your report the name of the metahuristic(s) implemented. If your algorithm differ in some elements from the standard templates of the metaheuristics seen in class you must state that in the report and if it is an original attempt you should try to indicate which approach seen in class gets closer to it.

Remark 4 This is a list of factors that will be taken into account in the evaluation (possibly in order of importance):

• correctness of results claimed after running the submitted program
• quality of the final results;
• level of detail of the study;
• complexity and originality of the approaches chosen;
• presence of the analysis of the computational costs involved in the main operations of the local search.
• organization of experiments that guarantees reproducibility of conclusions;
• clarity of the report;
• effective use of graphics in the presentation of experimental results.
• correctness in the classification of the algorithms, that is, using the right names for the metaheuristics described

Output Format

The program must run with a command line parameter -o OUTPUT_FILE. In the path and filename provided by this parameter the program must write the solution in json format as shown below:

{
  "N100007102": [
      27
  ],
  "N100008102": [
      6
  ],
  "N100008132": [
      12
  ],
  "N100015102": [
      4
  ],
  "N100018102": [
      6
  ],
  "N100020102": [
      13
  ],
  "N100029102": [
      17,
      18,
      19,
      20
  ],
  ...
}

The json object is a dictionary with keys the STADS code of the exam and value and array with the days in which the exam has been scheduled. Days are indicated by number corresponding to the day number from the start of the year. For example day 01/01/2022 is day 1.