[eclipse-clp-users] Deferred propagation in IC

From: Alex Mahrer <alex.mahrer_at_adventiumlabs.com>
Date: Mon, 30 Sep 2013 15:58:28 -0500
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?

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
Received on Mon Sep 30 2013 - 21:18:46 CEST

This archive was generated by hypermail 2.2.0 : Tue Oct 01 2013 - 06:13:23 CEST