MSCI534: Optimisation and Heuristics
Optimisation and Heuristics
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MSCI534: Optimisation and Heuristics
Coursework (30% of module)
1 Coursework Description
In this coursework, you are to write a program that attempts to solve an exam timetabling problem
using heuristic techniques. Specifically your program will read in a problem instance from a file
and will attempt to produce a solution using constructive and improvement algorithms. Note that
the optimal solutions to such intractable problems, are not currently known and so algorithms seen
to quickly achieve low cost solutions are viewed more favourably.
You are required to submit to Moodle a Python .py file. The name of this file should be your
library number (e.g. 12345678.py, where 12345678 is an example library number).
You should also submit a document file named 12345678.docx, where 12345678 is an example
library number, containing: (i) a short summary of your work listing the tasks that you have
completed and outlining all the features you have incorporated, e.g., how your constructive heuristics
work, how your neighbourhood operators work, how your improvement methods work, any additional
tricks you have incorporated; and (ii) a copy of your Python code.
Please do not submit compressed files such as zip and rar files; and do not import any packages
apart from pandas, matplotlib, numpy, math, random, tkinter, copy, time, and seaborn.
Problem description
The examination timetabling problem is defined as follows: a set of exams E = {e1, . . . , en} are
required to be scheduled within a certain number of periods P = {p1, . . . , pm}, while trying to avoid
“clashes”. A clash occurs when there are one or more students who need to attend a pair of exams,
but these exams have been assigned to the same period. Each day has three periods (10:00-13:00,
13:00-16:00 and 16:00-19:00). There are r examination rooms, and only one exam can take place
each room at any one period. The objective is to minimise the number of students having exams
in consecutive periods on the same day. The number of days (d) that the timetable will span
is specified as part of the problem, so the number of available periods equals the number of days
times three.
The problem instances, which are available in .csv format, contain (in the following order) the
number of days d (and therefore m = d× 3 periods), the number of rooms r, the number of exams
n and a symmetrical matrix n× n that contains the number of common students in each exam
pair.
On Moodle you will find two problem instances: I1.csv and I2.csv (note that your heuristics will
be tested on hidden instances!). An example of a problem instance file I1.csv is shown below.
Please Turn Over
MSCI534 Optimisation and Heuristics Page 2 of 4
In this example, we have d = 1 day (i.e., m = 3 periods), r = 3 rooms and n = 8 exams. The
matrix shows that the number of students attending exam e1 is 9. The number of students who
need to sit both exams e1 and e4 is 1. The number of students who need to sit both exams e1
and e7 is 6. The number of students attending exam e2 is 4. The number of students who need
to sit both exams e2 and e8 is 1. The number of students attending exam e3 is 9. The number of
students who need to sit both exams e3 and e5 is 4. The number of students attending exam e4 is
3. The number of students who need to sit both exams e4 and e8 is 1; and so on.
Using the problem instance given above, a solution S to this problem can be stored as a 2D list
of size n × n, with rows representing periods and columns representing rooms. We will also use
a “dummy value” (in this case -1) in cases where rooms are unoccupied. Here is an example
solution to I1.csv problem instance: S = [[1, 4, 2], [3, 5, 8], [7,−1, 6]]. Here, exams e1, e4, and e2
are assigned to period p1; exams e3, e5, and e8 are assigned to period p2; and exams e7 and e6
are assigned to period p3. Also, exams e1, e3, and e7 are assigned to the first room. Exams e4,
and e5 are assigned to the second room. Finally, exams e2, e8, and e6 are assigned to the third room.
The number of clashes in S above is 1 + 4 + 3 = 8. These are incurred due to: Exams e1 and e4
being in period p1 (1 student affected); Exams e3 and e5 being in period p2 (4 students affected);
Exams e5 and e8 being in period p2 (3 students affected). Our aim is to find a feasible solution (i.e.
no clashes) with a cost as close to zero as possible. The cost is defined as the number of students
having exams in consecutive periods on the same day. Using the example solution above, we see
that 1 student has to sit exam e4 followed by exam e8; 1 student has to sit exam e2 followed by
exam e8; and 2 students have to sit exam e8 followed by exam e7. In this case the cost is therefore
1 + 1 + 2 = 4.
Task 1: (2 marks) Your first task is to write a Python program that asks the user for the input
file name and then reads-in the specified problem instance file.
Task 2: (5 marks) Construct an initial solution to this problem in a randomised fashion of your
choosing. In order to obtain a good mark for this task, you will need to add some ‘intelligence’
to the procedure to produce high-quality initial solution. Anything that improves upon the basic
initialisation method is acceptable (providing it is a genuine improvement).
Please Turn Over
MSCI534 Optimisation and Heuristics Page 3 of 4
Task 3: (3 marks) Implement a Feasibility method that returns the number of clashes. It is
critical that your feasibility function is correct. Thus it is worth checking initial results manually
using the small problem instance file I1.csv.
Task 4: (3 marks) Implement a Cost method that calculates the cost of the solution in the way
described above. It is critical that your cost function is correct. Thus it is worth checking initial
results manually using the small problem instance file I1.csv.
Task 5: (5 marks) Implement a method that improves the initially generated solution using hill
climbing method which accepts only non-worsening moves. To do this, you will need to implement
an appropriate neighbourhood operator. Your program should be run for a fixed number of
iterations. Ask the user to input the number of iterations. At the end of the run, your best
obtained solution should be saved in a .csv file. The file specifies the solution, and the last two
rows display the Feasibility and the Cost of the solution, respectively. This format is extremely
important, as I will be using my own checker software tool to automatically examine your solution
and your calculated Feasibility and Cost. The example solution described above would be displayed:
Task 6: (12 marks) Try to make your solver more efficient and powerful, by:
• Implementing two of the following methods: simulated annealing, tabu search and best
improvement (steepest descent). This is of course in addition to the hill climbing method
implemented in the previous task. Please ask the user to choose which method to apply (e.g.
press ‘1’ for hill climbing, ‘2’ for simulated annealing, and so on).
• Employing more than one neighbourhood operators within your hill climbing method. Think
carefully about the sort of operators (moves) that will be appropriate with this problem.
• When performing a move, you may notice that only some periods are altered. Thus, you may
be able to speed up your program by only re-evaluating the effected periods.
Ultimately the goal is to minimise the Cost with no clashes.
2 Coursework Submission
In accordance with University
regulations, work submitted up to three days after the deadline will be classed as late submission
(10 marks will be deducted), and after three days as a non-submission. However, if an extension
is given then the rule applies from the date of the extension.
Please Turn Over
MSCI534 Optimisation and Heuristics Page 4 of 4
3 Plagiarism
According to university rules, instances of plagiarism will be treated very seriously. Penalties
are in line with the institutional framework of the University. We will analyse the coursework
using plagiarism detection software. In the days following submission, and at a prearranged time,
selected students will be asked to spend a few minutes in Teams where you will demonstrate your
program to me. I will use this opportunity to ask you to provide information on your program and
explain parts of your code.