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.

incumbentCallback

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

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.

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

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

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

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

Complete Source

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

  • No labels