Constraint programming

The constraint programming ( English Constraint Programming , CP) is a programming paradigm that since the mid- 1980s developed years and as a development of logic programming has emerged. The Constraint -based programming allows the integration of constraints and their resolution mechanisms in a programming language. It is now an independent area of artificial intelligence and has a wide range of applications in practice and science.

With constraint programming, the user describes the problem in a declarative way, while the solution process takes a back seat from the user's perspective. This is taken over by the constraint solver. For Eugene Freuder, the paradigm therefore represents the closest approach to the “Holy Grail” of programming to date: the user defines the problem, the computer solves it.

Constraints

→ Main article : Constraint

The term constraint means something like constraint or secondary condition. They are special predicate logic formulas that describe conditions or restrictions. In the mathematical sense, this also means secondary conditions , such as those used, for example, in solving mathematical optimization problems .

For example, you can see the conversion formula of degrees Celsius in Fahrenheit regarded as a constraint: . By assigning values ​​to the variables, the constraint is either fulfilled (true) or not fulfilled (false). The conversion is fulfilled, for example, with and , while and the constraint is obviously violated. ${\displaystyle F=1,8\times C+32}$ ${\displaystyle F=68}$ ${\displaystyle C=20}$ ${\displaystyle F=1}$ ${\displaystyle C=1}$

The constraint is always fulfilled regardless of a value assignment, but the constraint is never fulfilled . ${\displaystyle X^{2}\geq 0}$ ${\displaystyle X^{2}<0}$

Another example is a Pythagorean triple , which is formed by three natural numbers , and , which indicate the length of the side of a right triangle. A constraint-based modeling of such triples over the domain of definition can be represented by the following constraint conjunction: ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle \{1,...,100\}}$

${\displaystyle x^{2}+y^{2}=z^{2}\land x,y,z\in \{1,...,100\}}$

One possible solution is the triple . ${\displaystyle (x,y,z)=(3,4,5)}$

Feasibility and solutions

After you have described a problem using constraints, you want to find out whether the constraints can be fulfilled. In addition, possible solutions can be of interest. The questions about the feasibility of constraints and specific solutions are closely linked. If a constraint can be fulfilled, there is at least one solution. However, the calculation of a solution is often more complicated than the determination of the satisfiability.

A "naive" approach to the decision of the satisfiability and to the calculation of concrete solutions would be to try out all possible assignments of the variables with values. However, the number of possible assignments is often very large or infinite, so that this approach fails. For this reason, special algorithms for handling constraints are used in many situations .

Constraint solvers are algorithms that provide tests and operations on constraints. These can often not only check the feasibility and calculate concrete solutions, but also carry out other operations on constraints.

Constraint systems

From a formal point of view, constraints represent special predicate logic formulas that are used to describe the properties of problems and their solution. This includes equations and inequalities about numbers, but also other expressions about numbers, Boolean values or any other quantity such as letters or words.

Constraint solvers usually only work on a special class of constraints. These are classified by constraint systems. In this way, suitable solution mechanisms can be assigned to the constraint systems.

Typical constraint systems are:

• Linear systems of equations : a set of linear equations with one or more unknowns that should all be satisfied at the same time. A variety of solving methods can be used to solve a system of equations, e.g. B. the Gaussian elimination method .

• Linear optimization : the optimization of linear objective functions over a set constrained by linear equations and inequalities . One algorithm that is often used in practice to solve such problems is the simplex method .

• Boolean constraints : Boolean equations whose variables represent either the validity of a statement (true) or its invalidity (false). A solver for Boolean constraints is fundamental for all problems that are formulated as propositional satisfiability problems. Usually a Boolean constraint solver supports logical operations such as negation , conjunction , disjunction , implication, and equivalence .

• Finite domain constraints: These have the property that the variables involved are assigned finite domains from the outset . This constraint system has been extensively investigated in research. In practice it is of great importance in solving combinatorial problems, e.g. B. to deal with planning, diagnosis and configuration problems.

