Cut Callback

> Advanced Programming Techniques > Advanced MIP Control Interface > Cut Callback

Cut Callback

The next example we consider is the user cut callback routine. The user calls CPXsetcutcallbackfunc to set a cut callback, and the user's callback routine is called at every viable node of the branch & cut tree. We refer the reader to admipex5.c for a detailed example.

A likely sequence of events once the user callback function is called is as follows. First, the routine calls CPXgetcallbacknodex to get the relaxation solution for the current node. It possibly also gathers other information about the problem (through CPXgetcallbacklp, CPXgetcallbackgloballb, etc.) It then calls a user separation routine to identify violated user cuts. These cuts are then added to the problem by calling CPXcutcallbackadd, and the callback returns. Local cuts, that is, cuts that apply to the subtree of which the current node is the root, can be added by the routine CPXcutcallbackaddlocal.

At this point, it is important to draw a distinction between the two different types of constraints that can be added through the cut callback interface. The first type is the traditional MIP cutting plane, which is a constraint that can be derived from other constraints in the problem and does not cut off any integer feasible solutions. The second is a "lazy constraint", which is a constraint that can not be derived from other constraints and potentially cuts off integer feasible solutions. Either type of constraint can be added through the cut callback interface.

As with the heuristic callback, the user can choose whether to work with presolved values or original values. 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 must set advanced presolve parameter CPX_PARAM_PRELINEAR to CPX_OFF (0). This parameter forbids certain presolve reductions that make translation from original values to presolved values impossible.

If the user adds any lazy constraints, the user must turn off dual presolve reductions (using the CPX_PARAM_REDUCE parameter). The user must think carefully about whether constraints added through the cut interface are implied by existing constraints, in which case dual presolve reductions may be left on, or whether they are not, in which case dual reductions are forbidden.

ILOG Concert Technology users should use the class IloCplex::LazyConstraintCallbackI when adding lazy constraints, and the class IloCplex::UserCutCallbackI when adding cutting planes. Dual reductions and/or non-linear reductions then will be turned off automatically.

One scenario that merits special attention is when the user knows a large set of cuts a priori. Rather than adding them to the original problem, the user may instead wish to add them only when 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 user callback that checks each cut from the user set at each node, adding those that are violated. The user can do this either by setting CPX_PARAM_MIPCBREDLP to CPX_OFF to work with the original problem in the cut callback, or by using the Advanced Presolve Interface to translate the cuts on the original problem to cuts on the presolved problem, and then use the presolved cuts in the cut callback.

Another, perhaps simpler alternative is to add the cuts or constraints to cut pools before optimization begins. Pools are discussed in User Cut and Lazy Constraint Pools.

PREVIOUS NEXT