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.