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.

Full Size

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 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). 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

Full Size

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), 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:

To generate the constraints we will add, we use the same IloCplex instance that is solving the IP. Notice that IloCplex has all of these methods for getting variable values and adding constraints to the model. However, using these methods in the middle of a callback will cause an error. E.g., to make a \( \ge \) constraint, 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 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 \( 2^{|V|} \) 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 \( 2|V| \) edges in a solution, we can identify all such cuts in \( O(|V|){mathlinline} by partitioning the graph into connected components. Note however that each of the cuts constraints will have potentially \) O(|E|) \( \) nonzero coefficients.

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:

	private class IntegerCutCallback extends LazyConstraintCallback{

		public IntegerCutCallback(){}

		@Override
		protected void main() throws IloException {
			//fill this in
		}			
	}

Now you need to fill in the method main(), which should check to see if the current integer solution violates any lazy constraints, and if so, add those constraints. Here is an outline of one possible solution:

1. Get a double of all the edge variable values
2. Convert this into a Set<E> containing only those edges taking the value 1.0
3. Form a the subgraph only containing the above edges
4. Run connected components on this graph to get the set of sets of connected components, a Set<Set<V>>
5. If there is only one connected component, then the solution is feasible, so return.
6. Otherwise, for each connected component, get all edges in the original graph with one endpoint on each side of the cut, and add a constraint saying that at least two of these edges must be used
   Solution

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