Originally posted by: TimChippingtonDerrick

Not really looking for an 'answer', more an observation about an error message from CPLEX that I have never seen before.

In a MIP implementation using CPLEX from C# .Net, we had a problem some time ago with some numerical instabilities for some problem instances. This was 'cured' by turning on the numerical emphasis inside CPLEX. However, recently we have found some problem instances that are failing if we keep that numerical emphasis enabled, for example see below. We got around this by turning off the numerical emphasis setting. I know that we should really do some scaling or deeper analysis of the problem instances to avoid the issue, but the customer needed a quick fix and had no budget for the deeper analysis. This error message is not one I have seen before nor can I find any documentation of the error message.

        Nodes                                          Cuts/

   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap         Variable B NodeID Parent  Depth

 

      0     0  1.05074e+008     2                1.05074e+008    19520        

Integer feasible solution rejected --- infeasible on original model

      0     0  1.05074e+008     1                     Cuts: 9    19521        

Integer feasible solution rejected --- infeasible on original model

      0     2  1.05074e+008     1                1.05074e+008    19521                                  0             0

Elapsed time = 95.07 sec. (2833.60 ticks, tree = 0.01 MB, solutions = 0)

     50    52  1.05074e+008     1                1.05074e+008    19527         MissedDeliveryVa D     50     48     25

Integer feasible solution rejected --- infeasible on original model

     51    53  1.05074e+008     1                1.05074e+008    19527         MissedDeliveryVa U     51     50     26

Integer feasible solution rejected --- infeasible on original model

     52    54  1.05074e+008     1                1.05074e+008    19527         MissedDeliveryVa D     52     50     26

Integer feasible solution rejected --- infeasible on original model

     53    55  1.05074e+008     1                1.05074e+008    19527         MissedDeliveryVa U     53     52     27

Integer feasible solution rejected --- infeasible on original model

     54    56  1.05074e+008     1                1.05074e+008    19527         MissedDeliveryVa D     54     52     27

Integer feasible solution rejected --- infeasible on original model

This error message only appears in certain settings that ask CPLEX for increased care with respect to numerics.

Internally, CPLEX works with the presolved model. Solutions are found in the presolved model, stored there and translated later back to the original model (this translation is called "uncrush") in the very end.

Consider this example (things are in fact more complicted): Assume presolve performs an aggregation like

x = 10y

and thus eliminates x from the model. The presolved model will only have y. During uncrush any bound violation on y will multiply by a factor of 10 and will thus give an increased bound violation for x. Usually this is not a problem. However, if the bound violation for y is very close to the limit and you have a multiplier a lot larger than 10 then then an uncrush operation can result in the value for x being infeasible.

If you ask CPLEX for great numerical care then CPLEX immediately uncrushes each feasible solution it finds and checks it against the original model. If the uncrushed solution is found infeasible in the original model then the solution is discarded and the above message is issued.