Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
bjornsing
89 days ago
|
parent
|
context
|
favorite
| on:
Shortest-possible walking tour to 81,998 bars in S...
Would be nice if they could briefly describe the algorithm. Sounds like they’ve turned the TSP into an integer linear program that they can do branch and bound on, but I’m not sure.
pkhuong
89 days ago
[–]
It's classic Lin Kernighan (
http://webhotel4.ruc.dk/~keld/research/LKH/
) for the primal heuristic, and optimality proof by Concorde for cutting plane generation and branching (
https://www.math.uwaterloo.ca/tsp/book/index.html
, or
https://www.math.uwaterloo.ca/tsp/korea/computation.html
for details specific to this instance), with CPLEX as the underlying LP solver.
Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
