DM877: Constraint programming

Students taking the course are expected to be able to:

• use algorithms and data structures
• assess the complexity of the algorithms with respect to running time and space consumption
• program

The contents of DM550 Introduction to Programming and DM507 Algorithms and Data structures must be known.

The course aims to enable the student to use constraint programming systems, which is important in order to solve computational non-trivial problems in an often in practice effective way. Examples of these problems are discrete optimization problems such as scheduling, logistics, energy planning, sports planning and resource allocation. To help solve these problems, general purpose programming paradigms have been developed. This course provides an introduction to one of these: Constraint programming.

Constraint Programming is a programming language paradigm where variables and conditions between variables are expressed in a declarative form. A solution is sought by trying to assign a value selected from a valid domain to a variable and then by filtering values ​​from the domains of the other variables if these cannot not be part of a solution according to the given conditions.

One simply cannot learn to cope with the challenges of discrete optimization without trying to solve real problems. The course aims to provide first-hand experience through programming assignments that include the use of tools that illustrate many of the basic concepts covered in the lectures.

The course builds on the knowledge gained in the courses DM550 Introduction to Programming and DM507 Algorithms and Data Structures. The course provides a basis for making a thesis in which algorithms for discrete optimization are to be designed, analyzed and implemented.

In relation to the competence profile of the degree it is the explicit focus of the course to:

• Provide competence to plan and execute scientific projects at a high professional level, including managing work and development situations that are complex, unpredictable and require new solutions

• Provide skills in describing, analyzing and solving advanced computer science problems using the learned models

• Provide skills in analyzing the advantages and disadvantages of various algorithms, especially with regard to resource consumption

• Provide skills in elucidating proposed hypotheses on a qualified theoretical background and relate critically to own and others' research results and scientific models

• Provide skills in developing new variants of the learned methods where the specific problem requires it

• Provide skills in communicating research-based knowledge through a written report and discuss professional and scientific issues with colleagues

• Provide expert knowledge on discrete optimization and solution methods from the subject's international research front

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

• 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 

• undertake an experimental analysis, report the results and draw sound conclusions based on them.

• describe the work done in an appropriate language

The following main topics are contained in the course:

• constraint satisfaction model
• local consistency and propagation
• global constraints
• search and tree-based search heuristics
• symmetry breaking
• random restart strategies and large scale neighborhoods
• constraint programming systems
• applications: puzzles, combinatorial design, route planning, scheduling.

• Intro phase: 26 hours
• Training phase: 18 hours

• Solution of weekly assignments in order to discuss these in the exercise sections.
• Solving the project assignments
• Self study of various parts of the course material.
• Reflection upon the intro and training sections.