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 linear constraints (here we assume the
x variables are non-negative):
How large 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:
Here, we can combine these two equations in one:
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:
Code: Select all
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:
Code: Select all
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;