CPLEX violating constraints (CPLEX - version 12.10 - C++)

Question

I'm a researcher and I have a problem with CPLEX. The .lp file containing the model includes the following constraint:

1000000000 x(1,12,0) + T(1,0) - T(12,0) <= 999999992

where x and T are decision variables. The solution returned is x(1,12,0) = 1, T(1,0) = 8, T(12,0) = 8, which violates the constraint. Can someone help? I appreciate it in advance.

Answer 1

Your problem is that double precision arithmetic is not perfectly accurate. Consequently, CPLEX (and pretty much every other solver) has various tolerance settings for when a double precision value is "close enough" to the target to let the solution be accepted. If you divide your constraint by 1e9 you get x(1,12,0) + ... <= 0.999999992. Substitute the alleged solution and the violation is 8e-09, which is well below the default tolerance of 1e-6 used by CPLEX.

You can reduce the feasibility tolerance parameter, but I don't advise it. Crank it too low and feasible solutions will suddenly become "infeasible" due to rounding error. The fundamental problem is that your model is poorly scaled. The constraint looks like a "big M" constraint, and "big M" constraints are notorious for causing numerical problems. If it is a "big M" constraint, your options include the following:

• find a smaller value for $M$ that gets the job done;
• find an alternate formulation that does not require $M$ (you could perhaps try indicator constraints, although CPLEX may internally reformulate them as "big M" constraints); or
• find an alternative way to solve the model (combinatorial Benders decomposition might be an option).