I have been working on an applied problem with Big M constraints (due to several security issues in the company, I cannot write the formulation I am working on).

While solving with a partially LP-relaxed version of the problem and the original mixed integer linear program, I realized

  • With small (tight) big M, the LP relaxed version is far from the IP optimal.
  • With somewhat large big M, the LP relaxed version converges to the IP optimal (and also its solutions).
  • With an extremely large big M, the LP relaxed version indeed returns the IP optimal solution, while being SLOWER to solve.
  • Too tight big M makes IP solution time longer (I was expecting this to be helpful, since the tighter big-M value is, the tighter LP relaxation should be (in terms of convex hull approximation))

I was using Google OR tools + SCIP combination to solve the MILP model.

And I was wondering if there is any insights on this issue, from any perspective, e.g. polyhedral theory, convex optimization, etc.

There is no explicit question on this post, as I wanted to collect as much insights as possible, for my curiosity satisfaction.

  • 3
    $\begingroup$ Any chance that your "small (tight) big M" is so tight that it cuts off the optimal solution? $\endgroup$
    – prubin
    Commented Nov 1, 2022 at 2:59
  • $\begingroup$ @prubin Thanks for the comment. It seems like there is no chance for that... At least for the IP. From my point of view, the same conclusion should hold for its partial LP relaxation... $\endgroup$ Commented Nov 1, 2022 at 5:07
  • 3
    $\begingroup$ This seems like a rather strange behaviour. If you have bigM constraints of the form $\text{something on the LHS}\leq My$ where $y$ is binary, then larger $M$'s would lead to larger solution space, and as a consequence worse LP relaxation. $\endgroup$
    – Sune
    Commented Nov 1, 2022 at 9:43
  • $\begingroup$ @ApplicableMath, do you try using emphasis options in the SCIP setting to allow the solver automatically works on the problem? specifically in the pre-solving phase? $\endgroup$
    – A.Omidi
    Commented Nov 1, 2022 at 14:54
  • $\begingroup$ @SuneI agree. This is quiet strange, and I cannot understand why this would happen. The only thing I am guessing is this need to be somewhat related to some sort of heuristics that solver use (I am not sure if Google OR tools also applies some heuristics, or it is just a modeling language) $\endgroup$ Commented Nov 2, 2022 at 0:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.