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.
A numeric tolerance is always a wise thing to consider when dealing with any nontrivial model, to avoid certain logical inconsistencies that could otherwise occur due to numeric round-off. Here the standard simplex feasibility tolerance serves this purpose, to make sure there is 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 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
.