=d657log}
{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 _
d657log
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 Include
15DOTs60ia13:excerpt
d657 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.
d657 table
15DOTs60ia13:excerpt d657 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). 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.