Incumbent Callbacks in CPLEX



CPLEX allows the user to view and optionally reject every new incumbent solution.  Although we are not using the reject functionality, beware that when solutions are rejected, the user is responsible for providing CPLEX with additional branching instructions.  We will use this functionality so we can view each new incumbent solution and apply Two-Opt to potentially find a better solution. Note that we have already applied Two-Opt to solutions generated by Christofides, so we only want to apply Two-Opt to natural integer solutions encountered in branch and bound and integer solutions generated by CPLEX's internal heuristics.



The incumbent callback does not actually allow us to set the value of a new solution, it only allows us to view the value of a new incoming incumbent.  New solutions are added in the previously discussed Heuristic Callback.  Thus to apply Two-Opt to our incumbent solutions, we must must queue them in a separate data structure and then use the process the queue inside the Heuristic Callback.  Our strategy is illustrated in the diagram below.





Observe that any solution going to our incumbent callback should satisfy all of the cutset constraints, as either it passed the Lazy constraints or it was generated by a Heuristic, which is required to produce feasible solutions.



Implementing IncumbentCallback in CPLEX



The documentation for IncumbentCallback can be found here, but below we summarize the necessary functionality for you.






Method Name


Return Type


Arguments


Description






getValue


double


IloNumVar var


Returns the value of the variable var in the potential incumbent solution.






getValues


double[]


IloNumVar[] vars


Returns the values of variables in the array vars in the potential incumbent solution.






getSolutionSource


int


 


 Returns a value that specifies where the potential incumbent was found, e.g. user heuristic, CPLEX heuristic, or integral LP.  Enocoding of return values is done by IloCplex.SolutionSource










The class IncumbentCallback inherits two similar sounding but functionally different monitoring methods, getIncumbentValue and getIncumbentValues.  When called from within an IncumbentCallback, they give the variable value(s) of the previous incumbent that our "potential incumbent" is about to replace.



Again, the method getValue() is signficantly slower than getValues() and should be avoided if many variables are to be checked. The class SolutionSource has three static fields for the different ways we can generate incumbents.






Field Name


Type


 Description






HeuristicSolution


int


The integral solution was found by a CPLEX internal heuristic.






NodeSolution


int


The integral solution was found as the solution to an LP-relaxation of a node in the search tree.






UserSolution


int


The integral solution was found by the user's heuristic callback function.








Using IncumbentCallback in TSP



Our plan for IncumbentCallback is:


    
	
  1. Create a queue of integer solutions.
    2. 
	
  2. Create an IncumbentCallback that views new incumbent solutions and takes the ones not generate by Christofides and registers them in the queue.
    3. 
	
  3. In our existing HeuristicCallback, apply Two-Opt to integer solutions waiting in the queue and then submit them.
    4. 







While organizationally, it would make more sense to make a second HeuristicCallback and then add both, you are only allowed to add one of each type of callback to a model.




Remember that each time main() is called on a HeuristicCallback, it is only allowed to add a single integer solution (attempts to add additional solutions will just overwrite previous attempts).  Take care when modifying our HeuristicCallback!


We will add our queue as a new field of TspIpSolver


	private Set<Set<E>> twoOptQueue;



We create the IncumbentCallback by extending it as in inner class of TspIpSolver


	private class QueueForTwoOpt extends IncumbentCallback{
		
		public QueueForTwoOpt(){}

		@Override
		protected void main() throws IloException {			
		}		
	}



