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

STADS: 15007601

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. Kurset kører i 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:
a) Mandatory assignments, pass/fail with internal evaluation by the teacher. Assignments must be passed in order to attend the final project exam.
b) The exam consists of a project assignment that includes implementing and analyzing a number of heuristics and local search algorithms and results in a written report. The project assignment is graded according to the Danish 7-scale with external censorship.

Re-examination following the curriculum.

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 Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.