h1. TSPLIB performance
Run your new code (through main, with both the lazy and userCut options) on the same TSPLIB problems as before and compare the performance. My running times were
{chart:type=bar|title=Run time on TSPLIB instances|yLabel=Run time (sec)|width=600|height=400|displayData=after}
||Strategy||eil51||bier127||ch130||ch150||d198||
|Without User Cuts|0.13|1.23|1.96|5.01|8.58|
|With User Cuts|0.40|3.76|12.52|83.62|103.93|
{chart}
We see that the running time increased on every example! What is going on here? Lets add a few timely print statements to our {{UserCutCallback}} to try and better understand how the performance is worse.
{code}
V source = graph.getVertices().iterator().next();
double best = Double.MAX_VALUE;
System.out.print("looking for cut... ");
for(V sink : graph.getVertices()){
if(sink != source){
Set<V> cutNodes = minCutSolver.computeMinCut(source, sink);
Set<E> cutEdges = tspInstance.cutEdges(cutNodes);
double cutVal = Util.calcSum(cutEdges,edgeWeights);
best = Math.min(best, cutVal);
if(cutVal < minCutVal){
cutSets.add(cutEdges);
}
}
}
System.out.println("found " + cutSets.size() + " cuts, best " + best);
{code}
Lets run the code again on d198 and take a closer look at the output.
{noformat}
Reading file d198... complete!
Building problem... complete!
Solving TSP...Lazy constraint(s) or lazy constraint callback is present.
Disabling dual reductions (CPX_PARAM_REDUCE) in presolve.
Disabling non-linear reductions (CPX_PARAM_PRELINEAR) in presolve.
Tried aggregator 1 time.
Presolve time = 0.01 sec. (9.91 ticks)
Warning: Control callbacks may disable some MIP features.
Probing time = 0.01 sec. (3.35 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branch-and-cut.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.01 sec. (13.55 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap Variable B NodeID Parent Depth
0 0 11793.0000 28 11793.0000 282
0 0 11823.0000 18 Cuts: 9 291
0 0 11837.0000 21 Cuts: 5 295
0 0 11845.1667 10 Cuts: 5 303
0 0 11846.0000 10 Cuts: 5 306
0 0 11846.7500 14 Cuts: 3 309
0 0 11848.0000 8 Cuts: 3 311
0 0 11858.0000 10 Cuts: 5 317
0 0 11860.8750 18 Cuts: 5 323
0 0 11869.5000 12 Cuts: 3 329
0 0 12442.0000 22 Cuts: 3 331
0 0 12450.0000 20 Cuts: 8 337
0 0 12456.0000 14 Cuts: 5 351
0 0 12461.5000 14 Cuts: 6 358
0 0 12462.5000 22 Cuts: 3 367
0 0 12463.0000 14 ZeroHalf: 1 370
looking for cut... found 2 cuts, best 0.0
0 0 12463.0000 22 User: 2 372
looking for cut... found 1 cuts, best 0.0
0 0 12463.0000 33 User: 1 374
looking for cut... found 3 cuts, best 0.0
0 0 12468.5000 20 User: 3 389
looking for cut... found 3 cuts, best 0.0
0 0 12468.5000 20 User: 3 392
looking for cut... found 3 cuts, best 0.0
0 0 12469.7500 60 User: 3 399
looking for cut... found 2 cuts, best 0.0
0 0 12471.0000 40 User: 2 401
looking for cut... found 3 cuts, best 0.0
0 0 12479.5000 44 User: 3 413
looking for cut... found 3 cuts, best 0.0
0 0 12494.0000 49 User: 3 428
looking for cut... found 1 cuts, best 0.0
0 0 12494.0000 49 User: 1 429
looking for cut... found 3 cuts, best 0.0
0 0 12980.0000 34 User: 3 449
looking for cut... found 4 cuts, best 0.0
0 0 12981.2500 61 User: 4 454
looking for cut... found 8 cuts, best 0.0
0 0 12997.5000 14 User: 8 471
looking for cut... found 2 cuts, best 0.0
0 0 13000.5000 29 User: 2 474
looking for cut... found 6 cuts, best 0.0
0 0 13003.3750 57 User: 6 479
looking for cut... found 11 cuts, best 0.0
0 0 13006.5000 22 User: 11 487
looking for cut... found 2 cuts, best 0.0
0 0 13008.5000 73 User: 2 495
looking for cut... found 8 cuts, best 0.0
0 0 13023.2500 62 User: 8 516
looking for cut... found 6 cuts, best 0.0
0 0 14782.0000 8 User: 6 543
looking for cut... found 1 cuts, best 0.0
0 0 14782.0000 28 User: 1 547
looking for cut... found 2 cuts, best 0.0
0 0 14782.0000 8 User: 2 551
looking for cut... found 1 cuts, best 0.0
0 0 14782.6667 45 User: 1 555
looking for cut... found 7 cuts, best 0.0
0 0 14795.5000 68 User: 7 572
looking for cut... found 5 cuts, best 0.0
0 0 14846.0000 40 User: 5 588
looking for cut... found 3 cuts, best 0.0
0 0 14871.5000 42 User: 3 596
looking for cut... found 7 cuts, best 0.0
0 0 14873.0000 14 User: 7 598
looking for cut... found 2 cuts, best 0.0
0 0 14873.4000 52 User: 2 602
looking for cut... found 6 cuts, best 0.0
0 0 14902.5000 38 User: 6 613
looking for cut... found 3 cuts, best 0.0
0 0 14906.0000 16 User: 3 619
looking for cut... found 2 cuts, best 0.0
0 0 14906.8000 54 User: 2 623
looking for cut... found 6 cuts, best 0.0
0 0 14935.2500 44 User: 6 643
looking for cut... found 2 cuts, best 0.0
0 0 15356.5000 32 User: 2 647
looking for cut... found 2 cuts, best 0.0
0 0 15360.0000 52 User: 2 660
looking for cut... found 5 cuts, best 0.0
0 0 15388.7500 74 User: 5 679
looking for cut... found 5 cuts, best 0.0
0 0 15401.7500 70 User: 5 682
looking for cut... found 5 cuts, best 0.0
0 0 15422.2500 66 User: 5 693
looking for cut... found 5 cuts, best 0.0
0 0 15508.2500 64 User: 5 703
looking for cut... found 5 cuts, best 0.0
0 0 15549.7500 58 User: 5 712
looking for cut... found 5 cuts, best 0.0
0 0 15560.0000 20 User: 5 720
looking for cut... found 2 cuts, best 0.0
0 0 15560.0000 20 User: 2 722
looking for cut... found 2 cuts, best 0.0
0 0 15560.0000 20 User: 2 723
looking for cut... found 2 cuts, best 0.0
0 0 15560.0000 20 User: 2 724
looking for cut... found 2 cuts, best 0.0
0 0 15561.0000 42 User: 2 732
looking for cut... found 5 cuts, best 0.0
0 0 15561.0000 38 User: 5 735
looking for cut... found 5 cuts, best 0.0
0 0 15562.7500 67 User: 5 738
looking for cut... found 7 cuts, best 0.0
0 0 15564.7500 71 User: 7 743
looking for cut... found 8 cuts, best 0.5
0 0 15610.0000 47 User: 8 761
looking for cut... found 1 cuts, best 0.0
0 0 15675.0000 47 User: 1 771
looking for cut... found 2 cuts, best 0.0
0 0 15701.2500 61 User: 2 797
looking for cut... found 1 cuts, best 0.0
0 0 15726.7500 71 User: 1 801
looking for cut... found 0 cuts, best 1.9999999999999998
0 2 15726.7500 71 15740.2500 801 0 0
Elapsed time = 23.90 sec. (10515.28 ticks, tree = 0.00 MB, solutions = 0)
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 0.0
looking for cut... found 0 cuts, best 1.9999999999999998
2 4 15753.0000 47 15741.2500 816 x16243 N 2 1 2
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 1.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 0.0
looking for cut... found 0 cuts, best 1.9999999999999998
5 7 15762.0000 49 15741.2500 834 x25486 N 5 4 4
looking for cut... found 1 cuts, best 1.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 1.5
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 0 cuts, best 1.9999999999999998
* 10+ 10 15900.0000 15741.2500 887 1.00%
10 12 15776.0000 23 15900.0000 15741.2500 887 1.00% x5629 N 10 9 7
* 12 12 integral 0 15787.0000 15741.2500 891 0.29% x6893 U 12 11 9
looking for cut... found 0 cuts, best 2.0
looking for cut... found 1 cuts, best 1.3333333333333335
looking for cut... found 0 cuts, best 1.9999999999999998
* 15 11 integral 0 15781.0000 15741.2500 895 0.25% x6545 U 15 14 11
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 1.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 2.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 1.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 1.0
looking for cut... found 1 cuts, best 1.3333333333333335
looking for cut... found 1 cuts, best 0.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 1.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 4 cuts, best 1.5
looking for cut... found 1 cuts, best 1.0
looking for cut... found 0 cuts, best 1.9999999999999998
29 16 15777.0000 47 15781.0000 15755.7500 971 0.16% x4489 N 29 27 10
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 0.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 0.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 0.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 2.0
57 21 15776.5000 8 15781.0000 15763.0000 1076 0.11% x2871 D 57 56 9
looking for cut... found 0 cuts, best 2.0
* 59 20 integral 0 15780.0000 15763.0000 1078 0.11% x2847 D 59 58 11
looking for cut... found 1 cuts, best 0.0
looking for cut... found 1 cuts, best 0.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 1 cuts, best 1.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 2 cuts, best 0.6666666666666667
looking for cut... found 1 cuts, best 1.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 1 cuts, best 1.3333333333333333
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
91 18 cutoff 15780.0000 15769.5000 1232 0.07% x2871 U 91 65 9
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 2.0
looking for cut... found 1 cuts, best 1.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 1.9999999999999998
looking for cut... found 0 cuts, best 2.0
looking for cut... found 0 cuts, best 1.9999999999999998
Cover cuts applied: 3
Zero-half cuts applied: 11
User cuts applied: 362
Root node processing (before b&c):
Real time = 23.88 sec. (10502.64 ticks)
Sequential b&c:
Real time = 49.95 sec. (2187.41 ticks)
------------
Total (root+branch&cut) = 73.83 sec. (12690.05 ticks)
complete!
opt is: 15780.0
{noformat}
Running the code with and without user cuts, judging from the print statements (which are not entirely reliable), it seems that the bottle neck is actually solving the {mathinline}|V|-1{mathinline} max flow min cut problems. While we know there are better ways to compute a global minimum cut [from our previous discussion|Polynomial Time Separation and UserCutCallback#Polynomial Time Separation for TSP over Cutset Constraints], instead we will explore some heuristics to vastly improve performance without writing a lot of code.
Look at the first column of CPLEX's output, which gives the number of nodes generated thus far. When this column is zero, that means we are still working on the root node. Here are a few observations about our cuts:
* More often then not, when there is a violated cut, the most violated cut has weight zero.
* This is particularly true towards the end of the optimization when we are doing branch and bound (perhaps the _extreme_ action of forcing a variable to take the value one or zero causes the solution to make loops).
* The value of the root LP is significantly larger (which is better) with the cutset constraints, as seen below
* The total number of nodes created using the cutset constraints is much smaller, as seen below.
These final two bullet points indicate that we do stand to gain a lot from the cutset formulation if we can get the running time of our separation routine under control. We now give a few heuristics to improve performance.
{anchor:lpRelax}
{chart:type=bar|title=LP strength on TSPLIB instances|yLabel=LP relaxation/OPT|width=600|height=400|rangeAxisLowerBound=97|rangeAxisUpperBound=100}
||Problem Name||eil51|bier127|ch130|ch150|d198|
|Without User Cuts|99.6|99.1|99.7|98.1|78.9|
|With User Cuts|99.7|99.5|99.7|99.4|99.7|
{chart}
{chart:type=bar|title=Nodes created on TSPLIB instances|yLabel=B&B nodes created|width=600|height=400|}
||Problem Name||eil51|bier127|ch130|ch150|d198|
|Without User Cuts|16|88|142|1765|1536|
|With User Cuts|2|19|44|429|138|
{chart}
h1. Check Connected Components First
The first heuristic is as follows: on the subgraph using the edges with only nonnegative weight (which we have already formed) check for connectivity. If you have more than one connected component, then any cut separating connected components will have weight zero and hence be minimal. As we can check for connected components in {mathinline}O(|V|+|E|){mathinline} time, we will save a lot of time when there are multiple connected components. Viewing the log file above, we this is frequently the case (as conversely, whenever the best cut is zero, there must have been multiple connected components). Notice that the class {{MinCutSolver}} (which is holding the subgraph using only edges with positive weight) already has a method built in:
||Method Name||Return Type||Arguments||Description||
|checkConnectedComponents|Set<Set<V>>| |Returns the nodes of the subgraph using only edges with positive weight, partitioned into connected components.|
To integrate this with the UserCutCallback, simply add the code
{code}
MinCutSolver<V,E> minCutSolver = new MinCutSolver<V,E>(graph,edgeWeights);
Set<Set<E>> cutSets = new HashSet<Set<E>>();
//add here
Set<Set<V>> connectedComponents = minCutSolver.checkConnectedComponents();
if(connectedComponents.size() > 1){
for(Set<V> connectedComponent: connectedComponents){
cutSets.add(tspInstance.cutEdges(connectedComponent));
}
System.out.println("trivial cuts exist, found " + cutSets.size());
}
else{
//old
V source = graph.getVertices().iterator().next();
//...
System.out.println("found " + cutSets.size() + " cuts, best " + best);
//add extra brace
}
for(Set<E> cutEdges: cutSets){
this.add(cplex.ge(Util.integerSum(cplex, edgeVariables, cutEdges), 2));
}
{code}
Observe the large improvement in running time below.
{chart:type=bar|title=Run time for TSPLIB instances|yLabel=Run time (sec)|width=600|height=400}
||Problem Name||eil51|bier127|ch130|ch150|d198|
|Without User Cuts|0.13|1.23|1.96|5.01|8.58|
|With User Cuts|0.40|3.76|12.52|83.62|103.93|
|Connected Components First|0.38|2.42| 5.10|30.39|45.74|
{chart}
However, we are still not faster than our solver without user cuts, and we still can't practically solve d493 (although we get a lower bound that is 99.6% of the optimum in about 60 seconds). Our separation routine is still too slow, and is notably ineffective towards the end of the optimization. We give a quick fix in the next section.
h1. Use Only Connected Components After Root Node
Recall our observation from the log file that as we progressed in the branch and bound tree, it became rare that we encountered violated cutset constraints where the graph was not disconnected into multiple peices (i.e. constraints violated by 2.0). A coarse but effect solution for this problem is to simply stop solving max flow problems after a certain point in the optimization, and rely on the heuristic from the previous section (as a user cut) in combination with the lazy constraints. A convenient (and reasonable) place to stop attempting these max flow problems is when we solve the root node and start branching. That we chose the root node to stop looking for expensive cuts was not a coincidence: we see in was not a coincidence, our earlier [computations|#lpRelax] on the quality of the cutset LP relaxation suggest that once we have solved the root node, our lower bound will be within 1\% of optimal, leaving little room for further improvement by more cutting planes. Using the method [getNnodes64()|Polynomial Time Separation and UserCutCallback#getNnodes], we can modify {{MinCutCallback}} with *a single line of code* as follows:
{code}
//...
if(connectedComponents.size() > 1){
for(Set<V> connectedComponent: connectedComponents){
cutSets.add(tspInstance.cutEdges(connectedComponent));
}
System.out.println("trivial cuts exist, found " + cutSets.size());
}
else if(this.getNnodes64() == 0){// <--- the only line that changed!
V source = graph.getVertices().iterator().next();
//...
{code}
We see in the chart below that this new variation beats out all the other user cut heuristics thus far and is competitive with just using lazy constraints on small instances.
{chart:type=bar|title=Run time for TSPLIB instances|yLabel=Run Time (sec)|width=600|height=400}
||Problem Name||eil51|bier127|ch130|ch150|d198|
|Without User Cuts|0.13|1.23|1.96|5.01|8.58|
|With User Cuts|0.40|3.76|12.52|83.62|103.93|
|Connected Components First|0.38|2.42| 5.10|30.39|45.74|
|Stop After Root|0.20|1.70|2.40|4.77|10.3|
{chart}
However, the real gain is on the larger, more challenging instances, which we can now actually solve. As seen in the [log file|d493 CPLEX log excerpt], it took a little over 2 minutes to be provably within 1% of optimal, and we were able to solve the problem completely in about 12 minutes, while it took about 2 hours with only lazy constraints. Again the LP was 99.6\% of optimal, so we can't make a lot of improvement with better cuts (i.e. there is more room for improvement on the primal problem of generating good integer solutions). However, we did ultimately visit over 26,000 nodes. Next,The weproblem tryd657 twois morestill trickswell toout improveof performance,reach; butafter they4571 areseconds essentially(over secondan orderhour), correctionsthe asMIP comparedrelative togap Christofideswas and Two-Opt.still 0.33%.
{chart:type=bar|title=Run time for medium sized TSPLIB instances|yLabel=Run Time (sec)|width=600|height=400}
||Problem Name||d493||d657||
|Stop After Root|744.36| |
{chart}
Next, we try two more tricks to improve performance, but they are essentially second order corrections as compared to Christofides and Two-Opt.
h1. (Optional) Use a Backoff Function After the Root Node
{chart:type=bar|title=Run time for TSPLIB instances solved with lazy constraints|yLabel=Run Time (sec)|width=600|height=400}
||Problem Name||eil51|bier127|ch130|ch150|d198|
|Without User Cuts|0.11|0.77|1.98|5.09|17.57|
|With User Cuts|5|6|7|8|20|
|Connected Components First|5|6|7|8|20|
|Stop After Root|5|6|7|8|20|
|Backoff after root|5|6|7|8|20|
{chart}
h1. (Optional) Check Random s-t Cuts
{chart:type=bar|title=Run time for TSPLIB instances solved with lazy constraints|yLabel=Run Time (sec)|width=600|height=400}
||Problem Name||eil51|bier127|ch130|ch150|d198|
|Without User Cuts|0.11|0.77|1.98|5.09|17.57|
|With User Cuts|5|6|7|8|20|
|Connected Components First|5|6|7|8|20|
|Stop After Root|5|6|7|8|20|
|Backoff after root|5|6|7|8|20|
|Randomized s-t|5|6|7|8|20|
{chart}
|