[gecode-users] Taking an n-ary OR of distinct constraints?

[Christian Schulte]

Hi,

While you can express it easily enough in Gecode there is another catch:
there will be very little propagation.

So what you can do is the following: express each alldifferent by a
quadratic number of refied disequality constraints. For example, if you have
distinct(x,y,z) you reify as
	(x != y) <=> b1=1, (x != z) <=> b2=1, (y!=z) <=>b3=1
by introducing a quadratic number of Boolean variables bi.

Now, you will have to reify all of it into a conjunction
	b1=1/\b2=1/\b3=1 <=> b=1
Now b is 1 iff distinct(x,y,z) holds.

Then you can post a disjunction over all the Boolean variables you
introduced for each distinct.

This is more or less what MiniZinc will do.

Cheers
Christian

--
Christian Schulte, www.gecode.org/~schulte
Professor of Computer Science, KTH, cschulte at kth.se
Expert Researcher, SICS, cschulte at sics.se


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Jay
Sent: Thursday, May 07, 2015 5:52 PM
To: users at gecode.org
Subject: [gecode-users] Taking an n-ary OR of distinct constraints?

Hi,

I am building a model incrementally. I know in advance how many variables
there will be, but the constraints will be added to the model through a
graph search. I will have n integer variables, each taking a value from an
integer domain {1,...,k}. During the graph search, we are given a sets of
alldifferent (i.e. distinct) constraints. In a set of alldiff constraints,
at least one has to be satisfied (but not necessarily all!).

For example, a constraint to the model could be: (alldifferent(x1,x2,x3) OR
alldifferent(x2,x4,x6) OR alldifferent(x1,x2,x8)), where x_i's are
variables. If this 3-ary OR of 3 alldiff constraints is denoted by X, the
ultimate model could be say: (X AND Y AND Z), where Y and Z are similar sets
of alldiffs.

As far as I could tell from the documentation, an n-ary OR is not supported
between constraints. I can do this easily in MiniZinc though (just use \/),
so I wonder if I am mistaken here. If that is the case, what is a convenient
way of modeling such an n-ary OR between alldifferent constraints?

_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users