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

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

Total number of planned lessons: 44

Hereof: 

Common lessons in classroom/auditorium: 44 

In the common lessons, concepts, theories and models are introduced and put into perspective. In these lessons there is room for questions and discussions. In addition, students will work in small groups on data-based problems and discussion topics, related to the content of the previous lessons. In these hours there is a possibility of working specifically with selected difficult concepts

Other planned teaching activities: 

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