[Mozart Oz Users] Directed Search in Spaces?

[Denys Duchier]

frehberg at cs.tu-berlin.de (Frank Rehberger) writes:

> I did read the thesis of Christian Schulte "programming Constraint
> Services" but could not find a hint how to control the order, variables
> are labeled. And in addition I would like to control search via injecting
> new constraints of the form "X :=< Pivot" or "X :> Pivot" for a special
> variable X of the sub-space.

It is important to realize that what you call `search' is actually the
result of two orthogonal mechanisms:

        1. distribution (i.e. how to perform labeling on variables)
        2. exploration (i.e. how to explore the tree produced by the
           distribution strategy).

I believe that what you are after is a `distribution' strategy.  You
can program your own distribution strategies in Oz.  The most general
construct to this end is `choice'.  The typical shape of a procedure
implementing a distribution strategy is (off the top of my head):

	proc {Distribute Vars}
	  {Space.waitStable}
	  if {All Vars IsDet} then skip else
	    X = {ChooseVar Vars}
	    Pivot = {ChoosePivot X}
	  in
	     choice X =<: Pivot [] X >: Pivot end
	     {Distribute Vars}
	  end
	end

For FD and FS variables, there is usually an easier way which takes
advantage of the highly parametrizable FD.distribute and FS.distribute
procedures.  You should read about them in the "System Modules"
documentation.  There are many criteria which may guide (1) the choice
of a variable (2) the choice of how to constraint its domain further
for distribution.  The functionality used by FD.distribute to pick and
constraint a variable is also made available through procedure
FD.choose (FS.distribute uses only a naive criteria which it didn't
seem worth it to make similarly available).

My advice is:

1. carefully study what is already available with FD.distribute.  It
   may well be the case that what you want to achieve can be obtained
   by using appropriate parameters.
2. else try to design a strategy using the `generic' parameter to
   FD.distribute.
3. else try it using choice as outlined above.

There is also (early) support in the system for writing `distributors'
using the C++ API.  You should only try that route if you really
really need to squeeze more performance out of the distribution
strategy.  You should also only attempt it if you enjoy excruciating
pain.  ahem... :-)

Cheers,

-- 
Dr. Denys Duchier			Denys.Duchier at ps.uni-sb.de
Forschungsbereich Programmiersysteme	(Programming Systems Lab)
Universitaet des Saarlandes, Geb. 45	http://www.ps.uni-sb.de/~duchier
Postfach 15 11 50			Phone: +49 681 302 5618
66041 Saarbruecken, Germany		Fax:   +49 681 302 5615
-
Please send submissions to users at mozart-oz.org
and administriva mail to users-request at mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.