DM841: Heuristics and Constraint Programming for Discrete Optimization

Study Board of Science

Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N340104102
Censorship: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Master

STADS ID (UVA): N340104101
ECTS value: 10

Date of Approval: 17-03-2021


Duration: 1 semester

Version: Approved - active

Comment

The course is offered as required and is not necessarily offered every year.
Exam attempts for DM841 are offered in accordance to the following plan, when the course is offered: ordinary Exam (January), first reexamination (March) and 2nd reexamination (June or August).

Entry requirements

None

Academic preconditions

Students taking the course are expected to:

  • Have knowledge of linear and integer programming
  • Be able to use algorithms and data structures
  • Be able to assess the complexity of the algorithms with respect to runtime and space consumption
  • Be able to program

Course introduction

The aim of the course is to enable the student to solve in practice discrete optimization problems, which is important in regard to designing high efficiency solutions for industrial applications like scheduling, logistics, energy planning, sport planning, etc. Discrete Optimization is an exciting scientific field that focuses with problems that are most often. Constraint Programming and Local Search are two general-purpose solution paradigms. Constraint Programming is a programming paradigm, wherein variables and constraints between variables are expressed in a declarative form. A solution is then searched by tentatively assigning a value chosen from a valid domain to a variable and by consequently filtering according to the constraints the domains of the remaining variables.

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 the humans intuitively solve a problem. The success of specific heuristics to solve satisfactorily specific problems relies on insights into the structure of the problem and on the possibility of an efficient implementation.

Theory and practice go hand to hand in a course on Discrete Optimization that aims at preparing the students to solve real-life problems. Therefore the course will provide first-hand experience through programming tasks that involve the use of tools illustrating the fundamental concepts covered in the lectures.

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, can also occur during the course. The course provides a basis for a master thesis, in which constraint programming and heuristics are applied.

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 objectives of the course is that the student demonstrates the ability to:
  • model a problem similar in nature to the ones seen in the course within the framework of constraint programming and of local search
  • argue about the different modeling choices arising from the theory behind the components of constraint programming, including global constraints, propagators, search and branching schemes.
  • develop a solution prototype in a constraint programming system
  • design specialized versions of general purpose heuristics: construction heuristics and local search;
  • 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 including pseudocode

Content

The following main topics are contained in the course:
  • Introduction to discrete optimization;
  • Modeling in constraint programming with integer and set variables;
  • Notions of local consistency;
  • Global constraints and filtering algorithms
  • Search;
  • Symmetry breaking;
  • Construction heuristics and greedy algorithms;
  • Local search: modeling and algorithms;
  • Metaheuristics (variable neighborhood search, tabu search, simulated annealing, iterated local search, evolutionary algorithms);
  • Large scale neighborhood search;
  • Methods for the experimental analysis of optimization algorithms
  • Applications: constraint satisfaction, satisfiability, travelling salesman, vehicle routing, graph coloring, sport scheduling, scheduling, timetabling.

Literature

See itslearning for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

Autumn

Tests

Mandatory assignments

EKA

N340104102

Censorship

Second examiner: External

Grading

7-point grading scale

Identification

Full name and SDU username

Language

Normally, the same as teaching language

Examination aids

To be announced during the course.

ECTS value

10

Additional information

The evaluation consists of a number of assignments (3-5) during the course. The final grade will be given by a weighted average of these.

The examination form for re-examination may be different from the exam form at the regular exam, in this case it consists of a single project corresponding in size to the multiple assignments during the course.

Indicative number of lessons

88 hours per semester

Teaching Method

The teaching method is based on three phase model.
  • Intro phase: 48 hours
  • Skills training phase: 40 hours, hereof tutorials: 20 hours and laboratory exercises: 20 hours
Activities during the study phase:
  • Applications of the acquired knowledge to practical projects
  • Reading of scientific articles and book chapter
  • Practical experiments with the methods introduced in the course

Teacher responsible

Name E-mail Department
Marco Chiarandini marco@imada.sdu.dk Institut for Matematik og Datalogi, Datalogi, Datavidenskab & Statistik

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

Recommended course of study

Profile Programme Semester Period