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

STADS: 15013601

Level
Master's level course

Teaching period
The course is offered when needed.

Teacher responsible
Email: marco@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

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
There isn't any litterature for the course at the moment.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Three assignments graded jointly according to the Danish 7-scale with external censorship. (15013602)

reexam in the same exam period or immediately thereafter.

 

Expected working hours
The teaching method is based on three phase model.
Intro phase: 20 hours
Skills training phase: 14 hours

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.