Constraint satisfaction
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy.[1] A solution is therefore an assignment of values to the variables that satisfies all constraints—that is, a point in the feasible region.
The techniques used in constraint satisfaction depend on the kind of constraints being considered. Often used are
Constraint satisfaction as a general problem originated in the field of artificial intelligence in the 1970s (see for example (Laurière 1978)). However, when the constraints are expressed as multivariate linear equations defining (in)equalities, the field goes back to Joseph Fourier in the 19th century: George Dantzig's invention of the simplex algorithm for linear programming (a special case of mathematical optimization) in 1946 has allowed determining feasible solutions to problems containing hundreds of variables.
During the 1980s and 1990s, embedding of constraints into a programming language was developed. The first language devised expressly with intrinsic support for constraint programming was Prolog. Since then, constraint-programming libraries have become available in other languages, such as C++ or Java (e.g., Choco for Java[2]).
Constraint satisfaction problem
As originally defined in artificial intelligence, constraints enumerate the possible values a set of variables may take in a given world. A possible world is a total assignment of values to variables representing a way the world (real or imaginary) could be.[3] Informally, a finite domain is a finite set of arbitrary elements. A constraint satisfaction problem on such domain contains a set of variables whose values can only be taken from the domain, and a set of constraints, each constraint specifying the allowed values for a group of variables. A solution to this problem is an evaluation of the variables that satisfies all constraints. In other words, a solution is a way for assigning a value to each variable in such a way that all constraints are satisfied by these values.
In some circumstances, there may exist additional requirements: one may be interested not only in the solution (and in the fastest or most computationally efficient way to reach it) but in how it was reached; e.g. one may want the "simplest" solution ("simplest" in a logical, non-computational sense that has to be precisely defined). This is often the case in logic games such as Sudoku.
In practice, constraints are often expressed in compact form, rather than enumerating all the values of the variables that would satisfy the constraint. One of the most-used constraints is the (obvious) one establishing that the values of the affected variables must be all different.
Problems that can be expressed as constraint satisfaction problems are the eight queens puzzle, the Sudoku solving problem and many other logic puzzles, the Boolean satisfiability problem, scheduling problems, bounded-error estimation problems and various problems on graphs such as the graph coloring problem.
While usually not included in the above definition of a constraint satisfaction problem, arithmetic equations and inequalities bound the values of the variables they contain and can therefore be considered a form of constraints. Their domain is the set of numbers (either integer, rational, or real), which is infinite: therefore, the relations of these constraints may be infinite as well; for example, has an infinite number of pairs of satisfying values. Arithmetic equations and inequalities are often not considered within the definition of a "constraint satisfaction problem", which is limited to finite domains. They are however used often in constraint programming.
It can be shown that the arithmetic inequalities or equations present in some types of finite logic puzzles such as Futoshiki or Kakuro (also known as Cross Sums) can be dealt with as non-arithmetic constraints (see Pattern-Based Constraint Satisfaction and Logic Puzzles[4]).
Solving
Constraint satisfaction problems on finite domains are typically solved using a form of
Complexity
Solving a constraint satisfaction problem on a finite domain is an
Constraint programming
Constraint programming is the use of constraints as a programming language to encode and solve problems. This is often done by embedding constraints into a
Constraint logic programming
A constraint logic program is a
Constraint satisfaction toolkits
Constraint satisfaction toolkits are
- Cassowary constraint solver, an open sourceproject for constraint satisfaction (accessible from C, Java, Python and other languages).
- Comet, a commercial programming language and toolkit
- Gecode, an open source portable toolkit written in C++ developed as a production-quality and highly efficient implementation of a complete theoretical background.
- Gelisp, an open source portable wrapper of Gecode to Lisp.[5] http://gelisp.sourceforge.net/
- IBM ILOG CP Optimizer: C++, Python, Java, .NET libraries (proprietary, free for academic use).[6] Successor of ILOG Solver/Scheduler, which was considered the market leader in commercial constraint programming software as of 2006[7]
- JaCoP, an open source Java constraint solver.
- Koalog, a commercial Java-based constraint solver.
- logilab-constraint, an open source constraint solver written in pure Python with constraint propagation algorithms.
- Minion, an open-source constraint solver written in C++, with a small language for the purpose of specifying models/problems.
- ZDC, an open source program developed in the Computer-Aided Constraint Satisfaction Project for modelling and solving constraint satisfaction problems.
Other constraint programming languages
Constraint toolkits are a way for embedding constraints into an
Constraints have also been embedded into functional programming languages.
See also
- Constraint satisfaction problem
- Constraint (mathematics)
- Candidate solution
- Boolean satisfiability problem
- Decision theory
- Satisfiability modulo theories
- Knowledge-based configuration
References
- ISBN 978-3-7357-2366-6.
- ^ Choco: An Open-Source java library for constraint programming. https://choco-solver.org Accessed Dec 12, 2021.
- ^ "4.1.1 Variables and Worlds‣ 4.1 Possible Worlds, Variables, and Constraints ‣ Chapter 4 Reasoning with Constraints ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition".
- ISBN 978-1-291-20339-4. Archived from the originalon 12 January 2013. Retrieved 24 October 2012.
- ^ Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. "GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES." Journal of Theoretical and Applied Information Technology 86 (2). 2016. 327-331.
- S2CID 4360357.
- ISBN 978-0-444-52726-4.
- ISBN 978-0-521-82583-2.
- Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 978-1-55860-890-0.
- Dincbas, M.; Simonis, H.; Van Hentenryck, P. (1990). "Solving Large Combinatorial Problems in Logic Programming". .
- Freuder, Eugene; Mackworth, Alan, eds. (1994). Constraint-based reasoning. MIT Press. ISBN 978-0-262-56075-7.
- Frühwirth, Thom; Slim Abdennadher (2003). Essentials of constraint programming. Springer. ISBN 978-3-540-67623-2.
- Guesguen, Hans; Hertzberg Joachim (1992). A Perspective of Constraint Based Reasoning. Springer. ISBN 978-3-540-55510-0.
- Jaffar, Joxan; Michael J. Maher (1994). "Constraint logic programming: a survey". Journal of Logic Programming. 19/20: 503–581. .
- Laurière, Jean-Louis (1978). "A Language and a Program for Stating and Solving Combinatorial Problems". .
- Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 978-1-84821-106-3.
- Marriott, Kim; Peter J. Stuckey (1998). Programming with constraints: An introduction. MIT Press. ISBN 978-0-262-13341-8.
- Rossi, Francesca; Peter van Beek; Toby Walsh, eds. (2006). Handbook of Constraint Programming. Elsevier. ISBN 978-0-444-52726-4. Archived from the originalon 2012-10-04. Retrieved 2006-10-13.
- Tsang, Edward (1993). Foundations of Constraint Satisfaction. Academic Press. ISBN 978-0-12-701610-8.
- Van Hentenryck, Pascal (1989). Constraint Satisfaction in Logic Programming. MIT Press. ISBN 978-0-262-08181-8.
- Rashidi, Hassan.; Tsang, Edward. (2012). "Novel constraints satisfaction models for optimization problems in container terminals". Journal of Applied Mathematical Modelling. 37 (6): 3601–34. .
External links
Videos
- Constraint Satisfaction Lecture by Dr Madhu Sharma (3:47)
- Introduction of Constraint Satisfaction Problems by Edward Tsang (7:34)
- Constraint Satisfaction Problems by Wheeler Ruml (9:18)
- Lecture on Constraint Satisfaction Problems by Indian Institute of Technology Madras (51:59)
- Lecture on CSPs (1:16:39)
- Lecture on Constraint Satisfaction Problems by Berkeley AI (1:17:38)
- Graduate Course in AI 5: Constraint Satisfaction by Prof Mausam (1:34:29)