Constraint-based programming

Constraint-based programming allows constraints and their solution mechanisms to be integrated into a programming language. In addition, it usually enables the definition of new constraints. Constraint libraries allow the functional and syntactic expansion of an existing language to include constraints using existing language concepts. A constraint-based language is a semantic extension of an existing language by new concepts and evaluation mechanisms up to a completely new draft.

Constraint-based programming originally developed as an extension of logical programming . It is now an independent area of artificial intelligence and has a wide range of applications in practice and science.

Constraint-logical programming

The logical programming works on the basis of a knowledge database from which the solution of queries is derived . When evaluating inquiries, the predicates are derived using the resolution . Constraint-logic programs differ from logic programs only insofar as in the right-hand side of the clauses and in queries, in addition to logical predicates, they also allow constraints, which are checked for satisfiability with the help of constraint solvers.

The syntax of constraint-logic programs does not differ significantly from that of logic programs. Constraints are only permitted in the right-hand side of the rules and in the requests. While logical predicates are still handled by unification, the additional constraints are collected, transferred to the constraint memory and handled by a constraint solver. Constraint-logic programs often allow different constraint domains (e.g. FD constraints, arithmetic constraints or Boolean constraints) with appropriate solution methods, which are then available in the form of libraries, for example.

Typical constraint-logical languages ​​that represent a generalization of the logical languages ​​are, for example, ECLiPSe, CHIP and SICStus-Prolog.

Concurrent constraint-logic programming

The concurrent constraint logic programming (Engl. Concurrent Constraint Logic Programming , CCLP) integrates the concept of concurrency in the constraint logic programming. Concurrency is the property of a system to be able to execute several calculations, instructions or commands at the same time. The system thus dispenses with sequencing . This is possible if the actions in question are causally independent of one another, i.e. H. no action required the result of another. Independent actions can either be processed sequentially in any order or real parallel on several computers at the same time.

The model of concurrent constraint programming can also work with partial information about variable assignments. Instead of specific data for variables, conditions can also be set on them.

A multiparadigmatic programming language that combines declarative, parallel and constraint-based approaches, among other things, is Oz .

Constraint-imperative programming

Constraint-imperative programming combines the two paradigms of constraint programming and imperative programming . In imperative languages ​​the programmer describes how a given problem is solved by a sequence of instructions. It is particularly suitable for modeling time processes. In constraint programming, on the other hand, the programmer concentrates on the what , i. That is, it describes the problem through their properties in the form of constraints. The combination of imperative programming with declarative constraints is therefore a particular challenge.

An example of a constraint-imperative programming language is Turtle. This emerged as a simple imperative basic language and was initially expanded to include functional concepts such as higher-order functions. Then it was enriched with four essential concepts for constraint programming:

• Constraint variables: These differ from "normal" imperative variables, the values ​​of which are determined by assignments, in that their values ​​are determined or restricted by constraints. Constraint variables are also known as declarative variables.

• Constraint statements: A constraint statement can contain several constraints linked by the and operator. When the require statement is executed, the constraints are added to the constraint memory of the constraint solver. The solver checks the satisfiability of the constraint conjunctions and assigns a solution to the constraint variables.

• User-defined constraints: These abstract from constraints like functions of expressions. They are used to define frequently occurring patterns in order to reduce the programming effort and improve the readability of the programs.

• Constraint solvers: These are responsible for managing the constraints executed with require and for calculating solutions. If the constraints in the memory cannot be fulfilled together, an exception is raised.

The Turtle ++ C ++ library has adopted many of the Turtle constructs and adapted them for harmonious integration in C ++.

Constraint object-oriented programming

The embedding of constraints in object-oriented programming languages is called constraint-object-oriented programming.

