| << Prev | - Up - | Next >> |
We offer the following rules for the design of efficient constraint programs.
The first script for a difficult problem usually does not show satisfactory performance, even if you are expert. To improve it, you need to analyze and understand the search tree. The Explorer is a powerful tool for doing this. Use the statistics feature of the Panel to analyse the performance of your script: how many variables and propagators have been created? How often where the propagators invoked?
Once you have analyzed the search tree and performance of your script, start to experiment with different models, different distribution strategies, and propagators for redundant constraints.
More constraint propagation results in smaller search trees. Try to design a model that yields strong propagation. Try to eliminate symmetries by imposing canonical orders. Finally, try to find redundant constraints that result in stronger propagation when imposed as propagators.
A good distribution strategy can reduce the size of the search trees dramatically. Usually, it's a good idea to start with a first-fail strategy. The Grocery Puzzle (see Section 4.1) is an example where domain splitting is much better than trying the least possible value. Our script for the Queens Puzzle (see Section 5.1) can solve the puzzle even for large N's by using a first-fail distribution strategy that tries the value in the middle of the domain of the selected variable first.
The memory consumption of a script depends very much on the number of propagators and finite domain variables created. Models that keep these numbers low usually lead to more efficient scripts. The model for the Queens Problem in Section 5.1 is particularly successful in keeping the number of propagators low.
Use the statistics feature of the Panel to find out how many variables and propagators were created.
This rule conflicts with the rule asking for maximization of constraint propagation. Extra propagators for redundant constraints will improve performance if they reduce significantly either the size of search tree or the number of propagation steps (for the latter, see the Pythagoras Example in Section 7.2).
It is always a good idea to design a model such that symmetries are avoided as much as possible. The model for the Queens Puzzle (see Section 5.1) avoids possible symmetries by having a minimal number of variables. The models for the Grocery and Family Puzzles (see Section 4.1 and Section 4.2) eliminate symmetries by imposing a canonical order on the variables by means of additional constraints. The model of the Grocery Puzzle eliminates a subtle symmetry by stating that the price of the first item must have a large prime factor in common with the product of the prices of the items. The Fraction Puzzle (see Section 7.1) eliminates symmetries by imposing an order on the three occurring fractions.
Propagators for redundant constraints can often strengthen a script's propagation. A redundant constraint is a constraint that is logically entailed by the constraints specifying the problem. Try to find redundant constraints that yield nonredundant propagators. The models for the Fraction and Magic Square puzzles (see Section 7.1 and Section 7.3) feature good examples for nonredundant propagators for redundant constraints.
Scripts which create a large number of variables or propagators or scripts for which the search tree is very deep might use too much memory to be feasible. Search engines described in Chapter 4 of ``System Modules'' and the Explorer (see ``Oz Explorer - Visual Constraint Programming Support'') feature support for so-called recomputation. Recomputation reduces the space requirements for these problems in that it trades space for time.
| << Prev | - Up - | Next >> |