The Travelling Salesman Problem (TSP) is a famously hard combinatorial optimization problem. Here two solvers are implemented:
- An efficient solver, which uses the Miller-Tucker-Zemlin Encoding to translate TSP into an Integer Programming problem and solves that with the commercial state-of-the-art solver Gurobi
- A standalone solver which implements the Held-Karp algorithm to solve TSP with dynamic programming
- A simple branch-and-bound solver for educational purposes, who can prune backtracking branches as soon as their lower bound is bigger than the current maximum
Using benchmark(), one can compare the performances on the TSPLIB95 Dataset. benchmark.log also provides pre-recorded results measured with an Intel i9-10980HK and 32 GB of memory.
(c) Mia Müßig