constraint satisfaction problem
In plain wordsA problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes.
A problem specified by a set of variables, a domain of possible values for each, and a set of constraints, each restricting the combinations of values that some subset of the variables may take together; a solution assigns a value to every variable so that all constraints hold. Map coloring, Sudoku, timetabling, scheduling and product configuration are standard examples. General CSPs are NP-completeNP-complete, adj.: Describes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all., so solvers combine backtracking searchdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch. with constraint propagation, which deletes values that cannot appear in any solution (arc consistency is the classic form), and with variable- and value-ordering heuristicsheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer. such as choosing the most constrained variable first. Constraint optimization adds an objective to minimize. Constraint programming — languages and solvers built around CSPs, such as MiniZinc and Google's OR-Tools CP-SAT — is a mainstay of industrial scheduling and logistics.
We modeled the nurse rota as a constraint satisfaction problem with 3,000 variables.
Origin
Ivan Sutherland's Sketchpad (1963) solved geometric constraints interactively, and David Waltz's 1972 line-labeling program for drawings of 3-D scenes showed the power of propagation. Ugo Montanari formalized networks of constraints in 1974, and Alan Mackworth's 1977 paper defined arc consistency and the AC-3 algorithm.
Related
- Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions.
- depth-first searchdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch.
- heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- answer set programminganswer set programming, n.: A way to solve hard puzzles and scheduling problems by describing in logical rules what a valid solution looks like; a solver then finds the arrangements that fit those rules.
- local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch.
- combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers.
- automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes.
Sources
- Montanari, U. (1974). Networks of Constraints: Fundamental Properties and Applications to Picture Processing. Information Sciences 7, 95–132.
- Mackworth, A. K. (1977). Consistency in Networks of Relations. Artificial Intelligence 8(1), 99–118.
Mentioned in
Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., depth-first searchdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch., heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer., NP-completeNP-complete, adj.: Describes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all., answer set programminganswer set programming, n.: A way to solve hard puzzles and scheduling problems by describing in logical rules what a valid solution looks like; a solver then finds the arrangements that fit those rules., branch and boundbranch and bound, n.: A method for finding the provably best answer to a hard puzzle: divide the possibilities into groups, quickly estimate the best any group could offer, and throw out every group that cannot beat the best answer already in hand., integer programminginteger programming, n.: Finding the best plan when some decisions must be whole numbers or yes-or-no choices — you cannot open half a warehouse or send 2.7 trucks. That small change makes the best plan far harder to find., local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch., satisfiability modulo theoriessatisfiability modulo theories, n.: An extension of logic-puzzle solving that also understands arithmetic, arrays and other data types, so it can check whether conditions in software, such as 'x + y > 10 and x < 3', can ever be met., tabu searchtabu search, n.: A search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends.