User Tools

Site Tools


gams:how_large_should_big_m_be

Differences

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

Link to this comparison view

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 equationwhere Y(Jare binary variables: // +Binary variables allow us to formulate logical constraints. For exampleif ''​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(ix(i)) =lbigM*y; 
-   YBIN(J).. SUM(I,X(I,J)) =LM*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 NOTICEPRIVACY POLICY gams/how_large_should_big_m_be.txt · Last modified: 2020/05/19 09:59 by Michael Bussieck