Re: [Help-glpk] Problem representing c = min (a, b)

[Michael Hennebry]

On Thu, 18 Nov 2010, pradeep wrote:

> one stupid way may be is
> a+x=b+y
> u<=x
> M*u>=x
> v<=y
> M*v>=y
> u+v<=1
> c=a+(b-a)v
>
> u,v binary
> x,y integer >=0
> M - large integer

Too complicated, too many integer variables and too big an M.

The following constraints are valid and should be in any method:
c<=a
c<=b

c needs to be at least as big as one of them:
c >= a - Ma*bit
c >= b - Mb*(1-bit)
bit is the binary variable.
bit is 1 if b< a and 0 if a< b.
Ma and Mb should be big enough to work and not much bigger:
Ma*bit >= a - c
Valid values for Ma and Mb are upper bounds on a-c and b-c,
i.e. a-b and b-a, but one can sometimes do better.
If a< b, the value of Ma doesn't matter.
Ma can be any upper bound on a-c, i.e. a-b, given a>=b.
Likewise Mb can be any upper bound on b-c, i.e. b-a, given b>=a.
Ma and Mb need not be integer.

> On Thu, Nov 18, 2010 at 5:39 PM, dhiguero <address@hidden>wrote:
>
> > Hi everybody,
> >
> >  I am trying to represent a problem using linear programming and I got
> > stuck in how to model the minimum function. My problem is being c,a,b
> > variables of the problem (not params), I would like to declare c as c =
> > min(a,b). I have tried the approach of introducing a new binary variable B,
> > such as:
> >
> >  # c = min (a, b)
> >  (a-b)B >= 0
> >  (a-b)(1-B) <= 0
> >  c = aB+b(1-B)

--
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."