DM841: Heuristics and Constraint Programming for Discrete Optimization (10 ECTS)

STADS: 15015501

Level
Master's level course

Teaching period
The course is offered when needed.

Teacher responsible
Email: marco@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
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

Subject overview
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

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None.

Assessment and marking:

1. Mandatory assignments. Evaluated by external censorship by the Danish 7-mark scale. (15015502)

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 re-exam takes place according to the rules decided by the Study Board. It consists of a single project corresponding in size to the multiple assignments during the course.

Expected working hours
The teaching method is based on three phase model.
Intro phase: 48 hours
Skills training phase: 40 hours, hereof:
 - Tutorials: 20 hours
 - Laboratory exercises: 20 hours

Educational activities

Educational form
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

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.