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 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.
(c) Mia Müßig