|
Contact Us Abteilung
Programmiermethodik und Compilerbau |
|
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)
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.
Constraint Handling Rules (CHR)
CHR was designed as a language for defining constraint solvers, but at the same time it is one of the most powerful multiset rewriting languages.Cited from Programming with Logical Links by Kazunori Ueda and Norio Kato.
Created by Thom Frühwirth in 1991, the CHR language has become a major specification and implementation language for constraint-based algorithms and applications. Algorithms are often specified using inference rules, rewrite rules, sequents, proof rules, or logical axioms that can be directly written in CHR. Based on first order predicate logic, the clean semantics of CHR facilitates non-trivial program analysis and transformation. About a dozen implementations of CHR exist in Prolog, Haskell, and Java. CHR is also available as WebCHR for online experimentation with more than 40 constraint solvers. More than 100 projects wordlwide use CHR.