DM63: Heuristics for Combinatorial Optimization Problems (7.5 ECTS)

STADS: 1502541

Level


Teaching period

Fall semester.

Teacher responsible
Email: marco@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
None

Academic preconditions:
The content of DM02, MM02 must be known.

Course introduction
To introduce the students to a number of generic search algorithms, so-called metaheuristics, which have proven useful to obtain near-optimal solutions for many different optimization problems which occur in practical applications. A common feature of these algorithms is that they are often easy to implement and that one can apply these (with more or less succes) in order to find acceptable (that is near-optimal) solutions to many NP-complete combinatorial optimization problems. Examples of such are the travelling salesperson problem, scheduling, routing, packing and cutting problems. As the algorithms are generic (i.e. the underlying principle is not problem dependent) it is a natural consequence that they are not equally succeful for all types of optimization problems. It is a goal of the course to teach the students how to evaluate which of the algorithms seems to be best suited for a given problem (if any of them are). In order to make this evaluation a great deal of parameter tuning may be necessary for each method. Thus practical experience in this field is essential in order to judge applicability of each method. We also cover the branch and bound method which can be applied to find an optimal solution to any finite combinatorial optimization problem (given enough time and space!). The feasibility of solving a problem using B&B depends heaviliy on ones ability to estimate the value of an optimal solution and to evaluate how promissing intermediate steps are. The course addresses all students who wish to study techniques with high practical value rather than theory. We will not spend much time on the theory, but instead gather experience through practical experimentation.

Expected learning outcome


Subject overview
Heuristic algorithms, Simulated annealling, Tabu search, Iterated local search, Evolutionary algorithms, Backtracking.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Project. External examiner. Grades according to the 7-point scale. The project will be a natural continuation of the problems we have studied in the semester. Typically the purpose of the project is to compare various meta-heuristics for the same optimization problem.

Expected working hours
The teaching method is based on three phase model.

Vi starter med en 7-9 forelæsninger hvor formålet er at belyse de enkelte teknikker. Herefter er det planen at de studerende implementerer nogle af metoderne og eksperimenterer med disse. De skal så fremlægge deres resultater for de øvrige deltagere og i fællesskab drager vi konklusioner ud fra de eksperimentelle data (herunder om vi kan reproducere den opførsel som litteraturen beskriver for en given metode).
Educational activities

Language
This course is taught in English, if international students participate. Otherwise the course is taught in Danish.

Remarks
There will be a significant amount of programming and experimenting required. This is compensated for through a much lower number of lectures than normally. This course is taught in English, if any interational students participate, else the course is taught in Danish.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.