Constraint Programming

"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)

Constraint-based programming has emerged as a clever combination of two logic-based paradigms: logic programming and constraint solving. Logic programming defines calculations by rules. Constraint solving in turn means solving problems by stating constraints (conditions, restrictions) that have to be satisfied by a solution and combining these constraints to narrow the search space before trying alternatives by search. Thus complex combinatorial problems can be treated efficiently and elegantly by combining constraint solving and searching.

The main application areas are resource planning, transport optimisation and layout generation. The worldwide turnover generated by applying this technology has been estimated at 100 million dollars for 1996 already.

This lecture introduces concepts that are standard in program analysis and artificial intelligence and gives an outlook on properties of future programming languages. The course deals both with formal and practical aspects and provides mature, up-to-date course material and free software online and in books for students who like abstraction and problem solving. The lecture has two main parts: constraint programming languages and constraint systems.

  • constraint programming languages: constraint logic programming, concurrent constraint programming, Constraint Handling Rules
  • constraint systems and their applications: terms, linear equations, finite domains, intervals

The exercises provide the opportunity to work with one of the most advanced constraint programming languages.


Lecture: Tuesday 14-16 in O27-122

Lab: Thursday 12-14 in O27-122