DM/DMP86: Local Search Methods: Applications and Engineering (10 ECTS)

STADS: 1507001

Level
PhD course

Teaching period


Teacher responsible
Email: marco@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Prerequisites:
None

Academic preconditions:
The contents of DM02 and DM63 must be known.

Course introduction
The course is a continuation of DM63 and aims at enlarging the knowledge of local search methods and their practical applications in optimization.

Problems:
A wide range of optimization problems arising from different real life applications (transport, scheduling, timetabling, economics). Some may be suggested by the students themselves and may include popular puzzles such as Sudoku. The course will also consider multi-objective and stochastic optimization problems and how local search methods must be adapted in these contexts.

Algorithms:
The student will be introduced to the most common construction heuristics, neighborhood structures, and speed-up techniques for the fast examination of the neighborhood on some of the most recurrent problems. Moreover, the coverage of metaheuristics will be completed by introducing other trajectory methods such as Variable Neighborhood Search, Scatter Search and Path Relinking. Algorithms inspired by swarm behavior such as Ant Colony Optimization or adaptive methods such as GRASP and Memetic Algorithms will also be treated.

Empirical Software Engineering:
Local search methods generate stochastic algorithms whose assessment necessitates empirical analyses. The student will learn the appropriate statistical methods for the empirical analysis of algorithms. These techniques, mostly based on sequential testing, are then used for solving the configuration issue in the development of highly performing local search methods.

Expected learning outcome


Subject overview
Stochastic Local Search, Heuristics, Metaheuristics, Optimization, Configuration Problem, Experimental Algorithmics, Sequential Testing.

Literature
There isn't any litterature for the course at the moment.

Syllabus
See syllabus.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Oral exam (30 minutes without preparation) and evaluation of project report(s). Each count 50% of the total grade. External examination with marks according to the Danish 13-point marking scale. In order to reduce the work load, projects can be made in groups of up to three persons. The projects are evaluated and graded by the teacher only and will include an oral presentation to the class by the groups. The external examinator will have access to the reports during the examination. At the oral exam there may be questions in the topics of the projects.

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

De første 5-7 uger vil bestå af forelæsninger og øvelser (ca. 28 timer i alt). Ved forelæsningerne vil vi illustrere de forskellige metoder og teknikker, samt diskutere disses anvendelse på en bred vifte af problemer. Projektemnet kan vælges individuelt efter godkendelse af læreren.
Educational activities

Language
No recorded information about the language used in the course.

Remarks
There will be a significant amount of programming and experimentation in the course. The course will also contain a certain amount of work for the visualisation of results within the R environment, a free software package for statistical computing. The course will be taught in English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.