[gecode-users] Reified max/min

[Mikael Zayenz Lagerkvist]

Hi,

There is no reified version of min available. However you can solve
this easily by introducing an auxiliary variable.

Say that you want to express
    b <=> min(x_0,..x_n)=y
This can be modeled as follows
    min(x_0,...,x_n)=t
    b <=> t=y
where t is a otherwise unconstrained variable with an initial domain
including all possible values for x_0,...,x_n.

Hope this helps,
Mikael


On 4/18/07, Jonathan Mörndal <Jonathan.Morndal.7625 at student.uu.se> wrote:
> Hello all!
>
> I would like to use a reified version of the max/min functions in
> Gecode/J. As far as I can see there are none. Is this true, and if so,
> are there any "quick fix"?
>
> One idea I had was to model it as numerous inequalities and equalities
> instead, but I guess the propagation will not be very good in that case.
>
>
> Thanks in advance for any help!
> /Jonathan
>
> Clarification:
>
> What I want to model exactly:
>
> x_0 = min{x_i,...,x_j}
> or
> x_1 = min{x_k,...,x_l}
> or
> ...
> or
> x_p = min{x_m,...,x_n}
>
> My (probably pretty bad) solution would then be
>
> ((x_0 \leq x_i and ... and x_0 \leq x_j)
> and
> (x_0 = x_i or ... or x_0 = x_j))
>
> or
>
> ((x_1 \leq x_k and ... and x_1 \leq x_l)
> and
> (x_1 = x_k or ... or x_1 = x_l))
>
> or
>
> ...
>
> or
>
> ((x_p \leq x_m and ... and x_p \leq x_n)
> and
> (x_p = x_m or ... or x_p = x_n))
>
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>


-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/