DM811: Heuristics and Local Search Algorithms for Combinatorial Optimization (5 ECTS)

STADS: 15004601

Level
Master's level course

Teaching period

Offered according to needs.

Teacher responsible
Email: marco@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
Ubegrænset deltagerantal. 1. kvartal.

Prerequisites:
None

Academic preconditions:
The content of DM507 Algorithms and Data Structures should be known.

Course introduction
The students will learn how to implement efficient heuristics and local search algorithms to obtain near-optimal solutions for discrete optimization problems. These algorithms are useful for finding good approximations in reasonable time to NP-hard combinatorial problems, for which efficient exact solution methods are not known. Today, such heuristics are used for solving most large scale optimization problems occuring in practical settings.
Examples are greedy heuristics, tree-based search heuristics, iterative improvement, probabilistic iterative improvement, and large scale neighborhood search. The course will focus on example problems such as traveling salesman, boolean satisfiability, graph coloring, scheduling, packing and cutting in order to study the heuristics that have proved to be most successful for such problems.

The course is intended for persons interested in studying techniques with large practical usefulness. Since there are only few theoretical results available for these methods, we will not focus on theory but rather on gaining practical experience with the methods.

Expected learning outcome
After the course, the student is expected to be able to:

- describe in a precise and suitable language, including with the help of pseudeocode, the algorithms from the curriculum;
- adapt specific algorithms (construction heuristics and local search) to special cases of the problems studied or to new problems;
- design new algorithms based on the principles of those learned in the course;
- implement the designed algorithms in a suitable programming language;
- analyze the applied heuristic algorithms with respect to solution quality, computation time, memory usage and other qualities;
- undertake empirical studies of the applied methods and draw sound conclusions on qualitative and quantitative aspects of these methods;
- discuss the results obtained in the two previous points.

Subject overview
Construction heuristics, greedy heuristics, local search, iterative improvement. Several optimization problems, including the travelling salesman problem, satisfiability, and graph coloring.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
The project assignment is graded according to the 7-scale. Internal censorship.
The project consists of implementing and analysing a number of heuristics and local search algorithms, resulting in a written report.

Re-examination following the rules passed by the study board.

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

Forelæsninger: 20 timer
Laboratorieøvelser: 14 timer
Educational activities

Language
This course is taught in English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.