Control Callbacks for IloCplex

Control callbacks allow you to control the branch & cut search during the optimization of MIP problems. The following control callbacks are available for IloCplex:

The node callback allows you to query and optionally overwrite the next node CPLEX will process during a branch & cut search.
The solve callback allows you to specify and configure the optimizer option to be used for solving the LP at each individual node.
The cut callback allows you to add problem-specific cuts at each node.
The heuristic callback allows you to implement a heuristic that tries to generate a new incumbent from the solution of the LP relaxation at each node.
The branch callback allows you to query and optionally overwrite the way CPLEX will branch at each node.

These callbacks are implemented as an extension of the diagnostic callback class hierarchy. This extension is shown below along with the macro names for each of the control callbacks (see Diagnostic Callbacks for a discussion of how macros and callback implementation classes relate).

Similar to class IloCplex::CallbackI, class IloCplex::ControlCallbackI is not provided for deriving user callback classes, but for defining the common interface for its derived classes. This interface provides methods for querying information about the current node, such as current bounds or solution information for the current node. See class IloCplex::ControlCallbackI in the ILOG CPLEX Reference Manual for more information.

Example: Controlling Cuts

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.0 test-set, consisting only of 128 variables. This model is very hard to solve by itself, in fact until the release of CPLEX 6.5 it appeared to be unsolvable even after days of computation.

While it is now solvable directly, the computation time is in the order of several hours on state-of-the-art computers. However, cuts can be derived, the addition of which make the problem solvable in a matter of minutes or seconds. These cuts are:

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

These cuts have been derived after interpreting the model as a resource allocation model on five machines with scheduling, horizon constraints and transaction times. The first tree cuts break symmetries among the machines, while the others capture minimum bounds on transaction costs. See "MIP: Theory and Practice -Closing the Gap" for more on how these cuts have been found.

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. However, for demonstration purposes, we will add the cuts, using a cut callback, only when they are violated at a node. This cut callback takes a list of cuts as parameter and adds individual cuts whenever they are violated with the current LP solution. Notice, that adding cuts does not change the extracted model, but affects only the internal problem representation of the CPLEX object.

This callback is implemented with the code:

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 makeClone(). 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 IloCtCallbackI takes three parameters, called lhs, rhs, and eps. The constructor stores them as private members to have direct access to them in the callback function, implemented as method main. Notice the comma (,) between the type and the argument object in the macro invocation. Here is how the macro expands:

class IloCtCallbackI : public IloCplex::FractionalCutCallbackI {
  IloExprArray lhs;
  IloNumArray  rhs;
  IloNum       eps;
public:
  IloCplex::CallbackI* makeClone() const {
    return (new (getEnv()) IloCtCallbackI(*this));
  }
  IloCtCallbackI(IloExprArray xlhs, IloNumArray xrhs, IloNum xeps)
    : lhs(xlhs), rhs(xrhs), eps(xeps)
  {}
  void main();
};

IloCplex::Callback IloCtCallback(IloEnv env,
                                 IloExprArray lhs,
                                 IloNumArray rhs,
                                 IloNum eps) {
  return (IloCplex::Callback(new (env) IloCtCallbackI(lhs, rhs, eps)));
}

void IloCtCallbackI::main() {
  ...
}

where the actual implementation code has been substituted with "...". Similar macros are provided for other numbers of parameters ranging from 0 through 7 for all callback classes.

The first parameter lhs is an array of expressions, and the parameter rhs is an array of values. These parameters are the left-hand side and right-hand side values of cuts of the form lhs <= rhs to be tested for violation and potentially added. The third parameter 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. We loop over the potential cuts, checking each for violation by querying the value of the lhs expression with respect to the current solution. This is done by calling getValue with this expression as a parameter. This is tested for violation of more than the tolerance parameter eps with the corresponding right-hand side value.

A numerical tolerance is always a wise thing to consider when dealing with any non-trivial model, to avoid certain logical inconsistencies that could otherwise occur due to numerical roundoff. Here we use the standard CPLEX simplex feasibility tolerance for this purpose, to insure some consistency with the way CPLEX is treating the rest of the model.

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 method add(). Adding a cut to CPLEX, unlike extracting a model, only copies the cut into the 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 we 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, we enclose these operations in a try block and catch all exceptions that may occur. In the case of an exception, we delete the cut by calling cut.end() and re-throw whatever exception was caught. Re-throwing the exception can be omitted if you want to continue the optimization without the cut.

