Finding maximum of intvars

Help
jl251
2013-06-16
2013-06-16
  • jl251
    jl251
    2013-06-16

    Hi all,

    I have an optimization problem where I have several sets of IntVars S1, S2, etc.
    For each set, I would like to set
    max1 = Max(S1), max2 = Max(S2) etc.
    min1 = min(S1), min2 = min(S2) etc.

    And I would like to find the solution that minimizes (max1 + max2 + ...) - (min1 + min2 + ...)

    I know I can set an IntVar cost and a constraint (max1 + max2 + ...) = cost + (min1 + min2 + ...).

    This would work perfectly, but I don't know how to find the maximum of each set.

    Thank you!

     
  • kris
    kris
    2013-06-16

    Hi!

    Yes, JaCoP offers only minimization and therefore you must minimize negated cost (-cost). It can be achieved by defining variable minusCost using, for example constraint cost+minusCost=0.

    Best regards,
    /Kris

     
  • Hi,

    You need to impose proper constraints and create few extra variables. That's all.

    Therefore, for each set you will have to add two constraints. One Min constraint and one Max constraint. Check the JaCoP guide and section 3.3.7 that talks about those constraints. Now, with the help of those constraints you will have new variables that are set to the minimum and maximum value of the set of vars.

    Now, if you have those min and maximum value then you can use Sum constraint to compute the sums of maxs (smax) and the sum of mins (smin). Now, you have two variables smax and smin. If you impose the constraint XplusYeqZ(smin, cost, smax) then you impose the relationship (smin + cost = smax, which is smax - smin = cost) and now you can use cost as the optimization variable.

    Hope that helps.

    best,
    Radek

     
  • jl251
    jl251
    2013-06-16

    I see the relevant section:

    IntVar a = new IntVar(Store, "a", 1, 3);
    IntVar b = new IntVar(Store, "b", 1, 3);
    IntVar c = new IntVar(Store, "c", 1, 3);
    IntVar min = new IntVar(Store, "min", 1, 3);
    IntVar[] v = {a, b, c};
    Constraint ctr = new Min(v, min);
    Store.impose(ctr);

    So just to be clear, this defines min as the minimum of the set {a, b, c}?

     
  • kris
    kris
    2013-06-16

    Yes, it defines min as minimum value of variables a, b and c.
    /Kris