This example shows how to use the cut callback in the context of solving the noswot model. This is a relatively small model from the MIPLIB 3.0and MIPLIB 2003 test-sets, consisting only of 128 variables. This model is very hard to solve by itself. In fact, until the release of ILOG CPLEX version 6.5, it appeared to be unsolvable even after days of computation.

While it is now solvable directly, the computation time is still substantial. However, cuts can be derived, the addition of which make the problem solvable in a matter of minutes or seconds. These cuts, expressed as pseudo C++, look like this

x21 - x22 <= 0
x22 - x23 <= 0
x23 - x24 <= 0
2.08*x11 + 2.98*x21 + 3.47*x31 + 2.24*x41 + 2.08*x51 +
0.25*w11 + 0.25*w21 + 0.25*w31 + 0.25*w41 + 0.25*w51 <= 20.25
2.08*x12 + 2.98*x22 + 3.47*x32 + 2.24*x42 + 2.08*x52 +
0.25*w12 + 0.25*w22 + 0.25*w32 + 0.25*w42 + 0.25*w52 <= 20.25
2.08*x13 + 2.98*x23 + 3.47*x33 + 2.24*x43 + 2.08*x53 +
0.25*w13 + 0.25*w23 + 0.25*w33 + 0.25*w43 + 0.25*w53 <= 20.25
2.08*x14 + 2.98*x24 + 3.47*x34 + 2.24*x44 + 2.08*x54 +
0.25*w14 + 0.25*w24 + 0.25*w34 + 0.25*w44 + 0.25*w54 <= 20.25
2.08*x15 + 2.98*x25 + 3.47*x35 + 2.24*x45 + 2.08*x55 +
0.25*w15 + 0.25*w25 + 0.25*w35 + 0.25*w45 + 0.25*w55 <= 16.25

Of course the best way to solve the noswot model with these cuts is to simply add the cuts to the model before calling the optimizer. In case you want to copy and paste those cuts into a model in the Interactive Optimizer, for example, here are the same cuts expressed in the conventions of the Interactive Optimizer with uppercase variable names, as in the MPS data file:

X21 - X22 <= 0
X22 - X23 <= 0
X23 - X24 <= 0
2.08 X11 + 2.98 X21 + 3.47 X31 + 2.24 X41 + 2.08 X51 +
0.25 W11 + 0.25 W21 + 0.25 W31 + 0.25 W41 + 0.25 W51 <= 20.25
2.08 X12 + 2.98 X22 + 3.47 X32 + 2.24 X42 + 2.08 X52 +
0.25 W12 + 0.25 W22 + 0.25 W32 + 0.25 W42 + 0.25 W52 <= 20.25
2.08 X13 + 2.98 X23 + 3.47 X33 + 2.24 X43 + 2.08 X53 +
0.25 W13 + 0.25 W23 + 0.25 W33 + 0.25 W43 + 0.25 W53 <= 20.25
2.08 X14 + 2.98 X24 + 3.47 X34 + 2.24 X44 + 2.08 X54 +
0.25 W14 + 0.25 W24 + 0.25 W34 + 0.25 W44 + 0.25 W54 <= 20.25
2.08 X15 + 2.98 X25 + 3.47 X35 + 2.24 X45 + 2.08 X55 +
0.25 W15 + 0.25 W25 + 0.25 W35 + 0.25 W45 + 0.25 W55 <= 16.25

However, for demonstration purposes, this example adds the cuts, using a cut callback, only when they are violated at a node. This cut callback takes a list of cuts as an argument and adds individual cuts whenever they are violated by the current LP solution. Notice that adding cuts does not change the extracted model, but affects only the internal problem representation of the ILOG CPLEX object.

First consider the C++ implementation of the callback. In C++, the callback is implemented with these lines

ILOCUTCALLBACK3(CtCallback, IloExprArray, lhs, IloNumArray, rhs, IloNum, eps) { 
  IloInt n = lhs.getSize();
  for (IloInt i = 0; i < n; ++i) {
    IloNum xrhs = rhs[i];
    if ( xrhs < IloInfinity && getValue(lhs[i]) > xrhs + eps ) {
      IloRange cut;
      try {
        cut = (lhs[i] <= xrhs);
        add(cut).end();
        rhs[i] = IloInfinity;
      }
      catch (...) {
        cut.end();
        throw;
      }
    }
  }
}

This defines the class CtCallbackI as a derived class of IloCplex::CutCallbackI and provides the implementation for its virtual methods main and duplicateCallback. It also implements a function CtCallback that creates an instance of CtCallbackI and returns an IloCplex::Callback handle for it.

As indicated by the 3 in the macro name, the constructor of CtCallbackI takes three arguments, called lhs, rhs, and eps. The constructor stores them as private members to have direct access to them in the callback function, implemented as the method main. Notice the comma (,) between the type and the argument object in the macro invocation. Here is how the macro expands with ellipsis (...) representing the actual implementation

class CtCallbackI : public IloCplex::LazyConstraintCallbackI {
    IloExprArray lhs;
    IloNumArray rhs;
    IloNum eps;
public:
    IloCplex::CallbackI* duplicateCallback() const {
        return (new(getEnv()) CtCallbackI(*this));
    }
     CtCallbackI(IloEnv env, IloExprArray xx1, IloNumArray xx2, IloNum xx3) :
         IloCplex::LazyConstraintCallbackI(env), lhs(xx1), rhs(xx2), eps(xx3) {
    }
    void main();
};
IloCplex::Callback
CtCallback(IloEnv env, IloExprArray lhs, IloNumArray rhs, IloNum eps) {
    return (IloCplex::Callback(new(env) CtCallbackI(env, lhs, rhs, eps)));
}
void CtCallbackI::main() {
    ...
}

