Re: [Help-glpk] Modeling max-min or disjunction

[Jeroen Janssen]

Thank you for your help.  For future reference by other people searching this 
mailing list, I'll post the solution here (I received this solution by e-mail 
from Timo Van Donselaar):

For a >= min(b,c), which is equivalent to a >= b or a >= c we get:

var delta1, binary;
var delta2, binary;
var a,
param b;
param c;

constr1: delta1+delta2>=1;
constr2: a-b >= -M*(1-delta1);
constr3: a-c >= -M*(1-delta2);

Where M is a big number (in my case a and b were numbers in [0,1], so M 
doesn't need to be so big I guess).  The case for max follows then in much 
the same manner:

var delta3, binary;
var delta4, binary;
param d;
param e;

constr4: delta3+delta4 >= 1;
constr5: a-d <= M*(1-delta3);
constr6: a-e <= M*(1-delta4);

Kind regards,
Jeroen Janssen.


On Thursday 10 July 2008 21:06:06 Andrew Makhorin wrote:
> > For a project I'm working on, I need to model things like
> > a >= min(b,c) and a <= max(b,c)
> > in a linear program/MIP program. Obviously this is identical to
> > modelling a >= b or a >= c and likewise for the maximum, but as glpsol
> > does not support disjunctive programming, I am looking for a way to
> > model these type of things in MIP. I have read that there are methods
> > for transforming disjunctive programs into MIP programs, but I was not
> > able to find a document describing this (or the conditions under which
> > it is possible) online. So hopefully someone on this mailing list can
> > point me in the right direction?
>
> For modeling min and max see:
> http://lists.gnu.org/archive/html/help-glpk/2007-08/msg00026.html
>
> For modeling disjunctive constraints see:
> http://lists.gnu.org/archive/html/help-glpk/2007-08/msg00028.html