DM841: Heuristics and Constraint Programming for Discrete Optimization

The Study Board for Science

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

STADS ID (UVA): N340104101
ECTS value: 10

Date of Approval: 27-02-2023


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).

The course cannot be chosen if you have passed, registered, or have followed AI505, or if AI505 is a constituent part of your Curriculum.

Entry requirements

None

Academic preconditions

Students taking the course are expected to:

  • Be able to use algorithms and data structures
  • Be able to assess the complexity of 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 very difficult to solve. Constraint Programming and Heuristics 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 humans intuitively solve a problem. The success of specific heuristics to solve satisfactorily concrete 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 provides a basis for a master thesis in discrete optimization.

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:
  • model a problem similar in nature to the ones seen in the course within the framework of constraint programming and 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 in a programming language a solution prototype based on heuristic algorithms;
  • undertake an experimental analysis, report the results and draw sound conclusions based on them;
  • describe the work done in an appropriate language, eventually 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, ant colony optimization);
  • 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

Assessment

Second examiner: Internal

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: 58 hours
  • Skills training phase: 30 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 Data Science

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period

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.