Similar macros are provided for other numbers of arguments ranging from 0 through 7 for all callback classes.

The first argument lhs is an array of expressions, and the argument rhs is an array of values. These arguments are the lefthand side and righthand side values of cuts of the form lhs  rhs to be tested for violation and potentially added. The third argument eps gives a tolerance by which a cut must at least be violated in order to be added to the problem being solved.

The implementation of this example cut-callback looks for cuts that are violated by the current LP solution of the node where the callback is invoked. It loops over the potential cuts, checking each for violation by querying the value of the lhs expression with respect to the current solution. This query calls getValue with this expression as an argument. This value is tested for violation of more than the tolerance argument eps with the corresponding righthand side value.

If a violation is detected, the callback creates an IloRange object to represent the cut: lhs[i]  rhs[i]. It is added to the LP by calling the method add. Adding a cut to ILOG CPLEX, unlike extracting a model, only copies the cut into the ILOG CPLEX data structures, without maintaining a notification link between the two. Thus, after a cut has been added, it can be deleted by calling its method end. In fact, it should be deleted, as otherwise the memory used for the cut could not be reclaimed. For convenience, method add returns the cut that has been added, and thus the application can call end directly on the returned IloRange object.

It is important that all resources that have been allocated during a callback are freed again before leaving the callback--even in the case of an exception. Here exceptions could be thrown when creating the cut itself or when trying to add it, for example, due to memory exhaustion. Thus, these operations are enclosed in a try block to catch all exceptions that may occur. In the case of an exception, the cut is deleted by a call to cut.end and whatever exception was caught is then rethrown. Rethrowing the exception can be omitted if you want to continue the optimization without the cut.

After the cut has been added, the application sets the rhs value to IloInfinity to avoid checking this cut for violation at the next invocation of the callback. Note that it did not simply remove the ith element of arrays rhs and lhs, because doing so is not supported if the cut callback is invoked from a parallel optimizer. However, changing array elements is allowed.

Also, for the potential use of the callback in parallel, the variable xrhs makes sure that the same value is used when checking for violation of the cut as when adding the cut. Otherwise, another thread may have set the rhs value to IloInfinity just between the two actions, and a useless cut would be added. ILOG CPLEX would actually handle this correctly, as it handles adding the same cut from different threads.

The function makeCuts generates the arrays rhs and lhs to be passed to the cut callback. It first declares the array of variables to be used for defining the cuts. Since the environment is not passed to the constructor of that array, an array of 0-variable handles is created. In the following loop, these variable handles are initialized to the correct variables in the noswot model which are passed to this function as the argument vars. The identification of the variables is done by querying variables names. Once all the variables have been assigned, they are used to create the lhs expressions and rhs values of the cuts.

The cut callback is created and passed to ILOG CPLEX in the line:

The function CtCallback constructs an instance of our callback class CtCallbackI and returns an IloCplex::Callback handle object for it. This is directly passed to function cplex.use.

The Java implementation of the callback is quite similar:

   public static class Callback extends IloCplex.CutCallback {
      double     eps = 1.0e-6;
      IloRange[] cut;
      Callback(IloRange[] cuts) { cut = cuts; }
    
      public void main() throws IloException {
         int num = cut.length;
         for (int i = 0; i < num; ++i) {
            if ( cut[i] != null ) {
               double val = getValue(cut[i].getExpr());
               if ( cut[i].getLB() > val+eps || val-eps > cut[i].getUB() ) {
                  add(cut[i]);
                  cut[i] = null;
               }
            }
         }
      }
   }

Instead of receiving expressions and righthand side values, the application directly passes an array of IloRange constraints to the callback; the constraints are stored in cut. The main loops over all cuts and evaluates the constraint expressions at the current solution by calling getValue(cut[i].getExpr). If this value exceeds the constraint bounds by more than eps, the cut is added during the search by a call to add(cut[i]) and cut[i] is set to null to avoid unneccessarily evaluating it again.

As for the C++ implementation, the array of cuts passed to the callback is initialized in a separate function makeCuts. The callback is then created and used to with the noswot cuts by calling.

   cplex.use(new Callback(makeCuts(cplex, lp)));

IloCplex provides an easier way to manage such cuts in a case like this, where all cuts can be easily enumerated before starting the optimization. Calling the methods cplex.addCut and cplex.addCuts allows you to copy the cuts to IloCplex before the optimization. Thus, instead of creating and using the callback, a user could have written:

as shown in example iloadmipex4.cpp in the distribution. During branch & cut, ILOG CPLEX will consider adding individual cuts to its representation of the model only if they are violated by a node LP solution in about the same way this example handles them. Whether this or adding the cuts directly to the model gives better performance when solving the model depends on the individual problem.

The complete program iloadmipex5.cpp appears online in the standard distribution at yourCPLEXinstallation/examples/src.The Java version is found in file AdMIPex5.java at the same location. The C#.NET implementation is in AdMIPex5.cs and the VB.NET implementation is in AdMIPex5.vb.