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.

{composition-setup}
{composition-setup

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.

double[]

IloNumVar[] vars

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

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

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.

Using IncumbentCallback in TSP

Our plan for IncumbentCallback is:

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

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

}
{section} 
{column:width=300px} 
{pagetree:root=Tutorial} 
{column} 
{column} 
h1. 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|Generating Integer Solutions and HeuristicCallback].  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.

{gliffy:name=incumbentCallback|align=left|size=L|version=1}

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.

h1. Implementing IncumbentCallback in CPLEX

The documentation for IncumbentCallback can be found [here|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.IncumbentCallback.html], 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.|
|{anchor:getValues}getValues|double[]|IloNumVar[] vars|Returns the values of variables in the array vars in the potential incumbent solution.|
|{anchor:getSolutionSource}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|

{warning:title=Warning}
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.
{warning}

Again, the method {{getValue()}} is signficantly slower than {{getValues()}} and should be avoided if many variables are to be checked. The class [SolutionSource|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.SolutionSource.html] 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.|

h1. Using IncumbentCallback in TSP

Our plan for {{IncumbentCallback}} is:
# Create a queue of integer solutions.
# Create an {{IncumbentCallback}} that views new incumbent solutions and takes the ones *not* generate by Christofides and registers them in the queue.
# In our existing {{HeuristicCallback}}, apply Two-Opt to integer solutions waiting in the queue and then submit them.

{warning:title=Warning}
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.
{warning}
{warning:title=Warning}
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}}!
{warning}
We will add our queue as a new field of {{TspIpSolver}}
{code}
	private Set<Set<E>> twoOptQueue;
{code}
We create the {{IncumbentCallback}} by extending it as in inner class of {{TspIpSolver}}
{code}
	private class QueueForTwoOpt extends IncumbentCallback{
		
		public QueueForTwoOpt(){}

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

{code}
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

{code

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

{code}
by the following lines

{code

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

{code}
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:

* [getSolutionSource()

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:

• searchNeighborhoodEdgeSet() from TwoOptSolver
• cost() from TspInstance
• clear() from Set
• inverseEdgesUsed() from TspIpSolver
• setSolution() from HeuristicCallback

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

Complete Source

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

|#getSolutionSource]
* [edgeVariablesAsArray|Adding Variables Objectives and Constraints#edgeVariablesAsArray] from {{TspIpSolver}}
* [getValues()|#getValues]
* [edgesUsed()|Adding Variables Objectives and Constraints#edgesUsed] from {{TspIpSolver}}

{toggle-cloak:id=queueSolution}_Toggle Solution of QueueForTwoOpt_
{cloak:id=queueSolution}
{code}
		protected void main() throws IloException {
			if(getSolutionSource() != IloCplex.SolutionSource.UserSolution){
				double[] incumbent = this.getValues(edgeVariablesAsArray);
				Set<E> tour = edgesUsed(incumbent);
				twoOptQueue.add(tour);				
			}
		}	
{code}
{cloak}

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:
* [searchNeighborhoodEdgeSet()|Local Search with Two-Opt#searchNeighborhoodEdgeSet] from {{TwoOptSolver}}
* cost() from {{TspInstance}}
* [clear()|http://docs.oracle.com/javase/6/docs/api/java/util/Set.html#clear()] from {{Set}}
* [inverseEdgesUsed()|Advanced MIP Start and Christofides Approximation#inverseEdgesUsed] from {{TspIpSolver}}
* [setSolution()|Generating Integer Solutions and HeuristicCallback#setSolution] from {{HeuristicCallback}}

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

{toggle-cloak:id=heuristicSolution}_Toggle Solution of ChristofidesCallback_
{cloak:id=heuristicSolution}
{code}
@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	
{code}
{cloak}

h1. Complete Source

If all else fails, your code should now look like this:
{toggle-cloak:id=completeSource}_Toggle Complete Source_
{cloak:id=completeSource}
{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;
	
	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);				
			}
		}		
	}
}
{code}
{cloak}
{column} 
{section}