[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Michael Hennebry
Subject: Re: [Help-glpk] Linearising LP constraints and SOS2
Date: Wed, 25 May 2011 11:56:38 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]