Re: [eclipse-clp-users] Deferred propagation in IC

On 30/09/2013 21:58, Alex Mahrer wrote:
> Hello,
>
> Since constraints in the IC library tend to propagate as soon as they
> are called, it is presumable that the performance of a program
> containing multiple IC constraints may depend on the ordering of those
> constraints.
>
> For an example, see the code below. It calls a set of constraints using
> two different orderings, applying the global IC constraint,
> occurrences/3, either before or after the other constraints.
>
> In this case, we see that the second ordering is more efficient because
> it avoids unnecessary wakings of occurrences. However, in general we may
> not be free to choose an ordering of our constraints that avoids waking
> other constraints redundantly. This leads me to the following questions:
>
> 1) Outside of constraint ordering, is there a way to avoid the
> repetitive waking of IC constraints while additional IC constraints are
> being posted? In other words, can constraints be applied in batches?
>
> 2) If this cannot be accomplished with IC alone, is there another
> library or approach that fits the bill?

You can control this using priorities.  Constraints wake up with certain
priorities.  Complex constraints wake with lower priority than simple ones,
and occurrences/3 wakes with a priority of 3.

A useful idiom is to make a code sequence execute under high priority,
so it cannot be interrupted by woken goals, using call_priority(Goal, 2).
This will execute Goal under priority 2 (so it can only be interrupted
by priority 1 goals, which are reserved for debugging purposes).

In your example, you could do this for the bound constraint setup:

   call_priority(
       (for(I, 1, MaxVal - 3),
        param(Vars, MaxVal) do
	(foreach(Var, Vars),
	 param(I, MaxVal) do
	  Bound is MaxVal - I,
	  ic: (Var #< Bound)
	)
       ),
       2),

When you run this with the occurrences set up beforehand, their wakeup
will be postponed until the end of the call_priority.  As a result, it
executes almost as fast as when you delay the occurrences setup
until after the bounds setup.


-- Joachim


>
> Thanks,
> Alex
>
>
> Code:
>
> :- lib(ic).
> :- lib(ic_global).
> :- lib(util).
>
> main :-
>    time(constraint_ordering(before)),
>    time(constraint_ordering(after))
> .
>
> constraint_ordering(Order) :-
>    memberchk(Order, [before, after]),
>    length(Vars, 10),
>    MaxVal is 1000000,
>    ic: (Vars #:: 1..MaxVal),
>    (Order == before -> ic_global:occurrences(1, Vars, 1) ; true),
>    % Apply other constraints, potentially waking occurrences/3
>    % with each new constraint
>    (for(I, 1, MaxVal - 3),
>     param(Vars, MaxVal) do
>      (foreach(Var, Vars),
>       param(I, MaxVal) do
>        Bound is MaxVal - I,
>        ic: (Var #< Bound)
>      )
>    ),
>    (Order == after -> ic_global:occurrences(1, Vars, 1) ; true)
>    % If propagation could be deferred, we would invoke it here
>    % before starting search.
> .
>
> Output:
>
> Success, time = 78.19
>
> Success, time = 12.02