Heuristic Solution Generation in CPLEX

At every node, CPLEX gives you the opportunity to attempt to convert a fractional solution into an integer solution with the HeuristicCallback. In addition, CPLEX periodically uses its own heuristics, as described in the manual, to convert fractional solutions to heuristic ones. If you use a HeuristicCallback, the diagram below shows were it will be called.

A few observations:

• The heuristic callback can be called multiple times at a node, once for each round of cuts added. In any event, it is going to be called a lot. If your heuristic is computationally expensive, be sure to keep this in mind.
• The heuristic callback seems not to be called if CPLEX finds a solution on its own. This seems consistent with only allowing the user to add at most one solution every time heuristic callback is invoked.
• (Not quite about heuristic callback...) For integer solutions generated by CPLEX's heuristics, it isn't clear what happens when CPLEX detects a violated constraint. Perhaps a clever example and the right print statement could determine this.

Implementing HeuristicCallback in CPLEX

HeuristicCallback works similarly to LazyConstraintCallback and UserCutCallback. Mathematically, you are passing CPLEX the following function:

• Input: A fractional solution to the LP relaxation of your problem, potentially after some lazy constraints, CPLEX generated cuts, or user cuts have been added
• Output: Either a single integral feasible solution or nothing

The Javadoc for HeuristicCallback can be found here, but we summarize the important methods in the table below (the interface is very similar to the other callbacks}):

Generating Integer Solutions for TSP

We now need a method that can somehow use the information from a fractional solution to TSP to create an integer solution. We use the following simple variation of Christofides algorithm, as described in the method approximateBestTour(Set<E> suggestedEdges), where we adjust the procedure for making a minimum spanning tree:

• For every edge in suggestedEdges, set the edge weight to zero.
• For every node with two incident edges in suggestedEdges, set all other weights to $//<![CDATA[ \begin{array}{l}\end{array} //]]>$
• If the set of suggested edges contains a cycle that is not a hamiltonian, fail (and return null)

The algorithm then uses this minimum spanning tree and continues with Christofides algorithm as normal. Note that every suggested edge will be in the MST, and any node two edges in the suggested edges will have no other edges in the MST. The purpose of this is to try and encourage the suggested edges to be included in the final tour. However, they still might be skipped in the shortcutting phase of the algorithm.

While mildly effective, this is not a standard method and is only being introduced to simply demonstrate an example of a Heuristic Callback. Understanding exactly how the heuristic works isn't terribly important.

For packing and covering problems, simple rounding schemes are possible, but generating integer solutions for TSP is much more difficult.

Implementing HeuristicCallback for TSP

Add the utility method

	/**
	 * 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;
	}

Create a blank template for HeuristicCallback at the bottom of TspIpSolver

	private class ChristofidesCallback extends HeuristicCallback{

		public ChristofidesCallback(){}

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

Replace the final if clause if(options.contains(Option.christofidesApprox)){...} of the TspIpSolver constructor with

		if(options.contains(Option.christofidesApprox)||options.contains(Option.christofidesHeuristic)){
			christofides = new ChristofidesSolver<V,E>(graph,tspInstance.getEdgeWeights());
		}
		if(options.contains(Option.christofidesApprox)){//old code
			System.out.println("Beginning Christofides...");			
			List<E> christofidesApproxTour = christofides.approximateBestTour(new HashSet<E>());
			Set<E> submittedTour = new HashSet<E>(christofidesApproxTour);
			double[] edgeVals = inverseEdgesUsed(submittedTour);			
			cplex.addMIPStart(edgeVariablesAsArray, edgeVals);			
		}
		if(options.contains(Option.christofidesHeuristic)){//new code
			cplex.use(new ChristofidesCallback());
		}

This will create the ChristofidesSolver object if either option is selected. Now, try and fill in ChristofidesCallback yourself! The following methods and fields should be helpful:

• edgeVariablesAsArray from TspIpSolver
• getValues() from HeuristicCallback
• edgesAtOne() from TspIpSolver
• approximateBestTour() from ChristofidesSolver, be sure the check the result is not null!
• inverseEdgesUsed() from TspIpSolver
• setSolution() from HeuristicCallback

Show Solution

		@Override
		protected void main() throws IloException {
			double[] edgeVals = this.getValues(edgeVariablesAsArray);
			Set<E> suggest = edgesAtOne(edgeVals);
			List<E> approxTourAsList = christofides.approximateBestTour(suggest);
			if(approxTourAsList == null){
				return;
			}
			Set<E> 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);
		}

System.err.println("found a loop");

Profiling and Optimization

We won't go into too much detail here, as in the step we add start applying Two-Opt to the solutions generated by Christofides in the HeuristicCallback, greatly increasing the value of the callback.

If you run the above code, you will immediately notice that we spend almost all of our time inside the HeuristicCallback and we make no progress towards reaching a solution. With a proper implementation, Christofides should run in $//<![CDATA[ \begin{array}{l}\end{array} //]]>$, where the bottleneck is solving a non-bipartite matching problem on $//<![CDATA[ \begin{array}{l}\end{array} //]]>$ nodes. However, for anyone who is familiar with matching theory, they know that implementing non bipartite matching is incredibly difficult. Instead, we just solve an integer program to compute the matching.

Looking at the logs, we will ultimately see that while the heuristic is effective at first, as the algorithm continues, it becomes very rare that Christofides will be the incumbent (even after adding Two-Opt). In particular, once the "MIP relative gap" (the percentage going to zero in the node log file) is less than 1%, it almost never happens. For this reason, we suggest that you use a back off function and stop attempting the Heuristic Callback entirely when the MIP relative gap falls below 1%. Additionally, we know that if we suggest the same set of edges twice to our heuristic, it will produce the same result, so we can save time by caching the sets of edges we have already tested (at the cost of memory). Finally, we disable the HeuristicCallback until we have solved the root node (i.e. found a solution which passes the UserCutCallback, as if we are not yet branching then we have little to gain by finding a better incumbent. We adapt the given ChristofidesCallback implementation below:

	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(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 = new HashSet<E>(approxTourAsList);
			double submittedCost = tspInstance.cost(submittedTour);
			System.out.println("heuristic solution cost: " + submittedCost);
			double[] suggestedSolution = inverseEdgesUsed(submittedTour);				
			this.setSolution(edgeVariablesAsArray, suggestedSolution);			
		}		
	}

With these heuristics, the performance with and without the HeuristicCallback is comparable. Next, we apply Two-Opt to get a big improvement in performance.