Can not reach MIP Gap when solving MILP with big M formulation

[Zhe Yu]

Hello Professor Löfberg,

I was trying to linearize the product of a continuous variable and binary variable. Partial objective function containing the bilinear terms is given below:

max - (w_bar + w_plus*z_w_plus - w_minus*z_w_minus) * pi + (L_bar + L_plus * z_l_plus - L_minus * z_l_minus) * delta

• z_w_plus, z_w_minus, z_l_plus and z_l_minus are binary variables. 
  
• pi is a non-negative continuous variable.
  
• delta is a free variable.
  
• Others are constants.

Therefore, I have 4 product pairs needed to be linearized. I tried to implement by using either big M method or implies implications and set different values for M. However, the optimization process took forever without reaching the default Gurobi MIP gap (1e-4). 

Please find attached for the Matlab code. 

Thank you very much for your time if you could offer some help!

[Johan Löfberg]

https://yalmip.github.io/slowmilp

(btw, note that your code can be simplified a lot as you can remove most of your for loops, and simply write   constraint = [constraint, psi_l_plus <= BM*z_l_plus]; etc)

[Zhe Yu]

Hello profess Löfberg, thank you for your quick response. 

There is 576 binary variables in my code so I understand why it took so long. If that is the case, should I just manually modify either the TimeLimit or MIPGap in Gurobi setting so the optimization can terminate earlier? 

Besides, if I want to use implies implications, how should I set the upper bound and lower bound for that continuous variables if I do not know them beforehand? 

Thanks!

[Johan Löfberg]

Well, you have to accept a sub-optimal solution by increasing the gap tolerances etc, or much better is to come up with a model which has better combinatorial properties (and that's an art)

You select bounds by using domain knowledge. If you build a car, you know the car is >=0 meters, and any sensible solution is <= 10 meters

[Zhe Yu]

Thanks again!