The firstcs library for object-oriented constraint programming exists for the object-oriented programming language Java . At its core is a class called CS ( Constraint Solver ). Every object of this class owns and manages variables over finite, integer domains and constraints over these variables. Due to the object-oriented design of the library, it is possible to generate and manipulate several constraint systems in one program at the same time, which, however, can currently only represent independent CSPs. There are also the classes Domain, Variable, Constraint and the subclasses of Constraint, which provide the basic methods and procedures for modeling and solving CSP around the core.

Another approach was the Kaleidoscope programming language, which integrates constraints into an imperative, object-oriented style. It is one of the first languages ​​to specify constraints between attributes of different objects.

In addition, Koalog is a well-known Java library for finite domain constraints and Ilog-Solver is a C ++ library for various domains.

Applications

In the scientific field, constraint-based programming is used, for example, in the processing of natural language, in machine-aided proof , in the analysis of programs and in molecular biology . In industrial practice, typical applications are optimization problems and scheduling tasks, circuit design and verification, graphic systems and user interfaces .

literature

• Frédéric Benhamou, Narendra Jussien, Barry O'Sullivan: Trends in constraint programming. John Wiley and Sons: London / Newport Beach, 2007.
• Thom Frühwirth, Slim Abdennadher: Constraint Programming: Fundamentals and Applications. Springer-Verlag: Berlin / Heidelberg, 1997, ISBN 3-540-60670-X
• Petra Hofstedt, Armin Wolf: Introduction to Constraint Programming. (Springer eXamen-press) Springer-Verlag: Berlin / Heidelberg, 2007, ISBN 978-3-540-23184-4
• Francesca Rossi, Peter van Beek, Toby Walsh (Eds.): Handbook of Constraint Programming. Elsevier: Amsterdam et al., 2006.

Web links

• Association for Constraint Programming

Individual evidence

1. ↑ Eugene C. Freuder: In Pursuit of the Holy Grail. In: Constraints 2 (1), 1997, pp. 57-61; Petra Hofstedt: Chapter Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (eds.): Handbook of Artificial Intelligence. 5th revised and updated edition. Oldenbourg Verlag: München, 2014, p. 206.
2. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, pp. 51-52.
3. ↑ Petra Hofstedt: Chapter Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (eds.): Handbook of Artificial Intelligence. 5th revised and updated edition. Oldenbourg Verlag: München, 2014, p. 205.
4. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, p. 58.
5. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, p. 60.
6. ↑ For a formal definition of constraints see Hofstedt, Wolf: Introduction to Constraint Programming. 2007, pp. 54-55.
7. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, pp. 53-55.
8. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, p. 177.
9. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, pp. 57, 71.
10. ↑ Petra Hofstedt: Chapter Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (eds.): Handbook of Artificial Intelligence. 5th revised and updated edition. Oldenbourg Verlag: München, 2014, p. 220.
11. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, SS 127-133.
12. ↑ Petra Hofstedt: Chapter Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (eds.): Handbook of Artificial Intelligence. 5th revised and updated edition. Oldenbourg Verlag: München, 2014, p. 221.
13. ↑ The Eclipse Constraint Programming System
14. ↑ Coystec: CHIP V5
15. ↑ SICStus: SICStus prologue
16. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, SS 141-162.
17. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, p. 185.
18. ↑ catamorph.de: Turtle - a constraint-imperative programming language ( memento of the original from April 8, 2016 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. 
19. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, pp. 185-192.
20. ^ Hofstedt, Wolf: Introduction to Constraint Programming. 2007, pp. 199-215.
21. ^ Gus Lopez, Bjorn Freeman-Benson, Alan Borning: Kaleidoscope: A Constraint Imperative Programming Language. In: Brian Mayoh, Enn Tyugu, Jaan Penjam: Constraint Programming. Springer-Verlag, pp. 313-329.
22. ↑ Petra Hofstedt: Chapter Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (eds.): Handbook of Artificial Intelligence. 5th revised and updated edition. Oldenbourg Verlag: München, 2014, p. 206.