Sometimes ILOG CPLEX finds a good integer solution early, but many additional nodes must be examined to prove that solution is optimal. You can speed up the process in such a case if you are willing to change the optimality tolerance. ILOG CPLEX supports two kinds of tolerance:

• Relative optimality tolerance guarantees that a solution lies within a certain percentage of the optimal solution.

• Absolute optimality tolerance guarantees that a solution lies within a certain absolute range of the optimal solution.

The default relative optimality tolerance is 0.0001. At this tolerance, the final integer solution is guaranteed to be within 0.01% of the optimal value. Of course, many formulations of integer or mixed integer programs do not require such tight tolerance, so requiring ILOG CPLEX to seek integer solutions that meet this tolerance in those cases is wasted computation. If you can accept greater optimality tolerance in your model, then you should change the parameter to control relative gap.

For example, to set the relative gap to one percent:

• In the Interactive Optimizer, use this command: set mip tolerance mipgap 0.01.

• In the Concert Technology Library, use the method IloCplex::setParam(EpGap, 0.01).

• In the Callable Library, use the routine CPXsetdblparam(env, CPX_PARAM_EPGAP, 0.01).

If, however, you know that the objective values of your problem are near zero, then you should change the absolute gap because percentages of very small numbers are less useful as optimality tolerance.

For example, to change the absolute gap:

• In the Interactive Optimizer, use this command : set mip tolerance absmipgap 3.0.

• In the Concert Technology Library, use the method IloCplex::setParam(EpAGap, 3.0).

• In the Callable Library, use the routine CPXsetdblparam(env, CPX_PARAM_EPAGAP, 3.0).

Table 5.10 summarizes the default value and range of absolute and relative gap parameters.

To speed up the proof of optimality, you can set objective difference parameters, both relative and absolute. Setting these parameters helps when there are many integer solutions with similar objective values. For example, in the Interactive Optimizer, this command set mip tolerances objdifference 100.0 makes ILOG CPLEX skip any potential solution with its objective value within 100.0 units of the best integer solution so far. Naturally, since this objective difference setting may make ILOG CPLEX skip an interval where the true integer optimum may be found, the objective difference setting weakens the guarantee of optimality. Table 5.11 summarizes the default value and range of relative and absolute objective difference parameters.

Cutoff parameters can also be helpful in restricting the search for optimality. If you know that there are solutions within a certain distance of the initial relaxation of your problem, then you can readily set the upper cutoff parameter for minimization problems and the lower cutoff parameter for maximization problems. For example:

• In the Interactive Optimizer, use this command set mip tolerances uppercutoff 5000 in a minimization problem, and this one set mip tolerance lowercutoff 200 in a maximization problem.

• When using the Component Libraries, set the parameters IloCplex::CutUp or IloCplex::CutLo or CPX_PARAM_CUTUP or CPX_PARAM_CUTLO and appropriate values.

Table 5.12 summarizes the default value and range of the lower and upper cutoff parameters.

When you set a MIP cutoff value, ILOG CPLEX searches with the same solution strategy as though it had already found an integer solution, using a node selection strategy that differs from the one it uses before a first solution has been found.