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 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|
{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}
System.out.println("hello word!");
{code}
Lets run the code again on d198 and take a closer look at the output.
{noformat}
output...
{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. NoticeWhile 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 theCPLEX'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 Additionally,about we see that oftenour cuts:
* More often then not, when there is a anyviolated cut that is violated, the most violated cut has weight zero.
* This is particularly true Further, we see that as the optimization continues, more often then not, 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).
We now give a few heuristics to improve performance.
h3. Check Connected Components First
{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|
{chart}
h3. Use Only Connected Components After 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|
{chart}
h3. 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}
h3. (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}
|