The root page 15DOTs60ia13:Tutorial could not be found in space 15.S60 SSIM: Software Tools for Operations Research.
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
Unknown macro: {chart}
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 |
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.
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);
Lets run the code again on d198 and take a closer look at the output.
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
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 \( |V|-1 \) max flow min cut problems. While we know there are better ways to compute a global minimum cut from our previous discussion, 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.
Unknown macro: {chart}
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 |
Unknown macro: {chart}
Problem Name |
eil51 |
bier127 |
ch130 |
ch150 |
d198 |
|---|---|---|---|---|---|
Without User Cuts |
16 |
88 |
142 |
1765 |
1536 |
With User Cuts |
2 |
19 |
44 |
429 |
138 |
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
\( O(|V|+|E|) \)
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
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));
}
Unknown macro: {chart}
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 |
Use Only Connected Components After Root Node
Unknown macro: {chart}
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 |
Use a Backoff Function After the Root Node
Unknown macro: {chart}
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 |
(Optional) Check Random s-t Cuts
Unknown macro: {chart}
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 |