<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD><TITLE>B Golden Rules</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node52.html#appendix.traps"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node54.html#appendix.data">Next >></A></TD></TR></TABLE><DIV id="appendix.golden-rules"><H1><A name="appendix.golden-rules">B Golden Rules</A></H1><P>We offer the following rules for the design of efficient constraint programs. </P><DIV class="unnumbered"><H2><A name="label169">Analyze and Understand your Script</A></H2><P>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?</P></DIV><DIV class="unnumbered"><H2><A name="label170">Experiment</A></H2><P>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.</P></DIV><DIV class="unnumbered"><H2><A name="label171">Have as much Constraint Propagation as Possible</A></H2><P>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.</P></DIV><DIV class="unnumbered"><H2><A name="label172">Find a Good Distribution Strategy</A></H2><P>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 <A href="node21.html#section.elimination.grocery">Section 4.1</A>) is an example where domain splitting is much better than trying the least possible value. Our script for the Queens Puzzle (see <A href="node25.html#section.scripts.queens">Section 5.1</A>) can solve the puzzle even for large <I>N</I>'s by using a first-fail distribution strategy that tries the value in the middle of the domain of the selected variable first.</P></DIV><DIV class="unnumbered"><H2><A name="label173">Keep the Number of Variables and Propagators Low</A></H2><P>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 <A href="node25.html#section.scripts.queens">Section 5.1</A> is particularly successful in keeping the number of propagators low. </P><P>Use the statistics feature of the Panel to find out how many variables and propagators were created.</P><P>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 <A href="node32.html#section.propagators.pythagoras">Section 7.2</A>).</P></DIV><DIV class="unnumbered"><H2><A name="label174">Eliminate Symmetries</A></H2><P>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 <A href="node25.html#section.scripts.queens">Section 5.1</A>) avoids possible symmetries by having a minimal number of variables. The models for the Grocery and Family Puzzles (see <A href="node21.html#section.elimination.grocery">Section 4.1</A> and <A href="node22.html#section.elimination.family">Section 4.2</A>) 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 <A href="node31.html#section.propagators.fractions">Section 7.1</A>) eliminates symmetries by imposing an order on the three occurring fractions.</P></DIV><DIV class="unnumbered"><H2><A name="label175">Introduce Propagators for Redundant Constraints</A></H2><P>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 <A href="node31.html#section.propagators.fractions">Section 7.1</A> and <A href="node33.html#section.propagators.squares">Section 7.3</A>) feature good examples for nonredundant propagators for redundant constraints.</P></DIV><DIV class="unnumbered"><H2><A name="label176">Use Recomputation if Memory Consumption is a Problem</A></H2><P>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 <A href="../system/node9.html#chapter.search">Chapter 4 of ``System Modules''</A> and the Explorer (see <A href="../explorer/index.html">``Oz Explorer - Visual Constraint Programming Support''</A>) feature support for so-called <A name="label177"></A><EM> recomputation</EM>. Recomputation reduces the space requirements for these problems in that it trades space for time. </P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node52.html#appendix.traps"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node54.html#appendix.data">Next >></A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.ps.uni-sb.de/~smolka/">Gert Smolka</A><BR><SPAN class="version">Version 1.4.0 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1229
