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.
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. |
getValue |
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 |
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:
- Create a queue of integer solutions.
- Create an
IncumbentCallbackthat 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
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!