Re: incomplete constraint propagation

Raphael Finkel wrote:
> 
> Joachim,
> 
> Thanks very much for your informative response.  I have been using smodels for
> over a year, but I am new to Prolog-based constraint propagation.

I haven't heard about smodels, can you give me a pointer?


> 
> - Adding search is done by inserting the line
> -
> -       labeling(Costume),
> -
> - after the constraint setup and before printing results.
> - If you follow the execution, you will see that two
> - backtracks are needed before the solution is found.
> 
> How do I determine which variables need to have labeling turned on?  In this
> case, for instance, labeling(Costume) works, but only labeling(Place) does not.
> For now, I am using labeling(*) for all my classes.  I don't know if that
> makes things slower.

You just call labeling/1 on a list of all your problem
variables. The ones that are already instantiated at that
time will simply be skipped.

You may also want to look at the library fd_search, which
implements a more generic form of labeling where you can
select different heuristics etc.  If you are generating
code, it is probably best to by default choose a heuristic
that works well most of the time, such as first_fail.



> 
> -       (
> -           alldifferent(Costume),
> -           ( Scarecrow #= Place1 , Lion #= Place2
> -           ; Scarecrow #= Place2 , Lion #= Place3
> -           ; Scarecrow #= Place3 , Lion #= Place4
> -           )
> -       ) infers most,
> 
> Again, how can I determine which of my clauses to honor with "infers most"?

You can't know that without knowing something about the
problem structure. However, you actually do know something
because you are generating from a higher level description...
It might be a good idea to always handle disjunctions with
"infers most" rather than with reified constraints.

If you handle just the disjunction with infers most, i.e.

       (
           ( Scarecrow #= Place1 , Lion #= Place2
           ; Scarecrow #= Place2 , Lion #= Place3
           ; Scarecrow #= Place3 , Lion #= Place4
           )
       ) infers most,

that gives you the eliminaton of 4 as a possible value for
Scarecrow.

I suspect that it is impossible to discover automatically that
including the alldifferent in the scope of the "infers" gives
you just that extra bit of propagation which you need to solve
the problem without search...



> For now, I am staying away from propia.
> 
> - This now makes all the inferences that can be made by
> - looking at that particular group of constraints together,
> - and as a result you get the solution even without search.
> 
> How can I determine how many backtrackings are needed?  Is there a predicate
> similar to cputime/1 that I could use (like backtrackcount/1)?

search/6 from the fd_search library can do that.


> 
> - Since this discussion is of general interest, would you
> - mind if I copy this to the eclipse-users mailing list?
> 
> Not quite yet.  I have been working more on my front end.  I can now get
> Eclipse to handle a large subset of the Constraint Lingo language, but not all.
> Sometimes it is faster than smodels, sometimes slower.  At some point I will
> show you what I have done and ask for suggestions to speed up the search in
> those cases where Eclipse appears slower.
> 
> Thanks again for your speedy and helpful response.
> 
> Raphael

-- 
 Joachim Schimpf              /             phone: +44 20 7594 8187
 IC-Parc, Imperial College   /            mailto:J.Schimpf@ic.ac.uk
 London SW7 2AZ, UK         /    http://www.icparc.ic.ac.uk/eclipse