}
{composition-setup}
{section}
{column:width=300px}
{pagetree:root=Tutorial}
{column}
{column}
h1. 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|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2FCPLEX%2FUsrMan%2Ftopics%2Fdiscr_optim%2Fmip%2Fheuristics%2F42_heur_title_synopsis.html], to convert fractional solutions to heuristic ones. If you use a {{HeuristicCallback}}, the diagram below shows were it will be called.
{gliffy:name=heuristicCallbackCplex|align=left|size=L|version=4}
A few observations:
* The heuristic callback can be called multiple times at a node, once for each round of cuts added. In any event, it is going to be called a lot. If your heuristic is computationally expensive, be sure to keep this in mind.
* The heuristic callback seems not to be called if CPLEX finds a solution on its own. This seems consistent with only allowing the user to add at most one solution every time heuristic callback is invoked.
* (Not quite about heuristic callback...) For integer solutions generated by CPLEX's heuristics, it isn't clear what happens when CPLEX detects a violated constraint. Perhaps a clever example and the right print statement could determine this.
{warning:title=Warning}
Observe that any solution generated by a HeuristicCallback will not be checked against the lazy constraints. The programmer is responsible for ensuring feasibility.
{warning}
h1. 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|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.HeuristicCallback.html], 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.|
|{anchor:getValues} getValues|double[]|IloNumVar[] vars|Returns the solution values for vars at the current node.|
|{anchor:setSolution}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.|
h1. 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)|Advanced MIP Start and Christofides Approximation#approxTour], 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 {mathinline}\infty{mathinline}
* 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.
h1. Implementing HeuristicCallback for TSP
Add the utility method
{anchor:edgesAtOne}
{code}| Column |
|---|
Heuristic Solution Generation in CPLEXAt 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. | Gliffy Diagram |
|---|
| size | L |
|---|
| name | heuristicCallbackCplex |
|---|
|
A few observations: - The heuristic callback can be called multiple times at a node, once for each round of cuts added. In any event, it is going to be called a lot. If your heuristic is computationally expensive, be sure to keep this in mind.
- The heuristic callback seems not to be called if CPLEX finds a solution on its own. This seems consistent with only allowing the user to add at most one solution every time heuristic callback is invoked.
- (Not quite about heuristic callback...) For integer solutions generated by CPLEX's heuristics, it isn't clear what happens when CPLEX detects a violated constraint. Perhaps a clever example and the right print statement could determine this.
| 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 CPLEXHeuristicCallback 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 TSPWe 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
- 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. Implementing HeuristicCallback for TSPAdd the utility method
|
/**
* 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;
}
|
|
{code}
{{}} {{TspIpSolver}}
{code} TspIpSolver | Code Block |
|---|
private class ChristofidesCallback extends HeuristicCallback{
public ChristofidesCallback(){}
@Override
protected void main() throws IloException {
}
}
|
|
{code}
{{if(options.contains(Option.christofidesApprox))
|
\\}} {{}}
{} |
|---|
if(options.contains(Option.christofidesApprox)||options.contains(Option.christofidesHeuristic)){
christofides = new ChristofidesSolver<V,E>(graph,tspInstance.getEdgeWeights());
}
if(options.contains(Option.christofidesApprox)){//old code
System.out.println("Beginning Christofides...");
List<E> christofidesApproxTour = christofides.approximateBestTour(new HashSet<E>());
Set<E> submittedTour = new HashSet<E>(christofidesApproxTour);
double[] edgeVals = inverseEdgesUsed(submittedTour);
cplex.addMIPStart(edgeVariablesAsArray, edgeVals);
}
if(options.contains(Option.christofidesHeuristic)){//new code
cplex.use(new ChristofidesCallback());
}
|
|
{code}
{{}}
* [edgeVariablesAsArray|Adding Variables Objectives and Constraints#edgeVariablesAsArray] from {{TspIpSolver}}
* [|#getValues] {{HeuristicCallback}}
* [|#edgesAtOne] {{TspIpSolver}}
* [|Advanced MIP Start and Christofides Approximation#approxTour] {{}} * *
* [|Advanced MIP Start and Christofides Approximation#inverseEdgesUsed] {{TspIpSolver}}
* [|#setSolution] {{HeuristicCallback}}
{:=}_ _
{:=heuristicSolution}
{code}
@Override
protected void main() throws IloException {
double[] edgeVals = this.getValues(edgeVariablesAsArray);
Set<E> suggest = edgesAtOne(edgeVals);
List<E> approxTourAsList = christofides.approximateBestTour(suggest);
if(approxTourAsList == null){
return;
}
Set<E> 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);
}
{code}
{cloak}
{info}
To get rid of the message in red "found a loop" go to ChristofidesSolver.java and delete the line
{code}| Info |
|---|
To get rid of the message in red "found a loop" go to ChristofidesSolver.java and delete the line | Code Block |
|---|
System.err.println("found a loop");
|
|
|
{code}
{info}
h1. Profiling and Optimization
We Profiling and OptimizationWe won't |
* * {mathinline}O(|V|^3){mathinline}, where the bottleneck is solving a | , where the bottleneck is solving a non-bipartite |
{mathinline}O(|V|){mathinline} nodes. However, for anyone who is familiar with matching theory, they know that implementing non bipartite matching is incredibly difficult. Instead, we just solve an integer program to compute the matching.
Looking at the logs, we will ultimately see that while the heuristic is effective at first, as the algorithm continues, it becomes very rare that Christofides will be the incumbent (even after adding Two-Opt). In particular, once the "MIP relative gap" (the percentage going to zero in the node log file) is less than 1\%, it almost never happens. For this reason, we suggest that you use a back off function and stop attempting the Heuristic Callback entirely when the MIP relative gap falls below 1\%. Additionally, we know that if we suggest the same set of edges twice to our heuristic, it will produce the same result, so we can save time by caching the sets of edges we have already tested (at the cost of memory). Finally, we disable the HeuristicCallback until we have solved the root node (i.e. found a solution which passes the {{UserCutCallback}}, as if we are not yet branching then we have little to gain by finding a better incumbent. We adapt the given ChristofidesCallback implementation below:
{code}| nodes. However, for anyone who is familiar with matching theory, they know that implementing non bipartite matching is incredibly difficult. Instead, we just solve an integer program to compute the matching. Looking at the logs, we will ultimately see that while the heuristic is effective at first, as the algorithm continues, it becomes very rare that Christofides will be the incumbent (even after adding Two-Opt). In particular, once the "MIP relative gap" (the percentage going to zero in the node log file) is less than 1%, it almost never happens. For this reason, we suggest that you use a back off function and stop attempting the Heuristic Callback entirely when the MIP relative gap falls below 1%. Additionally, we know that if we suggest the same set of edges twice to our heuristic, it will produce the same result, so we can save time by caching the sets of edges we have already tested (at the cost of memory). Finally, we disable the HeuristicCallback until we have solved the root node (i.e. found a solution which passes the UserCutCallback, as if we are not yet branching then we have little to gain by finding a better incumbent. We adapt the given ChristofidesCallback implementation below: | Code Block |
|---|
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(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 = new HashSet<E>(approxTourAsList);
double submittedCost = tspInstance.cost(submittedTour);
System.out.println("heuristic solution cost: " + submittedCost);
double[] suggestedSolution = inverseEdgesUsed(submittedTour);
this.setSolution(edgeVariablesAsArray, suggestedSolution);
}
}
|
|
{code}
{{}}
{HTMLcomment:hidden}
{chart:type=bar|title=Run time TSPLIB instance d493|yLabel=Run Time (sec)|width=800|height=400|dataOrientation=vertical}
||Problem Name||w/o Christofides|| Advanced Start || Advanced Start + Heuristic||
|Deterministic, InfiniteWaiting|835.73|
|Randomized s-t, quadratic waiting|645.76| 561.79| 704.11|
|Randomized s-t, Exponential waiting| | |717.12|
|Randomized s-t, infinite waiting|491.26| | 464.32|
{chart}
{HTMLcomment}
{column}
{section} |