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.
|
Interestingly, the Heuristic callback can be called multiple times at a node, once for each round of cuts added. If your heuristic is computationally expensive, be sure to keep this in mind.
Warning
Observe that any solution generated by a HeuristicCallback will not be checked against the lazy constraints. The programmer is responsible for ensuring feasibility.
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}):
Method Name |
Return Type |
Arguments |
Description |
|---|---|---|---|
getValue |
double |
IloNumVar var |
Returns the solution value of var at the current node. |
getValues |
double[] |
IloNumVar[] vars |
Returns the solution values for vars at the current node. |
setSolution |
void |
IloIntVar[] vars, double[] vals |
Injects a solution to be used as the potential new incumbent. The injected solution is specified by providing solution values for all variables. If a user heuristic is successful in finding a new candidate for an incumbent, it can be passed to IloCplex by the method setSolution. IloCplex analyzes the solution and, if it is both feasible and better than the current incumbent, uses it as the new incumbent. A solution is specified using arrays vars and vals, where vals[i] specifies the solution value for vars[i]. Do not call this method multiple times. Calling it again overwrites any previously specified solution. |
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.