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