[eclipse-clp-users] Deferred propagation in IC

From: Alex Mahrer <alex.mahrer_at_...341...>
Date: Mon, 30 Sep 2013 15:58:28 -0500

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

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?



:- lib(ic).
:- lib(ic_global).
:- lib(util).

main :-

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.


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 : Mon Jul 09 2018 - 02:05:30 CEST