Yet another big-M problem, don’t blame Cplex

Hi,

I posted this message at the ILOG CPLEX Forum but I guess it could be
of interest here. I know that some people watch both forums, so I
apologize for the cross-post.

Any idea is appreciated. Could it be a problem on our cplex
installation ? We are using Ubuntu (one of the 2008 versions, I can
check exactly which one if anyone finds that information important).
---

Dear all,

I am really puzzled with the following:

I have an IP model. ( …) . If I solve this model (I am using Cplex 11.2, interative
optimizer, under Ubuntu ), I obtain an "optimal" integer solution with
cost 23 (…).

HOWEVER, I know of a solution with cost 21 ( … ). Indeed, if I
pass this solution to CPLEX as an mst file, Cplex starts using it as
the "Best Integer found" ( … ).

Am I missing anything ? Any help is appreciated,

It was suggested by another poster to use some clever but perfectly sensible options:

I verified this with CPLEX 11.0 (also on Ubuntu).  There are two ways (that I found) to get CPLEX to produce a correct solution (objective = 21) without the hot start:  turn off the presolver; or crank up the simplex feasibility tolerance (1e-9 worked for me).  Turning off the presolver seems to be the faster option.  (Disclaimer:  In both instances, I aborted the run after it found an integer-feasible solution with value 21 but before it exhausted the search tree, so it's possible one or the other option might have led to problems down the road.)

Cplex support in this forum adds more suggestions for even more exotic options (again they make perfect sense). However, I would approach this a little bit differently. First this problem is not purely a Cplex problem. Other solvers show the same problem. The reason lies actually in the formulation, which causes problems for relaxation-based branch & bound methods. It is always difficult to recognize the model structure from an LP file (please, use a proper modeling language) but there are big-M constants in the model with value 100,000. After I replaced all these instances by 10,000 Cplex shows the expected behavior: it does not stop with obj=23 but goes further to obj=21 on Ubuntu. So rather than tinkering with tolerances I would work on the model formulation and provide big-M values that are as small as possible. These values are often related to some upper bound. Experienced modelers (you can sometimes recognize them by their grey haires and thick glasses) will try to prevent using just a big arbitrary value like 1e5 but rather work on deducing a tight bound. Once you have proper formulation you will see that the model will behave better for any MIP solver. I would argue that a solver independent fix is better than using a solver specific option that works around the problem. (If you absolutely cannot provide a good value for your big-M’s you may want to look into Cplex’s indicator constraints).