gams:how_large_should_big_m_be

Binary variables allow us to formulate logical constraints. For example, if `y`

is 0 then `sum(i, x(i))`

should also be 0. The |Big M method allows us to formulate this with with linear constraints (here we assume the `x`

variables are non-negative):

yBin.. sum(i, x(i)) =l= bigM*y;

How big should the scalar bigM be? Inexperienced user just use `scalar bigM /1e9/;`

and cause a lot of numerical trouble in the solver. Moreover, solver work with integer tolerances, e.g. |epInt in GAMS/CPLEX.

In general the answer should be to choose bigM as small as possible. For example, you might limit `x`

in the following way:

cap.. sum(i, x(i)) =l= maxCap;

Here, we can combine these two equations in one:

yBin.. sum(i, x(i)) =l= maxCap*y;

Which both sets bigM to the smallest possible value and reduces the number of constraints. It might not be always that simple to determine a small bigM but in almost all cases bigM can be calculated from the input data rather than setting it to a data independent insane large value.

There are situations where it is not possible to find a finite bigM. In these rare cases one can use another trick to accomplish the original task, i.e. formulating the constraint if `y`

is 0 then `sum(i, x(i))`

should also be 0. We can do this with a SOS1 constraint where the SOS set contains only two elements: the binary and a slack variable:

positive variable slack; yBin.. sum(i, x(i)) =e= slack;

and SOS1 set containing *(slack, 1-y)*. So if `y=0`

then slack has to be 0 (because `1-y`

is non-zero) and SOS1 only allows one member to be non-zero. The GAMS way of formulating SOS constraints does not make it easy for this example, here is how you can do it anyway:

positive variable slack; binary variable y; set s / one, two /; SOS1 variable s1(s); yBin.. sum(i, x(i)) =e= slack; defs11.. s1('one') =e= slack; defs12.. s1('two') =e= 1-y;

IMPRESSUM / LEGAL NOTICE
PRIVACY POLICY
gams/how_large_should_big_m_be.txt · Last modified: 2020/05/19 09:59 by Michael Bussieck