Example: controlling cuts iloadmipex5.cpp

Illustrates callbacks to control cuts in the C++ API.

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 and MIPLIB 2003 test-sets, consisting only of 128 variables. This model is very hard to solve by itself. In fact, until the release of 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

These cuts derive from an interpretation of the model as a resource allocation problem on five machines with scheduling, horizon constraints and transaction times. The first three cuts break symmetries among the machines, while the others capture minimum bounds on transaction costs. For more information about how these cuts were found, see the technical research report MIP Theory and Practice: Closing the Gap.

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 CPLEX object.

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

ILOUSERCUTCALLBACK3(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::UserCutCallbackI 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 a handle for it, an instance ofIloCplex::UserCutCallback.

As specified by the 3 in the macro name, the constructor of CtCallbackI takes three arguments: lhs, rhs, and eps (lefthand side, righthand side, and tolerance). 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 the 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, the 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 the cut itself is created or when the application tries 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 re-thrown. Re-throwing 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 at IloInfinity to avoid checking this cut for violation at the next invocation of the callback. Note that it did not simply remove the i ^th 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. 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. Variables are identified by querying their names. After 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 this line:

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

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

The Java implementation of the callback is quite similar:

   public static class Callback extends IloCplex.UserCutCallback {
      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) {
            IloRange thecut = cut[i];
            if ( thecut != null ) {
               double val = getValue(thecut.getExpr());
               if ( thecut.getLB() > val+eps || val-eps > thecut.getUB() ) {
                  add(thecut);
                  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 the tolerance of eps, the cut is added during the search by a call to add(cut[i]), and cut[i] is set to null in order to avoid unnecessarily 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.

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:

makeCuts(cuts, vars);
cplex.addUserCuts(cuts);

as shown in the example iloadmipex4.cpp in the distribution. During branch & cut, CPLEX considers 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 approach or adding the cuts directly to the model gives better performance during the solution of 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.