| Guide to Constraint Programming |
© Roman Barták, 1998 |
||
| Contents | Next | ||
This page gathers information on constraints in a popular form of questions
and answers. I expect it to evolve into reach and useful part of the site. If you have any comments or corrections
to answers presented in this page, don't hesitate to contact
me.
Q: What is a constraint?
A: A constraint is simply a logical relation among several unknowns (or variables), each taking a value in a given domain (e.g., A+B=C, "the circle is inside the square" etc.).
Q: What does the constraint programming deal with?
A: Constraint programming is the study of computational systems based on constraints.
Q: Is it possible to use CSP for solving optimization problems which are solved by mathematical programmimg?
A: CSP can be used to find optimal solutions. This branch is called CSOP (Constraint Satisfaction Optimization Problems) and it's goal is similar to OR: find solution satisfying the constraints that minimize/maximize some function (see next question). It is also possible to use constraint hierarchies to find optimal solutions (use very weak constraint minimized_function=minimal_value).
Q: The optimisation aspect is emphasised in CP trough the use of a special additional constraint that is tighted when a solution is find. What is the efficiency of such technique?
A: In fact, the goal of CSOP is not to find the optimal solution (which is usually NP-hard) but to find some good solution quickly. Therefore constraint in the form "criteria_function<=expected_optimum_value" is added to the constraint store (if we are looking for a minimum). This corresponds to users requirements because the user wants to find some good solution, that is defined by the expected_optimum_value provided by the user, and if there is enough time, it is possible to tight the optimization constraint by decreasing the expected_optimum_value and to look for even better solution.
Q: Do have the usage of particular binarization technique some impact on the efficiency of the algorithm used to solve the CP problem?
A: The binarization of constraints is mainly theoretical tool to justify algorithms working with binary (and unary) constraints only. These algorithms are easier to understood but their ideas can be converted to n-ary constraints. Most practical applications work with n-ary constraints directly.
In fact, binarization with original variables is included implicitely in such algorithms. This is because using problem-dependent heuristics has significant impact on the efficiency of the system and it would be complicated to convert such heuristics to binarized (without original variables) problem.
Q: Where is possible to find information on real-life projects which exploit constraint programming techniques?
A: A good source was the PACT (Practical Application of Constraint Technology) conference organized by The Practical Application Company, but this conference was cancelled few years before (thus the above links might not work). There are also some workshops on practical applications organized within other conferences.
Q: Is it possible to add or remove variables from the constraint network?
A: In general, there is no difference between adding/removing a variable and adding/removing a constraint. Both cases can be represented by means of adding/removing constraints (e.g. removing a variable corresponds to removing all constraints which use this variable).
| Contents | Next | ||
|
Designed and maintained by Roman Barták |
|||