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
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 |
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.
System.out.println("hello word!");
Lets run the code again on d198 and take a closer look at the output.
output...
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. Notice the first column of the 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. Additionally, we see that often, when there is any cut that is violated, the most violated cut has weight zero. Further, we see that as the optimization continues, more often then not,