}
{composition-setup}
{section}
{column:width=300px}
{pagetree:root=Tutorial}
{column}
{column}
h1. Default CPLEX
Callbacks allow user written code to be run at select points to monitor or influence the behavior of the CPLEX solver. Before modifying the behavior of the solver, lets understand exactly how the solver works. Below is a somewhat simplified picture of the algorithm CPLEX is using to solve an integer program.
{gliffy:name=defaultCplex|align=left|size=L|version=5}
The algorithm terminates when the node stack is empty, and the best incumbent found is the new solution. The first node pushed on, the LP relaxation of the original problem is often called the _root node_.
h1. Lazy Constraints in CPLEX
Lazy constraints, at a high level, are constraints that are only checked when a candidate for an integer solution has been identified. They can be added to the model at the start though the {{IloCplex}} method {{addLazyConstraint(IloRange range)}}, or they can be added on the fly with a {{LazyConstraintCallback}} (documentation [here|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.LazyConstraintCallback.html]). The {{LazyConstraintCallback}} provides a user implemented routine to take a new potential incumbent solution, determine any of the lazy constraints were violated, and if so, to add at least one of them to the model. Typically, you would want to use lazy constraints when you have a large number of constraints and you expect that few will be violated, as they allow you to have smaller LPs to solve when processing each node. In the case of the {{LazyConstraintCallback}}, you gain an additional advantage in that you do not need to explicitly store all of the lazy constraints in memory, which is critical for problems like TSP that have an exponential number of constraints. The downside is that you can waste a lot of time in branch and bound trying to generate integer solutions, only to find that they are actually infeasible. Regardless of whether {{addLazyConstraint(IloRange range))}} or a {{LazyConstraintCallback}} was used, the model becomes
{gliffy:name=lazyCplex|align=left|size=L|version=2}
h1. Using LazyConstraintCallback
Qualitatively, the idea of the class {{LazyConstraintCallback}} is that you pass CPLEX the function meeting the following specification:
* *Input:* an integral solution to your IP that is guaranteed to satisfy all constraints except the Lazy Constraints not yet added
* *Output:* a (potentially empty) list of violated constraints that is guaranteed to be nonempty if at least one constraint was violated
However, in Java, we do not pass functions (methods), we pass objects satisfying some interface specifying methods. This means we must create an object of type {{LazyConstraintCallback}}. The class is {{abstract}}, (see [Java introduction|Do you know Java]), so we must extend the class and fill in the abstract methods, where we will specify how to check for violated constraints. Since LazyConstraintCallback is an abstract class, it comes with some methods already implemented:
||Method Name||Return Type||Arguments||Description||
|getValue|double|IloNumVar var|Returns the solution value of var at the current node.|
|getValues|double[]|IloNumVar[] vars|Returns the solution values for vars at the current node.|
|add|IloRange|IloRange cut|Adds the constraint cut to the model. Assumes cut is linear.|
To generate the constraints we will add, we use the same {{IloCplex}} instance that is solving the IP.
{warning:title=Warning}
Notice that {{IloCplex}} has methods *by the same name* for getting variable values and adding constraints to the model. However, using these methods in the middle of a callback will cause an error.
{warning}
{info}
To make a {mathinline} \ge {mathinline} constraint in the middle of callback, be sure to call {{cplex.ge()}}, not {{cplex.addGe()}}, as discussed [here|Java and CPLEX#The Java Interface to CPLEX].
{info}
{warning:title=Warning}
The method {{getValue(IloNumVar v)}} is significantly slower than {{getValues(IloNumVar[] vars)}}, as [previously discussed for IloCplex|Java and Cplex#Performance Issues Reading Variable Values from CPLEX].
{warning}
It is convenient to make the new class an [inner class|http://docs.oracle.com/javase/tutorial/java/javaOO/nested.html] of the class where you are formulating your optimization problem, as then all of the fields which hold your problem data will be accessible. In particular, you will need access to the {{IloCplex}} instance as well as whatever data structure you have storing your {{IloIntVar}} instances.
h1. TSP Integer "Solutions" Satisfying the Degree Constraints
To accomplish our task of identifying violated cutset constraints for integer solutions that are ensured to satisfy all of the degree constraints, we need to understand the combinatorial structure of these solutions to avoid checking all {mathinline}2^{|V|}{mathinline} constraints. However, it is easy to see that in any (finite) graph where every node has degree two, the graph must be a collection of node disjoint cycles. When the graph is a single cycle, none of the cutset constraints will be violated, and when it contains multiple cycles, we will have a violated constraint for each cycle, as there will be no edges across the cut separating the nodes in the cycle from the rest of the graph. Thus given the {mathinline}|V|{mathinline} edges in a solution, we can identify all such cuts in {mathinline}O(|V|){mathinline} by partitioning the graph into connected components. Note however that each of the cuts constraints will have potentially {mathinline}O(|E|){mathinline} nonzero coefficients.
h1. Implementing LazyConstraintCallback for the Cutset Constraints
First, we will extend {{LazyConstraintCallback}} with an innner class inside {{TspIpSolver}}. At the bottom of {{TspIpSolver.java}} (but before the final '\}' ending the class), add the following code to extend {{LazyConstraintCallback}}:
{code}| Column |
|---|
Default CPLEXCallbacks allow user written code to be run at select points to monitor or influence the behavior of the CPLEX solver. Before modifying the behavior of the solver, lets understand exactly how the solver works. Below is a somewhat simplified picture of the algorithm CPLEX is using to solve an integer program. The algorithm terminates when the node stack is empty, and the best incumbent found is the new solution. The first node pushed on, the LP relaxation of the original problem is often called the root node. Lazy Constraints in CPLEXLazy constraints, at a high level, are constraints that are only checked when a candidate for an integer solution has been identified. They can be added to the model at the start though the IloCplex method addLazyConstraint(IloRange range), or they can be added on the fly with a LazyConstraintCallback (documentation here). The LazyConstraintCallback provides a user implemented routine to take a new potential incumbent solution, determine any of the lazy constraints were violated, and if so, to add at least one of them to the model. Typically, you would want to use lazy constraints when you have a large number of constraints and you expect that few will be violated, as they allow you to have smaller LPs to solve when processing each node. In the case of the LazyConstraintCallback, you gain an additional advantage in that you do not need to explicitly store all of the lazy constraints in memory, which is critical for problems like TSP that have an exponential number of constraints. The downside is that you can waste a lot of time in branch and bound trying to generate integer solutions, only to find that they are actually infeasible. Regardless of whether addLazyConstraint(IloRange range)) or a LazyConstraintCallback was used, the model becomes Using LazyConstraintCallbackQualitatively, the idea of the class LazyConstraintCallback is that you pass CPLEX the function meeting the following specification: - Input: an integral solution to your IP that is guaranteed to satisfy all constraints except the Lazy Constraints not yet added
- Output: a (potentially empty) list of violated constraints that is guaranteed to be nonempty if at least one constraint was violated
However, in Java, we do not pass functions (methods), we pass objects satisfying some interface specifying methods. This means we must create an object of type LazyConstraintCallback. The class is abstract, (see Java introduction), so we must extend the class and fill in the abstract methods, where we will specify how to check for violated constraints. Since LazyConstraintCallback is an abstract class, it comes with some methods already implemented: Method Name | Return Type | Arguments | Description |
|---|
getValue | double | IloNumVar var | Returns the solution value of var at the current node. | getValues | double[] | IloNumVar[] vars | Returns the solution values for vars at the current node. | add | IloRange | IloRange cut | Adds the constraint cut to the model. Assumes cut is linear. |
To generate the constraints we will add, we use the same IloCplex instance that is solving the IP. | Warning |
|---|
| Notice that IloCplex has methods by the same name for getting variable values and adding constraints to the model. However, using these methods in the middle of a callback will cause an error. |
| Info |
|---|
To make a constraint in the middle of callback, be sure to call cplex.ge(), not cplex.addGe(), as discussed here. |
It is convenient to make the new class an inner class of the class where you are formulating your optimization problem, as then all of the fields which hold your problem data will be accessible. In particular, you will need access to the IloCplex instance as well as whatever data structure you have storing your IloIntVar instances. TSP Integer "Solutions" Satisfying the Degree ConstraintsTo accomplish our task of identifying violated cutset constraints for integer solutions that are ensured to satisfy all of the degree constraints, we need to understand the combinatorial structure of these solutions to avoid checking all constraints. However, it is easy to see that in any (finite) graph where every node has degree two, the graph must be a collection of node disjoint cycles. When the graph is a single cycle, none of the cutset constraints will be violated, and when it contains multiple cycles, we will have a violated constraint for each cycle, as there will be no edges across the cut separating the nodes in the cycle from the rest of the graph. Thus given the edges in a solution, we can identify all such cuts in by partitioning the graph into connected components. Note however that each of the cuts constraints will have potentially nonzero coefficients.Implementing LazyConstraintCallback for the Cutset ConstraintsFirst, we will extend LazyConstraintCallback with an innner class inside TspIpSolver. At the bottom of TspIpSolver.java (but before the final '}' ending the class), add the following code to extend LazyConstraintCallback: |
private class IntegerCutCallback extends LazyConstraintCallback{
public IntegerCutCallback(){}
@Override
protected void main() throws IloException {
//fill this in
}
}
|
|
{code}
{{}} {{}}
{} |
|---|
if(options.contains(Option.lazy)){
cplex.use(new IntegerCutCallback());
}
|
|
{code}
{{}}
# {{}}
#
#
#
#
#
|| || ||||Description||
|getConnectedComponents|Set<Set<V>>|Set<E> includedEdges|Using the undirected graph for this instance, forms a subgraph using all of the vertices but only includedEdges, then computes and returns the set of connected components of the subgraph|
|{anchor:cutEdges}cutEdges|Set<E>|Set<V> cutVertices|Gets from the undirected graph from this instance all edges with exactly one endpoint in cutVertices.|
Here are a few more hints:
* We have already stored an array with all of the edge variables in {{TspIpSolver}}, {{edgeVariablesAsArray}}, which you can apply {{getValues()}} directly to.
* We already defined the method {{edgesUsed(double[] edgeValues)}} in the class {{TspIpSolver}} that takes in a double[] of the variable values of each edge, assuming they are in the same order as {{edgeVariablesAsArray}}, and returns edges where the variable value is (approximately) 1.0.
* The method {{integerSum}} from class {{Util}} as introduced in [Java style for CPLEX|Java style for CPLEX#Good Style] should be useful.
{toggle-cloak:id=LazySolution} _Solution_
{cloak:id=LazySolution|visible=false}
{code}
@Override
protected void main() throws IloException {
//fill this in
Set<E> edgesUsed = edgesUsed(this.getValues(edgeVariablesAsArray));
Set<Set<V>> connectedComponents = tspInstance.getConnectedComponents(edgesUsed);
if(connectedComponents.size() > 1){
for(Set<V> connectedComponent: connectedComponents){
this.add(cplex.ge(Util.integerSum(cplex, edgeVariables, tspInstance.cutEdges(connectedComponent)),2));
}
}
}
{code}
This solution is a little sloppy in that if there are only two connected components, the set of edges for their cut will be the same, but we will add the constraint twice. To get around this, you could cache the sets of edges in a new HashSet, to automatically filter out duplicates, then add all the constraints once all the edge sets have been determined. To think about: when there {mathinline}n>2{mathinline} connected components, are all of the constraints needed, or do any {mathinline}n-1{mathinline} of the constraints imply the final constraint?
{cloak}
h1. Testing your solution
We will use the [same test instance|Adding Variables Objectives and Constraints#Test Your Code] we used before we had implemented the cutset constraints. Thus the first integer solution found should cause our model to add the cut below and ultimately reach a final solution with objective value 24.
{gliffy:name=lazyCut|align=left|size=L|version=1}
The correct JUnit test has already been coded for you. If you run the JUnit test {{TspSolverTest}}, now the second test, {{testCutsetLazy()}}, should pass in addition to the first test {{testDegreeConstraints()}}.
h3. Implementation Note
Ideally, it would have been better to make a function that takes in the set of edges used and returns the cuts as a set of set of edges. Then we could test this function for a fixed input independently of CPLEX and solving the whole TSP. If the code is designed as a bunch of modular, independent parts that are independently tested and simply connected together, it is much easier to determine where errors are coming from. This idea is known as [Unit Testing|http://en.wikipedia.org/wiki/Unit_testing].
h1. Complete Source
If all else fails, {{TspIpSolver.java}} should currently look something like this:
{toggle-cloak:id=lazySource}_Show code_
{cloak:id=lazySource}
{code}
public class TspIpSolver<V,E> {
public static enum Option{
lazy,userCut, randomizedUserCut, christofidesApprox, christofidesHeuristic,twoOpt,incumbent;
}
private EnumSet<Option> options;
private IloCplex cplex;
private TspInstance<V,E> tspInstance;
private final ImmutableBiMap<E,IloIntVar> edgeVariables;
private ImmutableSet<E> edgesInOpt;
private double optVal;
private IloIntVar[] edgeVariablesAsArray;
public TspIpSolver(TspInstance<V,E> tspInstance) throws IloException{
this(tspInstance,EnumSet.of(Option.lazy, Option.userCut, Option.christofidesApprox, Option.christofidesHeuristic));
}
public TspIpSolver(TspInstance<V,E> tspInstance, EnumSet<Option> options) throws IloException{
this.options = options;
this.tspInstance = tspInstance;
this.cplex = new IloCplex();
UndirectedGraph<V,E> graph = tspInstance.getGraph(); //for convenience, we will be using this a lot
this.edgeVariables = Util.makeBinaryVariables(cplex, graph.getEdges());
edgeVariablesAsArray = edgeVariables.inverse().keySet().toArray(new IloIntVar[]{});
//the degree constraints
for(V vertex: graph.getVertices()){
cplex.addEq(Util.integerSum(cplex, edgeVariables,
graph.getIncidentEdges(vertex)), 2);
}
//the objective
cplex.addMinimize(Util.integerSum(
cplex, edgeVariables, graph.getEdges(),tspInstance.getEdgeWeights()));
if(options.contains(Option.lazy)){
cplex.use(new IntegerCutCallback());
}
}
public void solve() throws IloException{
if(!cplex.solve()){
throw new RuntimeException();
}
optVal = cplex.getObjValue();
edgesInOpt = ImmutableSet.copyOf(edgesUsed(cplex.getValues(edgeVariablesAsArray)));
cplex.end();
}
public ImmutableSet<E> getEdgesInOpt(){
return edgesInOpt;
}
public double getOptVal(){
return optVal;
}
/**
* assumes edgeVarVals[i] in {0,1}, up to some tolerance.
* @param edgeVarVals
* @return the edges where the variable takes the value one.
*/
private Set<E> edgesUsed(double[] edgeVarVals){
Set<E> ans = new HashSet<E>();
for(int e = 0; e < edgeVarVals.length; e++){
if(Util.doubleToBoolean(edgeVarVals[e])){
ans.add(edgeVariables.inverse().get(edgeVariablesAsArray[e]));
}
}
return ans;
}
private class IntegerCutCallback extends LazyConstraintCallback{
public IntegerCutCallback(){}
@Override
protected void main() throws IloException {
Set<E> edgesUsed = edgesUsed(this.getValues(edgeVariablesAsArray));
Set<Set<V>> connectedComponents = tspInstance.getConnectedComponents(edgesUsed);
if(connectedComponents.size() > 1){
for(Set<V> connectedComponent: connectedComponents){
this.add(cplex.ge(Util.integerSum(cplex, edgeVariables, tspInstance.cutEdges(connectedComponent)),2));
}
}
}
}
}
{code}
{cloak}
{column}
{section} | Description |
|---|
getConnectedComponents | Set<Set<V>> | Set<E> includedEdges | Using the undirected graph for this instance, forms a subgraph using all of the vertices but only includedEdges, then computes and returns the set of connected components of the subgraph | | cutEdges | Set<E> | Set<V> cutVertices | Gets from the undirected graph from this instance all edges with exactly one endpoint in cutVertices. |
Here are a few more hints: - We have already stored an array with all of the edge variables in
TspIpSolver, edgeVariablesAsArray, which you can apply getValues() directly to. - We already defined the method
edgesUsed(double[] edgeValues) in the class TspIpSolver that takes in a double[] of the variable values of each edge, assuming they are in the same order as edgeVariablesAsArray, and returns edges where the variable value is (approximately) 1.0. - The method
integerSum from class Util as introduced in Java style for CPLEX should be useful.
Solution | Cloak |
|---|
| visible | false |
|---|
| id | LazySolution |
|---|
| | This solution is a little sloppy in that if there are only two connected components, the set of edges for their cut will be the same, but we will add the constraint twice. To get around this, you could cache the sets of edges in a new HashSet, to automatically filter out duplicates, then add all the constraints once all the edge sets have been determined. To think about: when there connected components, are all of the constraints needed, or do any of the constraints imply the final constraint? |
Testing your solutionWe will use the same test instance we used before we had implemented the cutset constraints. Thus the first integer solution found should cause our model to add the cut below and ultimately reach a final solution with objective value 24. The correct JUnit test has already been coded for you. If you run the JUnit test TspSolverTest, now the second test, testCutsetLazy(), should pass in addition to the first test testDegreeConstraints(). Implementation NoteIdeally, it would have been better to make a function that takes in the set of edges used and returns the cuts as a set of set of edges. Then we could test this function for a fixed input independently of CPLEX and solving the whole TSP. If the code is designed as a bunch of modular, independent parts that are independently tested and simply connected together, it is much easier to determine where errors are coming from. This idea is known as Unit Testing. Complete SourceIf all else fails, TspIpSolver.java should currently look something like this:
Show code |
|