After the cut has been added, we set the rhs value to IloInfinity to avoid checking this cut for violation at the next invocation of the callback. Note that we did not simply remove the ith element of arrays rhs and lhs, because this 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 ensures that we are using the same value 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. CPLEX would actually handle this correctly, as it handles adding the same cut from different threads.

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 parameter 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 CPLEX in the line:

cplex.use(CtCallback(env, lhs, rhs, cplex.getParam(IloCplex::EpRHS)));

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.

We should point out that 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, we could have written:

cplex.addCuts(makeCuts(var));

as shown in example iloadmipex7.cpp in the distribution. During branch & cut, 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.

Complete Program: iloadmipex5.cpp

The complete program, iloadmipex5.cpp, appears here or online in the standard distribution.

#include <ilcplex/ilocplex.h>
ILOSTLBEGIN

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;
      }
    }
  }
}

void
makeCuts(const IloNumVarArray vars, IloExprArray lhs, IloNumArray rhs) {
  IloNumVar x11, x12, x13, x14, x15;
  IloNumVar x21, x22, x23, x24, x25;
  IloNumVar x31, x32, x33, x34, x35;
  IloNumVar x41, x42, x43, x44, x45;
  IloNumVar x51, x52, x53, x54, x55;
  IloNumVar w11, w12, w13, w14, w15;
  IloNumVar w21, w22, w23, w24, w25;
  IloNumVar w31, w32, w33, w34, w35;
  IloNumVar w41, w42, w43, w44, w45;
  IloNumVar w51, w52, w53, w54, w55;
  IloInt num = vars.getSize();

  for (IloInt i = 0; i < num; ++i) {
     if      ( strcmp(vars[i].getName(), "X11") == 0 ) x11 = vars[i];
     else if ( strcmp(vars[i].getName(), "X12") == 0 ) x12 = vars[i];
     else if ( strcmp(vars[i].getName(), "X13") == 0 ) x13 = vars[i];
     else if ( strcmp(vars[i].getName(), "X14") == 0 ) x14 = vars[i];
     else if ( strcmp(vars[i].getName(), "X15") == 0 ) x15 = vars[i];
     else if ( strcmp(vars[i].getName(), "X21") == 0 ) x21 = vars[i];
     else if ( strcmp(vars[i].getName(), "X22") == 0 ) x22 = vars[i];
     else if ( strcmp(vars[i].getName(), "X23") == 0 ) x23 = vars[i];
     else if ( strcmp(vars[i].getName(), "X24") == 0 ) x24 = vars[i];
     else if ( strcmp(vars[i].getName(), "X25") == 0 ) x25 = vars[i];
     else if ( strcmp(vars[i].getName(), "X31") == 0 ) x31 = vars[i];
     else if ( strcmp(vars[i].getName(), "X32") == 0 ) x32 = vars[i];
     else if ( strcmp(vars[i].getName(), "X33") == 0 ) x33 = vars[i];
     else if ( strcmp(vars[i].getName(), "X34") == 0 ) x34 = vars[i];
     else if ( strcmp(vars[i].getName(), "X35") == 0 ) x35 = vars[i];
     else if ( strcmp(vars[i].getName(), "X41") == 0 ) x41 = vars[i];
     else if ( strcmp(vars[i].getName(), "X42") == 0 ) x42 = vars[i];
     else if ( strcmp(vars[i].getName(), "X43") == 0 ) x43 = vars[i];
     else if ( strcmp(vars[i].getName(), "X44") == 0 ) x44 = vars[i];
     else if ( strcmp(vars[i].getName(), "X45") == 0 ) x45 = vars[i];
     else if ( strcmp(vars[i].getName(), "X51") == 0 ) x51 = vars[i];
     else if ( strcmp(vars[i].getName(), "X52") == 0 ) x52 = vars[i];
     else if ( strcmp(vars[i].getName(), "X53") == 0 ) x53 = vars[i];
     else if ( strcmp(vars[i].getName(), "X54") == 0 ) x54 = vars[i];
     else if ( strcmp(vars[i].getName(), "X55") == 0 ) x55 = vars[i];
     else if ( strcmp(vars[i].getName(), "W11") == 0 ) w11 = vars[i];
     else if ( strcmp(vars[i].getName(), "W12") == 0 ) w12 = vars[i];
     else if ( strcmp(vars[i].getName(), "W13") == 0 ) w13 = vars[i];
     else if ( strcmp(vars[i].getName(), "W14") == 0 ) w14 = vars[i];
     else if ( strcmp(vars[i].getName(), "W15") == 0 ) w15 = vars[i];
     else if ( strcmp(vars[i].getName(), "W21") == 0 ) w21 = vars[i];
     else if ( strcmp(vars[i].getName(), "W22") == 0 ) w22 = vars[i];
     else if ( strcmp(vars[i].getName(), "W23") == 0 ) w23 = vars[i];
     else if ( strcmp(vars[i].getName(), "W24") == 0 ) w24 = vars[i];
     else if ( strcmp(vars[i].getName(), "W25") == 0 ) w25 = vars[i];
     else if ( strcmp(vars[i].getName(), "W31") == 0 ) w31 = vars[i];
     else if ( strcmp(vars[i].getName(), "W32") == 0 ) w32 = vars[i];
     else if ( strcmp(vars[i].getName(), "W33") == 0 ) w33 = vars[i];
     else if ( strcmp(vars[i].getName(), "W34") == 0 ) w34 = vars[i];
     else if ( strcmp(vars[i].getName(), "W35") == 0 ) w35 = vars[i];
     else if ( strcmp(vars[i].getName(), "W41") == 0 ) w41 = vars[i];
     else if ( strcmp(vars[i].getName(), "W42") == 0 ) w42 = vars[i];
     else if ( strcmp(vars[i].getName(), "W43") == 0 ) w43 = vars[i];
     else if ( strcmp(vars[i].getName(), "W44") == 0 ) w44 = vars[i];
     else if ( strcmp(vars[i].getName(), "W45") == 0 ) w45 = vars[i];
     else if ( strcmp(vars[i].getName(), "W51") == 0 ) w51 = vars[i];
     else if ( strcmp(vars[i].getName(), "W52") == 0 ) w52 = vars[i];
     else if ( strcmp(vars[i].getName(), "W53") == 0 ) w53 = vars[i];
     else if ( strcmp(vars[i].getName(), "W54") == 0 ) w54 = vars[i];
     else if ( strcmp(vars[i].getName(), "W55") == 0 ) w55 = vars[i];
  }
  lhs.add(x21 - x22);  rhs.add(0.0);
  lhs.add(x22 - x23);  rhs.add(0.0);
  lhs.add(x23 - x24);  rhs.add(0.0);
  lhs.add(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);  
rhs.add(20.25);
  lhs.add(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);  
rhs.add(20.25);
  lhs.add(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);  
rhs.add(20.25);
  lhs.add(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);  
rhs.add(20.25);
  lhs.add(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);  
rhs.add(16.25);
}


int
main(int argc, char** argv)
{
  IloEnv env;
  try {
    IloModel m;
    IloCplex cplex(env);

    IloObjective   obj;
    IloNumVarArray var(env);
    IloRangeArray  con(env);

    env.out() << "reading ../../../examples/data/noswot.mps" << endl;
    cplex.importModel(m, "../../../examples/data/noswot.mps", obj, var, con);

    env.out() << "constructing cut callback ..." << endl;
    
    IloExprArray lhs(env);
    IloNumArray  rhs(env);
    makeCuts(var, lhs, rhs);
    cplex.use(CtCallback(env, lhs, rhs, cplex.getParam(IloCplex::EpRHS)));

    env.out() << "extracting model ..." << endl;
    cplex.extract(m);

    env.out() << "solving model ...\n";
    cplex.solve();
    env.out() << "solution status is " << cplex.getStatus() << endl;
    env.out() << "solution value  is " << cplex.getObjValue() << endl;
  }
  catch (IloException& ex) {
    cerr << "Error: " << ex << endl;
  }
  env.end();
  return 0;
}