[Oz] Filtering of values of constraint variables

[Denys Duchier]

> > > filter(X, V) :-
> > >         (   \+ X = V -> X #\= V
> > >         ;   true
> > >         ).
> > 
> > It seems to me that, for finite domain and finite set variables, what
> > you outline above is pointless since X=V fails precisely when V is no
> > longer a value in the domain of X.
> 
> No, (because of the incompleteness of the FD solver) X=V can fail even if
> the domain of X contains V.  It happens quite often that none of the
> propagators posted on X can infer that V is inconsistent, but as soon as X
> is instantiated to V, they detect the inconsistency.

We are both right.  What you outlined in your filter is merely the
unification of X with value V.  This does fail precisely when V is not
in the domain of X.  What you really mean is: X=V plus propagation
using all other constraints in the system; in other words, you want to
add constraint X=V, then reach a new propagation fix point.
Essentially what you are describing here is a form of `local search'.
This is one the many things that first-class "computation spaces" make
possible to program.

The idea is as follows: the current state of your constraint problem
is encapsulated in a space S.  You want to perform local search on a
problem variable X, made available as feature x of S's root variable
(let's call the latter R).  For each value V in the domain of X, you
clone S as S2, inject the constraint X=V (i.e. R.x=V) and observe
whether S2 becomes failed or not.  Let D be the domain of all values
that do not lead to a failed S2.  You can now inject the constraint
X::D in S.

I know that Christian Schulte has actually used this technique to
improve search on a problem that I can't remember at all :-)

The techniques which I described in a previous message do not help you
if local search is the effect that you want to achieve.  They help you
express better more powerful constraints which may obviate the need
for local search.

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/.