| Wiki Markup |
|---|
h1.
Lets take a look at where we are with all the bells and whistles added. If you expand the toggle below, you will see the log file from our failed attempt to solve {{d657
}}.
{
:=}_Show d657 log _
{| Cloak |
|---|
: | = | }
{excerpt-include:excerpt d657 log}
{cloak}
As stated on the [TSPLIB website|http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html], the optimal solution for this problem is 48912. By looking through the logs, you see that after only about 25,000 nodes, we reach a solution with objective 48913. Unfortunately, our lower bound, while initially 99.3% of the optimal solution, increases very slowly. Using the _ | | excerpt d657 log | As stated on the TSPLIB website, the optimal solution for this problem is 48912. By looking through the logs, you see that after only about 25,000 nodes, we reach a solution with objective 48913. Unfortunately, our lower bound, while initially 99.3% of the optimal solution, increases very slowly. Using the src/output/NodeLog.java _, we turned the node log into the plot below illustrating how slowly our lower bound is converging, in comparison to our upper bound. Even after creating over 300,000 nodes in branch and bound, we have quite a way to go proving optimality. This suggests that our next few optimizations should be in trying to improve our lower bounds.
{: |
|---|
| excerpt d657 table |
|---|
| excerpt |
|---|
|
}
Looking more closely at the log file, we see that there were not many instances where two-opt was able to improve an integer solution generated by CPLEX. We see that every "*" in the log, which indicate where new incumbent solutions have been found, is accompanied by a "+", which indicates that a heuristic of some kind (either heuristic callback or internal CPLEX heuristic) was used (as opposed to the solution to the LP at a node being integral). We can see from the print statements that the first few "*" are from the heuristic callback, and that two-opt significantly improved the quality of these solutions. However, for the remaining solutions, we see that two-opt generally made no improvement. Perhaps this is because CPLEX's internal heuristics already applied some kind of local search, (read about RINS [in the manual |http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2FCPLEX%2FUsrMan%2Ftopics%2Fdiscr_optim%2Fmip%2Fheuristics%2F42_heur_title_synopsis.html]). However, if we considered a more powerful heuristic than two-opt, perhaps we could still make some improvement. Note that in general, our {{IncumbentCallback
}} can still improve the optimal solution. To see it in action, turn off the option {{christofidesHeuristic
}} and run {{d493
}}.
h1. Future Directions
The first step taken should be to identify more valid inequalities that can be quickly separated over. The literature on this topic is vast.
* [Here|http://www.jstor.org/discover/10.2307/3690679?uid=3739696&uid=2&uid=4&uid=3739256&sid=21101688382987] provides a unified view of many classes of valid inequalities for TSP using lifting
* [Here|http://dedekind.mit.edu/~goemans/PAPERS/Goemans-1995-WorstCaseComparisonOfValidInequalitiesForTheTSP.pdf] provides a simple LP duality argument to compare various classes of valid inequalities for TSP. The paper also provides a good number of references on classes of valid inequalities and separation.
Here are a few more ideas:
* Integrate two-opt with either cuts or branching, as once we have run two-opt on some tour {mathinline}T \subset E{mathinline}, we know all future solutions will satisfy
{mathdisplay}
\sum_{e \in E \setminus T} x_e \geq 2
{mathdisplay}
* Use a "very large neighborhood search," a local search that checks an exponentially large neighborhood in polynomial time with an efficient algorithm [see section 4 here|https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CFMQFjAD&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.91.2825%26rep%3Drep1%26type%3Dpdf&ei=36D9UOrsMMje0gGCx4CQAQ&usg=AFQjCNFqHCZHzjn2egMyse7NJ0TrXopG-g&sig2=ZSl87Ro8h2X7bXI8v3rRbQ&bvm=bv.41248874,d.cWE&cad=rja].
* Implement a more traditional improvement on two-opt, the Lin–Kernighan heuristic, as described both in the paper above and [here|http://www2.research.att.com/~dsj/papers/TSPchapter.pdf].
* Improve the efficiently of separating over the cutset constraints [as previously described|Polynomial Time Separation and UserCutCallback#Polynomial Time Separation for TSP over Cutset Constraints]
* Use better construction heuristics. For example, given a set of edges (with no cycles or nodes with degree above two), the problem of finding the optimal tour using all of these edges can be written as a small ATSP (with one node for each connected component in the subgraph using only the suggested edges). Since ATSP can be solved by [solving a TSP that is twice as large|http://en.wikipedia.org/wiki/Travelling_salesman_problem#Solving_by_conversion_to_symmetric_TSP], we can bootstrap our tour construction. Fixing a set of variables to be one and then solving the restricted problem is actually a general technique called diving, just in our special case, the diving has a special form.
|