Finally, we modify the constructor of TspIpSolver to initialize twoOptQueue and use both HeuristicCallback and QueueForTwoOpt when the Incumbent option is set (and fail if the TwoOpt option is not set, as we can't use our IncumbentCallback without TwoOpt.  Replace the last part of the constructor


		if(options.contains(Option.christofidesHeuristic)){
			cplex.use(new ChristofidesCallback());
		}



by the following lines


		if(options.contains(Option.christofidesHeuristic)||options.contains(Option.incumbent)){
			cplex.use(new ChristofidesCallback());
		}
		if(options.contains(Option.incumbent)){
			if(!options.contains(Option.twoOpt)){
				throw new RuntimeException("Incumbant callback requires that two opt option is on.");
			}
			twoOptQueue = new HashSet<Set<E>>();
			cplex.use(new QueueForTwoOpt());
		}



It would be reasonable to rename ChristofidesCallback to reflect that it is now doing double duty, but we will not bother.  Now that everything is wired together, we leave the hard work to you: fill in the main() method in QueueForTwoOpt to queue up integer solutions, and modify our existing ChristofidesCallback to clear the queue when incumbent option is set but to still run Christofides when the christofidesHeuristic option is set.



To fill in main() from QueueForTwoOpt, the following fields and methods should be helpful:





Toggle Solution of QueueForTwoOpt




		protected void main() throws IloException {
			if(getSolutionSource() != IloCplex.SolutionSource.UserSolution){
				double[] incumbent = this.getValues(edgeVariablesAsArray);
				Set<E> tour = edgesUsed(incumbent);
				twoOptQueue.add(tour);				
			}
		}	




Next, we need to process the solutions we queue up in ChristofidesCallback, our HeuristicCallback.  Here is one possible strategy: whenever we enter the callback, if the incumbent option is on and the queue of solutions is non-empty, apply two-opt to every solution in the queue.  If two-opt produces at least one non-null tour, submit the best found tour, and then return (to terminate main() so the result is not overwritten by Christofides).  If the incumbent option is off, or the queue of solutions is empty, or applying two-opt to each solution produces only null results, proceed as we previously did in attempting to apply the Christofides heuristic.



The following methods may be helpful:





Filling in this method is a little tricky, you may just want to read the solution.



Toggle Solution of ChristofidesCallback




@Override
		protected void main() throws IloException {
			if(options.contains(Option.incumbent) && twoOptQueue.size()>0){
				Set<E> bestTour = null;
				double bestTourVal = Double.MAX_VALUE;
				for(Set<E> tour : twoOptQueue){
					Set<E> improved = twoOpt.searchNeighborhoodEdgeSet(tour);
					if(improved != null){
						double tourVal = tspInstance.cost(improved);
						if(tourVal < bestTourVal){
							bestTourVal = tourVal;
							bestTour = improved;
						}
					}
				}
				twoOptQueue.clear();
				if(bestTour != null){
					System.out.println("improved CPLEX incumbent to: " + bestTourVal);
					double[] suggestedSolution = inverseEdgesUsed(bestTour);				
					this.setSolution(edgeVariablesAsArray, suggestedSolution);
					return;
				}
			}
			//replace old code with below
			if(!options.contains(Option.christofidesHeuristic) ||this.getMIPRelativeGap()< 0.01|| this.getNnodes64() == 0){
				return;
			}
			//... continue with old code	




Complete Source



If all else fails, your code should now look like this:

Toggle Complete Source




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;
	
	private ChristofidesSolver<V,E> christofides;
	private TwoOpt<V,E> twoOpt;
	private Set<Set<E>> twoOptQueue;
	
	
	
	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());
		}
		if(options.contains(Option.userCut)){
			cplex.use(new MinCutCallback());
			if(options.contains(Option.randomizedUserCut)){
				System.err.println("Warning, userCut and randomizedUserCut both selected, ignoring randomizedUserCut");
			}
		}
		else if(options.contains(Option.randomizedUserCut)){
			cplex.use(new RandomMinCutCallback());
		}		
		if(options.contains(Option.christofidesApprox)||options.contains(Option.christofidesHeuristic)){
			christofides = new ChristofidesSolver<V,E>(graph,tspInstance.getEdgeWeights());
		}
		if(options.contains(Option.twoOpt)){
			twoOpt = new TwoOpt<V,E>(tspInstance);
		}
		if(options.contains(Option.christofidesApprox)){
			System.out.println("Beginning Christofides...");			
			List<E> christofidesApproxTour = christofides.approximateBestTour(new HashSet<E>());
			Set<E> submittedTour;
			if(options.contains(Option.twoOpt)){
				submittedTour = twoOpt.searchNeighborhoodEdgeList(christofidesApproxTour);
			}
			else{
				submittedTour = new HashSet<E>(christofidesApproxTour);
			}
			double[] edgeVals = inverseEdgesUsed(submittedTour);			
			cplex.addMIPStart(edgeVariablesAsArray, edgeVals);			
		}
		if(options.contains(Option.christofidesHeuristic)||options.contains(Option.incumbent)){
			cplex.use(new ChristofidesCallback());
		}
		if(options.contains(Option.incumbent)){
			if(!options.contains(Option.twoOpt)){
				throw new RuntimeException("Incumbant callback requires that two opt option is on.");
			}
			twoOptQueue = new HashSet<Set<E>>();
			cplex.use(new QueueForTwoOpt());
		}
	}
	
	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;
	}
	
	/**
	 * Given a subset of the edges, produces a binary vector indicating which edges were included using the same ordering as edgeVariablesAsArray
	 * @param edgesUsed a subset of the set of edges in the grpah
	 * @return an array of zeros and ones where the ith entry corresponds to the ith edge variable from edgeVariablesAsArray
	 */
	private double[] inverseEdgesUsed(Set<E> edgesUsed){
		double[] edgeVals = new double[this.edgeVariablesAsArray.length];
		for(int i =0; i < edgeVals.length; i++){
			edgeVals[i] = edgesUsed.contains(edgeVariables.inverse().get(edgeVariablesAsArray[i])) ? 1 : 0;
		}
		return edgeVals;
	}
	
	private Map<E,Double> getNonZeroEdgeWeights(double[] edgeValues){
		Map<E,Double> edgeWeights = new HashMap<E,Double>();		
		for(int i = 0; i < edgeValues.length; i++){
			if(edgeValues[i] > Util.epsilon){
				edgeWeights.put(edgeVariables.inverse().get(edgeVariablesAsArray[i]), edgeValues[i]);
			}
		}
		return edgeWeights;
	}
	
	/**
	 * assumes  edgeVarVals[i] in [0,1].  Different than edgesUsed because an exception will not be thrown in
	 * 0 < edgeVarVals[i] < 1.
	 * @param edgeVarVals
	 * @return the edges where the variable takes the value one, up to some tolerance.
	 */
	private Set<E> edgesAtOne(double[] edgeVarVals){
		Set<E> ans = new HashSet<E>();
		for(int e = 0; e < edgeVarVals.length; e++){
	        if(edgeVarVals[e] >= 1-Util.epsilon){
	        	ans.add(edgeVariables.inverse().get(edgeVariablesAsArray[e]));
	        }
	    }
		return ans;
	}
	
	private class IntegerCutCallback extends LazyConstraintCallback{
		
		private double minCutVal;
		
		public IntegerCutCallback(){
			minCutVal = 1.99;
		}

		@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));
				}			
			}
		}			
	}
	
	private class MinCutCallback extends UserCutCallback{
		
		
		private BackOffFunction backOff;
		private double minCutVal;
		
		public MinCutCallback(){
			minCutVal = 1.99;
			this.backOff = new BackOffFunction.QuadraticWaiting();
		}

		@Override
		protected void main() throws IloException {
			//do not attempt to add any cutset constraints until CPLEX is done adding constraints
			if(!this.isAfterCutLoop()){
				return;
			}
			double[] edgeVals = this.getValues(edgeVariablesAsArray);
			Map<E,Double> edgeWeights = getNonZeroEdgeWeights(edgeVals);
			UndirectedGraph<V,E> graph = tspInstance.getGraph();
			MinCutSolver<V,E> minCutSolver = new MinCutSolver<V,E>(graph,edgeWeights);
			Set<Set<E>> cutSets = new HashSet<Set<E>>();
			Set<Set<V>> connectedComponents = minCutSolver.checkConnectedComponents();
			if(connectedComponents.size() > 1){				
				for(Set<V> connectedComponent: connectedComponents){
					cutSets.add(tspInstance.cutEdges(connectedComponent));				
				}
				System.out.println("trivial cuts exist, found " + cutSets.size());
			}
			else if(this.getNnodes64() == 0 || this.backOff.makeAttempt()){				
				V source = graph.getVertices().iterator().next();
				double best = Double.MAX_VALUE;
				System.out.print("looking for cut... ");
				for(V sink : graph.getVertices()){
					if(sink != source){
						Set<V> cutNodes = minCutSolver.computeMinCut(source, sink);
						Set<E> cutEdges = tspInstance.cutEdges(cutNodes);
						double cutVal = Util.calcSum(cutEdges,edgeWeights);
						best = Math.min(best, cutVal);
						if(cutVal < minCutVal){
							cutSets.add(cutEdges);
						}
					}
				}
				System.out.println("found " + cutSets.size() + " cuts, best " +	best);				
			}			
			for(Set<E> cutEdges: cutSets){
				this.add(cplex.ge(Util.integerSum(cplex, edgeVariables, cutEdges), 2));
			}
		}
	}
	
	private class RandomMinCutCallback extends UserCutCallback{
		
		private int numAttempts;
		private Random rand;
		private BackOffFunction backOff;
		private double minCutVal;
		
		public RandomMinCutCallback(){
			numAttempts = 20;
			rand = new Random();
			backOff = new BackOffFunction.QuadraticWaiting();
			minCutVal = 1.99;
		}

		@Override
		protected void main() throws IloException {
			//do not attempt to add any cutset constraints until CPLEX is done adding constraints
			if(!this.isAfterCutLoop()){
				return;
			}
			double[] edgeVals = this.getValues(edgeVariablesAsArray);
			Map<E,Double> edgeWeights = getNonZeroEdgeWeights(edgeVals);
			UndirectedGraph<V,E> graph = tspInstance.getGraph();
			MinCutSolver<V,E> minCutSolver = new MinCutSolver<V,E>(graph,edgeWeights);
			Set<Set<E>> cutSets = new HashSet<Set<E>>();
			Set<Set<V>> connectedComponents = minCutSolver.checkConnectedComponents();						
			if(connectedComponents.size() > 1){				
				for(Set<V> connectedComponent: connectedComponents){
					cutSets.add(tspInstance.cutEdges(connectedComponent));				
				}
				System.out.println("trivial cuts exist, found " + cutSets.size());
			}
			else if(this.getNnodes64() == 0 || this.backOff.makeAttempt()){
				double best = Double.MAX_VALUE;
				System.out.print("looking for cut... ");
				List<V> nodes = new ArrayList<V>(graph.getVertices());
				for(int i = 0; i <numAttempts; i++){				
					V source = nodes.get(rand.nextInt(nodes.size()));
					V sink = nodes.get(rand.nextInt(nodes.size()));
					if(source != sink){
						Set<V> cutNodes = minCutSolver.computeMinCut(source, sink);
						Set<E> cutEdges = tspInstance.cutEdges(cutNodes);
						double cutVal = Util.calcSum(cutEdges,edgeWeights);
						best = Math.min(best, cutVal);
						if(cutVal < minCutVal){
							cutSets.add(cutEdges);
						}
					}
				}
				System.out.println("found " + cutSets.size() + " cuts, best " + best);
			}
			
			for(Set<E> cutEdges: cutSets){
				this.add(cplex.ge(Util.integerSum(cplex, edgeVariables, cutEdges), 2));
			}						
		}		
	}
	
	private class ChristofidesCallback extends HeuristicCallback{

		private Set<Set<E>> previouslySuggested;
		private BackOffFunction backoff;
		
		public ChristofidesCallback(){
			previouslySuggested = new HashSet<Set<E>>();
			backoff = new BackOffFunction.QuadraticWaiting();
		}

		@Override
		protected void main() throws IloException {
			if(options.contains(Option.incumbent) && twoOptQueue.size()>0){
				Set<E> bestTour = null;
				double bestTourVal = Double.MAX_VALUE;
				for(Set<E> tour : twoOptQueue){
					Set<E> improved = twoOpt.searchNeighborhoodEdgeSet(tour);
					if(improved != null){
						double tourVal = tspInstance.cost(improved);
						if(tourVal < bestTourVal){
							bestTourVal = tourVal;
							bestTour = improved;
						}
					}
				}
				twoOptQueue.clear();
				if(bestTour != null){
					System.out.println("improved CPLEX incumbent to: " + bestTourVal);
					double[] suggestedSolution = inverseEdgesUsed(bestTour);				
					this.setSolution(edgeVariablesAsArray, suggestedSolution);
					return;
				}
			}
			if(!options.contains(Option.christofidesHeuristic) ||this.getMIPRelativeGap()< 0.01|| this.getNnodes64() == 0){
				return;
			}
			double[] edgeVals = this.getValues(edgeVariablesAsArray);
			Set<E> suggest = edgesAtOne(edgeVals);
			if(previouslySuggested.contains(suggest)){
				return;
			}
			else{
				previouslySuggested.add(suggest);
			}
			if(!backoff.makeAttempt()){
				return;
			}
			List<E> approxTourAsList = christofides.approximateBestTour(suggest);
			if(approxTourAsList == null){
				return;
			}
			Set<E> submittedTour;
			if(options.contains(Option.twoOpt)){
				submittedTour = twoOpt.searchNeighborhoodEdgeList(approxTourAsList);
				if(submittedTour == null){
					System.out.println("Two-Opt revisted same solution");
					return;
				}
			}
			else{
				submittedTour= new HashSet<E>(approxTourAsList);
			}			
			double submittedCost = tspInstance.cost(submittedTour);
			System.out.println("heuristic solution cost: " + submittedCost);
			double[] suggestedSolution = inverseEdgesUsed(submittedTour);				
			this.setSolution(edgeVariablesAsArray, suggestedSolution);			
		}		
	}
	private class QueueForTwoOpt extends IncumbentCallback{
		
		public QueueForTwoOpt(){}

		@Override
		protected void main() throws IloException {
			if(getSolutionSource() != IloCplex.SolutionSource.UserSolution){
				double[] incumbent = this.getValues(edgeVariablesAsArray);
				Set<E> tour = edgesUsed(incumbent);
				twoOptQueue.add(tour);				
			}
		}		
	}
}