Thom Frühwirth and Slim Abdennadher
Textbook, ISBN: 978-0817644451, Springer Verlag, 2003.
The first book that presented constraint logic programming languages and
constraint solving systems in a uniform and concise way.
A standard reference for two decades now.
"...a very valuable book that I wholeheartedly recommend..."
From review by Eric Monfory in Journal TPLP(4)3:381-382, 2004.
"Anybody looking for a formal, essential but never-shallow introduction to
the field should definitely consider this book."
From review
by Rosella Gennari in Journal of Logic, Language and Information (JOLLI), 2004.
"...a truly concise summary of constraint-based logic
programming...comprehensive...by far the best summarization..."
From review
by Bernard M. Kuc in ACM Computing Reviews,
2004.
Errata (thanks to Marc Meister and Walter Guttmann).
|
|
What is 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)
Slides Introducing Constraint Programming
Other Slides Introducing Constraint Programming
Video Vortrag (Talk in German):
Computer knacken harte Nuesse: Von Sudoku ueber den Aktienhandel zum Robotersegeln, Thom Fruehwirth, 2013.
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.
For example, consider a bicycle number lock. We forgot the first digit, but
remember some constraints about it: The digit was an odd number, greater than 1,
and not a prime number. Combining the pieces of partial information expressed by
these constraints (digit, greater than 1, odd, not prime) we are able to derive
that the digit we are looking for is "9".
As it runs, a constraint program successively generates constraints. As a
special program, the constraint solver stores, combines, and simplifies the
constraints until a solution is found. The partial solutions can be used to
influence the run of the program.
Book and Course Description
The formally well-founded presentation introduces the common classes of constraint programming
languages and constraint systems in a uniform way. It also includes application examples
from real life. We first introduce the basic ideas behind the family of (concurrent) constraint logic programming languages
in a calculus-based framework. Constraint solving algorithms are specified and
implemented in the constraint handling rules language (CHR) in a uniform
high-level executable notation.
The most common constraint domains, their solvers and applications such as
Boolean constraints for circuit design, terms and trees for unification, linear
polynomial equations for financial and engineering applications and finite
domains for scheduling, are presented.
The family of (concurrent) constraint logic programming languages
Preliminaries of Syntax and Semantics
Constraint logic programming (incl. Prolog)
Concurrent committed-choice constraint logic programming
Constraint handling rules (CHR)
Constraint systems and their solvers
Rational Trees
Feature Terms, Description Logic (not in book)
Boolean Constraints
Finite Domains
Linear polynomial equations
Non-Linear polynomial equations
Applications
Commercial applications, market and companies
Case study Munich rent advisor on the internet
Case study Planning wireless telecommunication
Case study Timetabling and Roomplanning
Course Slides
Courses by the authors were held at the University of Pisa in
1999 and 2002, at the University of Venice in 2004 and yearly at
the University of Munich from 1998-2001, at the University of Ulm since
2002, at the German University of Cairo since 2004.
Constraint Programming and Reasoning (Slides, 2019)
Constraint Programming Cheat Sheet
Constraint Systems Cheat Sheet
Supplementary slides:
Global Constraints (2013)
Theorem Proving - Resolution Variants (2002)
University Timetabling Application (2002)
Optimal Sender Placement Application (2002)
Practical Lab Course
The course can be combined with a practical lab course using a constraint logic programming language such as:
SWI Prolog
(SWI Prolog Reference Manual),
Sicstus Prolog
(Sicstus Prolog User's Manual),
Yap Prolog.
Constraint Handling Rules (CHR).
Exercises 2014
Exercises 2013
Exercises 2012
Constraint Programming Links
Thom Frühwirth et. al.,
Constraint logic programming: An informal introduction,
Chapter in Logic Programming in Action (G. Comyn et al., Eds.), Springer LNCS 636, 1992.
3rd CHR Summer School 2013: programming and reasoning with rules and constraints.
More constraint programming languages:
Ilog JRules BRMS,
Mozart (former OZ),
Cosytec CHIP,
Constraint
Papers
Constraint
Links
Thom Frühwirth,
updated March 29, 2022