Re: [Help-glpk] Linearising LP constraints and SOS2

[Michael Hennebry]

On Wed, 25 May 2011, Paolo Rossi wrote:

> 1)      How can I linearise a constraint of the type –
>
> x1 <= x2*bx1
>
> where bx1 is binary and x2 is a positive real which arises as a result of a
> linearisation through using SOS2 and  x1 is a positive real decision
> variable
x1 <= x2  if bx1==1
x1 <=  0  if bx1==0

If x2 has an upper bound, Ux2:
x1 <= x2*bx1 <= Ux2*bx1
x1 <= Ux2*bx1  // correct when bx1 in {0,1}, sufficient when bx1==0
x1 - Ux2*bx1 <= 0

If x1 has an upper bound, Ux1:
x1 <= x2 + M*(1-bx1)  for some large M
Clearly correct if bx1==1 .
If bx1==0:
x1 <= x2 + M
x1 - x2 <= M
Select M large enough to make it redundant, but not much larger:
M = Ux1 - 0 = Ux1
x1 <= x2 - Ux1*bx1 + Ux1  // correct when bx1 in {0,1}, sufficient when bx1=1
x1 - x2 + Ux1*bx1 <= Ux1

Note that when using a big-M method,
it is important to select a big-M as small as possible.
To emphasize this, I use the term small M method for such selections.
Even with the small-M method, the constraints tend to be rather loose.

--
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."