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