2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Welcome to OR SE. $\endgroup$
    – prubin
    Commented Jul 5, 2023 at 21:38

1 Answer 1

8
$\begingroup$

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).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.