Cut callback

Describes special considerations of the cut callback.

The next example to consider is the user cut callback routine. The user calls CPXsetusercutcallbackfunc to set a user cut callback. Then CPLEX calls the user's callback routine at every viable node of the branch & cut tree. See the sample admipex5.c for a detailed demonstration.

A likely sequence of events after the user cut callback function is called goes like this. First, the routine calls CPXgetcallbacknodex to get the relaxation solution for the current node. It possibly also gathers other information about the problem (through such routines as CPXgetcallbacklp, CPXgetcallbackgloballb, and others). It then calls a user separation routine to identify violated user cuts. These cuts are then added to the problem by a call to CPXcutcallbackadd, and the callback returns. You can add local cuts, that is, cuts that apply to the subtree of which the current node is the root, by means of the routine CPXcutcallbackaddlocal.

CPLEX supports two rather different types of constraints that might both be regarded as cuts in some sense.

• The first type is the conventional MIP cutting plane. A MIP cutting plane is a constraint that can be derived from other constraints in the problem. Equally important, a MIP cutting plane does not cut off any integer feasible solutions. This type is known as a user cut in CPLEX. To add a MIP cutting plane (that is, a user cut), use the routine CPXsetusercutcallbackfunc.

• The second type is a lazy constraint that is, a constraint that can not be derived from other constraints and potentially cuts off integer feasible solutions. In other words, a lazy constraint changes the feasible region of the model. To add a lazy constraint, use the routine CPXsetlazyconstraintcallbackfunc.

As with the heuristic callback, the user can choose whether to work with presolved values or original values of the model. If the user chooses to work with original values, a few parameters must be modified:

• If the user adds only cutting planes to the original problem, the user can set the advanced presolve linear reduction switch (CPX_PARAM_PRELINEAR) to CPX_OFF (0). This parameter forbids certain presolve reductions that make translation from original values to presolved values impossible. What happens if the user does not turn off this parameter? If the user chooses to leave this parameter on, it can happen that certain user cuts cannot be transformed into the presolved-problem space; in that case, a call to the routine CPXcutcallbackadd to add such a cut returns the error CPXERR_PRESLV_CRUSHFORM. As user cuts are optional for solving a MIP problem, the user can safely ignore this error status code. However, the user must realize that the cut was not added to the LP relaxation of the problem.

• If the user adds any lazy constraints, CPLEX detects the lazy constraints and automatically turns off dual presolve reductions. That is, CPLEX resets two parameters. CPLEX sets the primal and dual reduction type CPX_PARAM_REDUCE to the value CPX_PREREDUCE_PRIMALONLY. CPLEX sets the presolve linear reduction switch CPX_PARAM_PRELINEAR to off. Consequently, the user must think carefully about whether constraints added through the cut interface are implied by existing constraints (in which case, these additions are user cuts and thus nonlinear reductions and dual presolve reductions can be left on) or whether they are not (in which case, these additions are lazy constraints and thus nonlinear reductions and dual presolve reductions are forbidden).

Concert Technology users use the class IloCplex::LazyConstraintCallbackI when adding lazy constraints. CPLEX then automatically turns off dual reductions and nonlinear reductions.

Concert Technology users use the class IloCplex::UserCutCallbackI when adding cutting planes. In this case, CPLEX does not adjust parameters because these parameter changes are not required for user cuts.

One scenario that merits special attention is when the user knows a large set of cuts because of prior knowledge. Rather than adding them to the original problem one by one, the user can add them only when they are violated. The CPLEX advanced MIP control interface provides more than one mechanism for accomplishing this. The first and probably most obvious at this point is to install a lazy constraint callback that checks each of them at each node, adding those that are violated.

Another, perhaps simpler alternative is to add them to a pool of user cuts or lazy constraints before optimization begins. The topic User-cut and lazy-constraint pools discusses pools in greater detail.