3 ms·
That's an interesting result; do you happen to have a citation? I couldn't find one with a few minutes of Google Scholar. If I understand Concorde's claims cor
by _dps 11y ago
That's an interesting result; do you happen to have a citation? I couldn't find one with a few minutes of Google Scholar.
If I understand Concorde's claims correctly, there is still the question of finite numerical precision (it doesn't seem to use MPFR or any other arbitrary precision library). Perhaps the suboptimality of the path is less than 1e-7 or 1e-16 (depending on precision) times the distance between the "looped" cities?
Having said that, one of the authors of Concorde is R. Bixby, a co-author of CPLEX (which was for decades, and may still be, the industry standard LP solver including for branch-and-bound problems). And Chvatal is another very widely regarded LP researcher. So I would take Concorde's claims of optimality at face value (though of course there could be a data input error somewhere).
Edit: Ah, I misunderstood the sense of "loop"; I thought there was a subcircuit (which I believe can be optimal in some cases), but instead there are two segments crossing each other that, per wrk1's comment below, should really be shorter if their destinations were "swapped". Rough Google-maps math suggests that would reduce the distance by ~10 miles out of ~16k, which seems well above numerical precision.
- wrk1 11y agoYou don't need a citation - look at NM. By straightening the loop, the path will be shorter, due to the triangle inequality.
- pvdebbe 11y agoI don't have a citation at hand, but the proof is simple enough. It does rely on the triangle inequality and can be used to construct a quick approximator for this Euclidean variation of TSP. Granted, the math is different on a surface of a sphere. The error could be caused by imprecise input values.
- pkhuong 11y agoIn operations research, it's common to stop when a solution is provably within 1e-4 of optimum. Off the top of my head, reasons include: we don't want to optimize FP error, limited precision in the input data, and negligible real world impact. That said, it's also well known that non-OR practitioners have less confidence in our results when there are trivial local suboptimalities, in some cases even when they don't affect the objective function (e.g., off the critical path in a scheduling problem); I've heard of several professionals who pass the output of exact (modulo stopping criteria) methods through stupid local searches just for that reason.
- Bill_Cook 11y agoConcorde produces a provably optimal tour, but it follows the TSPLIB input format and requires that all distances be integers. There will thus be rounding error in converting the geodesic distances to integers. To obtain greater precision, the geodesic distances should be scaled to meters rather than kilometers.