gams:how_large_should_big_m_be

This shows you the differences between two versions of the page.

gams:how_large_should_big_m_be [2007/08/10 11:06] 127.0.0.1 external edit |
gams:how_large_should_big_m_be [2020/05/19 09:59] (current) Michael Bussieck |
||
---|---|---|---|

Line 1: | Line 1: | ||

====== How large should BIG M be? ====== | ====== How large should BIG M be? ====== | ||

- | //How big should the constant M be in the equation, where Y(J) are binary variables: // | + | Binary variables allow us to formulate logical constraints. For example, if ''y'' is 0 then ''sum(i, x(i))'' should also be 0. The [[https://en.wikipedia.org/wiki/Big_M_method#Other_usage||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; |

- | YBIN(J).. SUM(I,X(I,J)) =L= M*Y(J); | + | 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. [[https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXepint||epInt]] in GAMS/CPLEX. |

- | // I said in my model: // | + | 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. | ||

- | SCALAR M /10000000000/ | + | 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; | ||

- | // but that causes problems. // | ||

- | |||

- | In general the answer should be as small as possible. Your model | ||

- | with the M of 1.0E10 could not be solved by any of the MIP solvers | ||

- | we tried out. It causes enormous scaling problems. However further | ||

- | on in your model you have | ||

- | |||

- | CAP(J).. SUM(I,X(I,J)) =L= MAXCAP; | ||

- | |||

- | We can combine these two equations in one: | ||

- | |||

- | YBIN(J).. SUM(I,X(I,J)) =L= MAXCAP*Y(J); | ||

- | |||

- | Which both sets M to the smallest possible value and reduces the | ||

- | number of constraints. | ||

- | |||

- | We have seen MIP models fail miserably when using a real big M. | ||

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