DM865: Heuristics and approximation algorithms
Study Board of Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N340040102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Master
STADS ID (UVA): N340040101
ECTS value: 10
Date of Approval: 01-11-2022
Duration: 1 semester
Version: Approved - active
Comment
The course is offered as required and is not necessarily offered every year. Exam attempts for DM865 are offered in accordance to the following plan, when the course is offered: Spring (course Start February): ordinary Exam (June), first reexamination (August) and 2nd reexamination (January or March).
Entry requirements
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.
Content
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
Examination regulations
Exam element a)
Timing
June
Tests
Oral exam
EKA
N340040102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Student Identification Card
Language
Normally, the same as teaching language
Duration
25 minutes
Examination aids
To be announced during the course
ECTS value
10
Additional information
Oral exam based on:the theoretical part and two practical project assignments submitted earlier.
Indicative number of lessons
Teaching Method
At the faculty of science the teaching is organized according to the three-phase model, ie. intro, the training and study phase.
- Introphase: 42 hours
- Training phase: 42 hours, of which: tutorial: 42 hours
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.
Educational activities is implementation of some of the algorithms taught in the course.
Teacher responsible
Additional teachers
Timetable
Administrative Unit
Team at Educational Law & Registration
Offered in
Recommended course of study
Transition rules
Transitional arrangements describe how a course replaces another course when changes are made to the course of study.
If a transitional arrangement has been made for a course, it will be stated in the list.
See transitional arrangements for all courses at the Faculty of Science.