paradigm/technique where a problem is specified in terms of a constraint system
(a set of variables and their respective domains, and list of predicates ranging over the variables which must be true of all of them), and a type of TheoremProvingSystem
called a constraint solver
is employed to find solution(s) (a set of values which satisfy all constraints) to the problem.
A good introduction is PrinciplesOfConstraintProgramming
Constraint programming is an emergent software technology for declarative description and effective solving of large, particularly combinatorial, problems especially in areas of planning and scheduling. See also ConstraintModels
Since it's been around for decades (e.g. IvanSutherland's SketchPad), or even longer in pure math, why is it "emergent"? Is there some measure of popularity that it just achieved?
Just quoting http://kti.ms.mff.cuni.cz/~bartak/constraints/
, probably I should have made it clear?
Anyway I think that it is _emerging_ now. Operational Research is strictly related to CP, and new general purpose languages such as AliceLanguage
integrate constraint programming as a building block.
Traditional languages also are getting their CSP packages, I just stumbled across a package for Java and one for Python in the last week, and various PrologLanguage
implementations such as GnuProlog?
integrate modules to do CSP.
Finally I can see the growing of groups such as CoLogNet?
, the Constraint Programming Organizing Committee, and the Constraint Programming Industrial Association.
What's the difference between this and DesignByContract
, humans program both the constraints and solution to those constraints, and the language implementation checks that the solution is valid. In ConstraintProgramming
, you specify only the constraints, and the language implementation finds the solution for you. In DesignByContract
, the purpose of constraints is to ensure correctness. In ConstraintProgramming
, the constraints ARE the program.
for an example in MiniZinc
of a solution to ProjectEuler?
problem 9. Notice that there are no loops anywhere, and only the
output section contains anything imperative. MiniZinc
translates the constraints into a form that can be understood by a constraint solver, and after it is solved, converts the solution according to the format given in the MiniZinc