Example: Controlling Cuts iloadmipex5.cpp
PREVIOUS
NEXT
| > Advanced Programming Techniques > Using Callbacks > Example: Controlling Cuts iloadmipex5.cpp |
Example: Controlling Cuts iloadmipex5.cpp |
INDEX
PREVIOUS
NEXT
|
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 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 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:
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 three cuts break symmetries among the machines, while the others capture minimum bounds on transaction costs. For more information about how these cuts have been found, see MIP Theory and Practice: Closing the Gap, available online at http://www.ilog.com/products/optimization/tech/researchpapers.cfm#MIPTheory.
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, 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 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 ILOG CPLEX object.
First consider the C++ version of the callback. In C++, the callback is implemented with the code:
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 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:
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. 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 a parameter. This value is tested for violation of more than the tolerance parameter eps with the corresponding right-hand 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 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 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 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:
Instead of receiving expressions and right-hand 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++ version, 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 here and online in the standard distribution.The Java version is found in file AdMIPex5.java at the same location.
| Copyright © 1987-2003 ILOG, S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |