help-glpk
[Top][All Lists]

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

--