Course Description

Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it.
 (E. Freuder)

The use of constraints had its scientific and commercial breakthrough in the 1990s. Programming with constraints makes it possible to model and specify problems with uncertain, incomplete information and to solve combinatorial problems, as they are abundant in industry and commerce, such as scheduling, planning, transportation, resource allocation, layout, design, and analysis. Constraint-based programming languages enjoy elegant theoretical properties, conceptual simplicity, and practical success.

The idea of constraint-based programming is to solve problems by simply stating constraints (conditions, properties) which must be satisfied by a solution of the problem. Constraints can be considered as pieces of partial information. Constraints describe properties of unknown objects and relationships between them. Constraints are formalized as distinguished, predefined predicates in first-order predicate logic. The unknown objects are modeled as variables.

The main goal of this course is to give an introduction to a new programming paradigm based on constraints over different domains, such as Booleans, real (rational) numbers or finite domains. Special emphasis will be put on the practical use of these methods, in particular for solving combinatorial optimization problems.

Recommended Textbook:

Essentials of Constraint Programming
Thom Frühwirth and Slim Abdennadher
ISBN 3-540-67623-6

Programming with Constraints
K. Marriott und P. Stuckey
March 1998, 8 x 10, 476 pp.
ISBN 0-262-13341-5, MIT Press, USA.

The Art of Prolog
L. Sterling und E. Shapiro
MIT Press, USA, 2nd edition
1994.