My Constraint Programming Blog

The ECLiPSe program mentioned in this post: modulo_propagator.ecl which defines an modulo propagator for lib(ic) and includes some simple tests.

Preamble

In Some 40 new ECLiPSe models I mentioned some 40 models that where translated from SICStus Prolog to ECLiPSe. For two problems, however, I became very aware of that the where no support for the modulo operator in ECLiPSe's ic library.

• averbach_1.4.ecl: Seating puzzle, Problem 1.4 from Averbach & Chein "Problem Solving Through Recreational Mathematics"
• divisible_by_9_through_1.ecl: Divisible by 9 trough 1 (truncated numbers). In "any" base. From Microsoft, Visual C# Developer Center Solving Combinatory Problems with LINQ (A better name for this is "Divisible by Base -1 through 1".)

(These models has now been "patched" using the propagator version of modulo, but the older version is kept in comments.)

"Trickery" versions of modulo

In these models, I tried some different approaches ("trickeries"), including using the suspend library, which works for some problems, but not for these two.

  :- lib(suspend).
  % ....
  modulo_suspend(X,M,Y) :-  
       suspend(M is X mod M, 3, [X,Y]->inst).

One way that did worked with the Averbach & Chein Seating puzzle, was to use an auxilliary variable C1:

C1 :: 0..1,
PDyer+C1*5 #= (Hosier - 2),

and similar for the four other modulo constraints.

For the Divisible by 9 through 1 problem, I wanted this construct (which don't work since T[Base_I] is a decision variable and not bound which is required by mod)

 T[Base_I] mod I #= 0

The working version was using the lib(ic_kernel) predicate get_max for getting the maximal domain of T[Base_I]:

 
   % ...
   TBase_I is T[Base_I],
   % get max domain value for [Base_I]
   get_max(TBase_I, TBase_IMax), 
   MaxLimit is TBase_IMax // I,
   Q :: 1..MaxLimit,
   TBase_I #= Q*I
   % ...

A modulo propagator for ECLiPSe

However, I wasn't really satisfied with these solutions and first tried to write a modulo propagator based on the example in the Comet Tutorial (included in the Comet distribution). However, I didn't manage to translate it into working ECliPSe code.

Yesterday I recalled that the MiniZinc gang had implemented a modulo predicate for testing the new policy of modulo in MiniZinc. See Division and Modulus Functions. The predicate int_mod along with int_div_mod is defined in div_mod.mzn (written by Peter Stuckey, September 2009).

It was then surprisingly easy to translate this to ECLiPSe code, probably since both MiniZinc and ECLiPSe are so declarative (which for example Comet - albeit very high level - is not).

So, here (modulo_propagator.ecl) is my translation of this predicate to ECLiPSe:

:-lib(ic_kernel).
% syntactic sugar
:- op(500,xfy,'modulo').

% ...
 
modulo(X1,Y1,R1) :-
   X #= eval(X1),
   Y #= eval(Y1),
   R #= eval(R1),
   (
       nonvar(X),nonvar(Y) -> 
           R is X mod Y
   ;
           Y #\= 0,
           get_min(X,LBX),
           get_max(X,UBX),
           UBXNeg is -UBX,
           LBXNeg is -LBX,
           min(LBX,UBXNeg,MinX),
           max(UBX,LBXNeg,MaxX),
           D :: MinX..MaxX,
           
           X #= Y * D + R,
           -abs(Y) #< R, R #< abs(Y),
           MinX #=< D,
           D #=< MaxX
   ).

The lib(ic_kernel is for the low level predicates get_min and get_max for getting the min/max domain of a decision variable. The three eval at the beginning is to be able to use expressions in the arguments, e.g. as (as in averbach_1.4.ecl):

PDyer #= (Hosier-2) modulo 5,

The corresponding part in the Divisible by 9 .. 1 problem is just as I wanted it.

T[Base_I] modulo I #= 0

Well, I don't really know if this is the best (or even a good) implementation of the modulo operator in ECLiPSe, and I assume that it can be improved upon. However, it seems to work well for my purposes.