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

STADS: 15015501

Level
Master's level course

Teaching period
The course is offered in the autumn semester.

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:
The content of Introduction to Programming and Algorithms and Data Structures should be known.

Course introduction
Discrete Optimization is an exciting scientific field forming the basis for high-efficiency scheduling, logistics, energy planning, sports scheduling, and more. Problems in Discrete Optimization are most often hard and their solution is a challenging task. To help in this task three important general-purpose solution paradigms have been developed: Mixed Integer Programming (MIP), Constraint Programming (CP) and Local Search (LS). This course provides an introduction to the science of Discrete Optimization and focuses on two of its solution paradigms: CP and LS. The course is self-contained and it does not assume knowledge of MIP.

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

One simply cannot learn to tackle the challenges of optimization without trying to solve real problems. The course aims at giving first hand experience through programming assignments that include the use of tools that implement many of the fundamental concepts covered in the lectures.

Qualifications
To solve discrete optimization problems the practitioner needs to have: problem solving skills, knowledge of general purpose methods, knowledge of specific approaches for specific problems, modeling skills, implementation experience, analyzis competences and reporting skills.

Expected learning outcome
At the end of the course the student is expected to be able 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
Discrete optimization; problem formulations and modeling; general purpose methods; constraint programming; constraint satisfaction model; search; propagation; local consistency; global constraints; symmetry breaking; construction heuristics; greedy algorithms; tree-based search heuristics; local search; large scale neighborhood search; metaheuristics (variable neighborhood search, tabu search, simulated annealing, iterated local search, evolutionary algorithms). Problems: travelling salesman, graph coloring, sport scheduling, car sequencing, vehicle routing, warehouse location, 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: 20 hours, hereof:
 - Tutorials: 20 hours

Educational activities Study phase: 30 hours

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.