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
Censorship: 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: 27-10-2018


Duration: 1 semester

Version: Approved - active

Comment

15020201 (former UVA) is identical with this course description. 

Entry requirements

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.

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

See Blackboard for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

June

Tests

Oral exam

EKA

N340040102

Censorship

Second examiner: External

Grading

7-point grading scale

Identification

Student Identification Card

Language

Normally, the same as teaching language

Examination aids

Allowed, a closer description of the exam rules will be posted under 'Course Information' on Blackboard.

ECTS value

10

Additional information

Oral exam based on:the theoretical part and two practical project assignments submitted earlier.

The examination form for re-examination may be different from the exam form at the regular exam.

Indicative number of lessons

84 hours per semester

Teaching Method

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 
  • Implementation of some of the algorithms taught in the course.

Teacher responsible

Name E-mail Department
Marco Chiarandini marco@imada.sdu.dk

Additional teachers

Name E-mail Department City
Lene Monrad Favrholdt lenem@imada.sdu.dk

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi, fiktiv)

Team at Registration & Legality

NAT

Recommended course of study

Profile Programme Semester Period