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.

  • No labels