DM865: Heuristics and approximation algorithms (10 ECTS)

STADS: 15020201

Level
Master's level course

Teaching period
The course is offered in the spring semester.

Teacher responsible
Email: marco@imada.sdu.dk

Additional teachers
lenem@imada.sdu.dk

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

Comment:
Ubegrænset deltagerantal

Prerequisites:
The course cannot be chosen by students who have passed DM811, DM833 or DM841.

Academic preconditions:
Students taking the course are expected to be able to:

• use algorithms and data structures
• assess the complexity of the algorithms with respect to running time and space consumption
• program

The contents of DM507 Algorithms and Datastructures and DM550 Introduction to Programming  must be known. It is an advantage to know the contents of DM553 Complexity and Computability or DM508 Algorithms and Complexity and the contents of DM559 Linear and Integer Programming.

Course introduction
Many optimization problems from industrial applications such as scheduling, logistics, energy planning, sports planning, etc., can be formulated as discrete optimization problems, but they can not be resolved optimally within a reasonable time. Here, heuristics, metaheuristics and approximation algorithms play an important role. General heuristics and metaheuristics are loosely defined rules to proceed to near-optimal solutions. They are often inspired by nature. For example, local search techniques are based on the principle of trial and error, which is a possible way in which humans intuitively solve a problem. The success of specific heuristics to satisfactorily solve specific problems relies on insights into the structure of the problem and on the possibility of an efficient implementation. In contrast to heuristics, approximation algorithms come with a guaranteed running time and solution quality. For example, we will learn a simple and fast algorithm for finding a TSP-tour that is at most 50% longer than the optimal one. In this course, we will learn about heuristic and approximation algorithms, using a number of NP-hard problems as example problems.

The course builds on the knowledge acquired in the courses DM550 Introduction to Programming and DM507 Algorithms and Data Structures. Reference to concepts from DM554 Linear and Integer Programming together with DM508 Algorithms and Complexity or DM553 Complexity and Computability can also occur during the course. The course provides a basis for a master thesis in which algorithms for discrete optimization must be designed, analysed and implemented.

In relation to the competence profile of the degree it is the explicit focus of the course to:

• Give the competence to plan and execute scientific projects at an high professional standard
• Give the competence to plan and carry out scientific projects at the high professional level including managing work and development situations that are complex, unpredictable and require new solutions
• Give the skills to describe, analyze and solve advanced computational problems using the learned models
• Give the skills to analyze the advantages and disadvantages of various algorithms, especially in terms of resource consumptions
• Give the skills to elucidate the hypotheses of qualified theoretical background and critically evaluate own and others' research and scientific models
• Give the skills to develop new variants of the methods learned where the specific problem requires
• Give the skills in communicating through a written report research based knowledge and discuss professional and scientific problems with peers
• Give the expertise in discrete optimization and solution methods from the international research front

Expected learning outcome
The learning objective of the course is that the student demonstrates the ability to:

• design specialized versions of general purpose heuristics, greedy, local search and metaheuristics, for problems similar in nature to the ones seen in the course.
• develop a solution prototype in a local search framework.
• undertake an experimental analysis, report the results and draw sound conclusions based on them.
• describe the work done in an appropriate language, possibly including pseudocode.
• give an overview of the problems and techniques studied in the course.
• give a precise description and analysis of each of the algorithms studied in the course.

Subject overview
The following main topics are contained in the course:
Combinatorial algorithms, LP-based algorithms, greedy algorithms, (stochastic) local search algorithms, metaheuristics. These techniques will be applied, among others, on the following concrete problems: set cover, traveling salesman, satisfiability, scheduling, bin-packing, knapsack.

Literature

Meddeles ved kursets start

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:

1. Oral exam based on:the theoretical part and two practical project assignments submitted earlier. ( 10 ECTS). Marking by the danish 7-mark scale, external marking. Exam aids allowed, a closer description of the exam rules will be posted under 'Course Information' on Blackboard. (15020202).

Expected working hours
The teaching method is based on three phase model.
Intro phase: 42 hours
Skills training phase: 42 hours, hereof:
 - Tutorials: 42 hours

Educational activities
Implementation of some of the algorithms taught in the course.Educational form
The course will contain lectures, problem solving and programming. In the lectures, the theory will be covered, partly via a dialogue with the students. The aim of the problem solving is a better understanding of the theory, and through programming the students will obtain experience with the challenges and advantages of the various techniques and algorithm types.

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.