table}
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.
|