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.

Full Size

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 \( \infty \)
• 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);
		}