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. 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.
h3. Check Connected Components First{chart:type=bar|title=TSPLIB instances solved with lazy constraints|yLabel=LP relaxation|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}
{chart:type=bar|title=Run time for TSPLIB instances solved with lazy constraints|yLabel=Run Time (sec)=B&B nodes created|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}
h3. Check Connected Components First
{chart:type=bar|title=TSPLIB instances solved with lazy constraints|yLabel=LP relaxation|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}
|