Monday, February 18, 2013

big-M

In http://bob4er.blogspot.com/2013/02/the-big-m.html a big-M constraint (my favorite subject!) is formed like:

xij ≤ [1.1 min (ai, bj)] zij

I don’t really understand the reason for the fudge factor 1.1. I would write this as:

image

Here M(i,j) is an implied upper bound on x(i,j). The feasibility tolerances already add a “fudge factor”, and I can not see why I should add another one.

In some cases big-M’s need to be much smaller than this post suggests. In http://yetanothermathprogrammingconsultant.blogspot.com/2009/03/yet-another-big-m-problem-dont-blame.html we see M=1e5 is not good enough, and reducing M to 1e4 helped solve Cplex the problem correctly.