Tuesday, September 13, 2011

Big-M and Scaling

I was working on a client MIP model that showed strange behavior: with Cplex and Mosek optimal values were found while Gurobi and Xpress reported the model to be infeasible. There were a few Big-M values in the model, in equations like:

Capture5

Some of the big M values were very large e.g. 99999999. The actual value of this M should be equal to the upper bound of x. Unfortunately x can assume very large values, something like $100,000,000. This meant we could only reduce the big M values by a small amount. With some trial and error we found some big M values that worked. Of course this was just a band-aid solution.

In the end we chose to scale the model by changing units for x. Instead of $ we now use millions of $. As a result the new big M values can just be M=100. As the model was rather complex we needed to spend half a day on this exercise. After this work, the model solved with all solvers without a problem.