CPLEX tolerance usage

Answer

CPLEX provides the user three tolerances that apply directly to a computed solution, namely the feasibility, optimality, and integrality tolerances. These tolerances help CPLEX distinguish small values that have legitimate meaning in a model from those that arise from round off error in the model data or optimization calculations. The feasibility and optimality tolerances apply to linear and quadratic programs solved by one the CPLEX simplex methods. The CPLEX barrier methods use different tolerances to assess feasibility and optimality; those will be considered in a separate technote. The feasibility and optimality tolerances also apply indirectly to the CPLEX MIP algorithm for mixed integer linear and quadratic programs (since it typically uses one of the simplex methods to solve node relaxation problems), The feasibility tolerance specifies the amount by which a solution can violate its bounds and still be considered feasible. The optimality tolerance specifies the amount by which a reduced cost in a minimization problem can be negative (or equivalently, the amount by which the associated dual solution can violate dual feasibility). The integrality tolerance specifies the amount by which an integer restricted variable can violate its integrality restriction.

CPLEX uses default settings of 1e-6 for the feasibility and optimality tolerances, and 1e-5 for the integrality tolerance. Smaller values of these tolerances may yield more precise solutions. But, they may also increase the run time significantly, particularly if the tolerances are set below values that arise from round off error in the finite precision calculations CPLEX performs. Larger values of these tolerances may reduce run time and allow CPLEX to accept additional solutions, but that has little value if those solutions violate the intended meaning in the physical system being modelled. The default settings essentially assume that values below 1e-6 are either due to round off error, or are sufficiently small that they do not significantly change the optimization results. As long as this assumption holds true, one can leave these parameters at their defaults. For most models, these settings need not be altered. However, some noteworthy exceptions do exist.

• The model has large problem data coefficients that cannot be reduced by rescaling or reformulating the model. In such cases, round off error arising from these large coefficients may exceed the default feasibility, optimality and integrality tolerances. Leaving the tolerances at their defaults would cause the CPLEX LP and MIP algorithms to make decisions based on values associated with round off error rather than meaningful values derived from the model. This can result in both unnecessary excess run time, and in extreme cases unexpected results. In such cases, consider increasing the tolerances. Specifically, most computers on which CPLEX runs have a machine precision of roughly 1e-16. Problem data values of 1e+10 or higher can then multiply the machine precision to create round off error of 1e-6 or higher, enough to influence algorithmic decisions with the default feasibility and optimality tolerances. Therefore, a useful estimate for tolerance settings consists of taking the largest problem data coefficient and multiplying it by the machine precision. That provides a good estimate of the level of round off error that can potentially accumulate in calculations, even when the model is well conditioned. The feasibility tolerance should be at least one order of magnitude larger than that threshold. Keep in mind that rescaling or reformulating the model to avoid such large coefficients in the model typically provides a more robust approach; only consider changing tolerances when rescaling or reformulating is not possible.
• The model has small problem data values less than the default tolerance settings. In this case, the default settings will cause CPLEX to ignore coefficients that have meaning in the model. This could yield solutions that violate the intent of the model. Be sure to set the tolerances to be at least one order of magnitude smaller than the smallest meaningful problem data values. Also, make sure that the tolerances are set to values larger than the largest problem data value that occurs due to round off error. For example, consider the following feasibility problem.

By default, the CPLEX presolve will declare this model infeasible because it can use the variable bounds to determine that the left hand side of the constraint is at least 21 + 1.92e-6, which exceeds the right hand side by more than the default feasibility tolerance of 1e-6. However, with presolve off, different starting bases can lead to conclusions of feasibility or infeasibility. Specifically, if x2 is basic and x1 is nonbasic at its upper bound of 3, the resulting solution of x1 = 3, x2 = 1, and the slack on the constraint = 0 only violates feasibility by .00000008, and is considered feasible. In this case, the modeller should not just automatically adjust the feasibility tolerances. Rather, the modeller should assess whether the lower bound on x2 is supposed to be 1, or 1.00000008. In the former case, remove any obvious round off error from the problem data values, use a lower bound of 1, and leave the feasibility tolerances alone. In the latter case, a value of .00000008 has significance in the model, so the feasibility, optimality, and (if applicable) integrality tolerances should be set to values at least an order of magnitude smaller than .00000008.
• The model is ill conditioned. As with large values in the data, this can increase the order of magnitude of round off errors. Addressing the source of the ill conditioning directly constitute the preferred approach in such cases. But, if that really is not possible, increasing tolerances may provide an alternative. However, in this case a suitable threshold consists of the product of the machine precision, largest data coefficient, and the condition number. So, with a condition number of 1e+10, a largest data coefficient of 1e+4, and the typical machine precision of 1e-16, the threshold would be 1e-2, and a suitable tolerance setting would be 1e-1.

Note also the feasibility, optimality and integrality tolerances are used to define acceptable violations of feasibility or optimality for a solution. They are NOT designed to relax the feasibility or optimality conditions for the model. For example, with default tolerances, for the model