You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 5 Next »

The root page 15DOTs60ia13:Tutorial could not be found in space 15.S60 SSIM: Software Tools for Operations Research.

Medium Instance Performance

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_

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

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.

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 provides a unified view of many classes of valid inequalities for TSP using lifting
  • Here 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 \( T \subset E \) , we know all future solutions will satisfy \[ \sum_{e \in E \setminus T} x_e \geq 2 \]
  • 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.
  • Implement a more traditional improvement on two-opt, the Lin–Kernighan heuristic, as described both in the paper above and here.
  • Improve the efficiently of separating over the cutset constraints as previously described
  • 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, 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.
  • No labels