Hide menu

Advanced Course on Constraint Programming

FDA152, 2005HT

Status Archive
School National Graduate School in Computer Science (CUGS)
Division DCS-LTH
Owner Krzysztof Kuchcinski
Homepage http://www.cs.lth.se/home/Krzysztof_Kuchcinski/CP.html

  Log in  




Course plan

Lectures

24h

Recommended for

Doctoral students in computer science.

The course was last given

Fall 2003.

Goals

The goal of this course is to give a good knowledge and practical
experience on programming with constraints over finite domains. The course will also
provide insight into current research issues in constraint programming
related to symmetry-breaking methods, connections to Integer Linear
programming and local search methods.

Prerequisites

Programming in Java. Data structures and algorithms.

Contents

Introduction
- Constraint Satisfaction Problem
- Constraint Graph
- Constraint Entailment
- Consistency Techniques (node and arc consistency, path consistency, bounds consistency, generalized consistency)
- Solver implementation

Combinatorial constraints and related algorithms (alldifferent, circuit, diffn, cumulative, etc.)

Search methods and search heuristics.

Modeling and other constraints.

Advanced Techniques
- Symmetry Elimination
- Connection to ILP
- Local Search

Organization

Lectures

Literature

Krzysztof Kuchcinski, "Constraint Programming Approach to Embedded System Optimization: Principles and Practice", Draft.

Lecturers

Krzysztof Kuchcinski

Examiner

Krzysztof Kuchcinski

Examination

Written assignments.

Credit

5

Organized by

Computer Science Dept. Lund University.

Comments

The course will be organized as an intensive course, i.e., there will
be two meetings of two days. In between students will work with programming assignments.


Page responsible: Director of Graduate Studies