TSP (with additional side constraints)

[ruthmair]

Why this Mod?

• TSP is a well-known combinatorial problem and can arise as subproblem of more complicated problems, e.g., from routing and scheduling.
• Formulating the TSP as MILP is not trivial because of subtour elimination. Many people use Big-M formulations but cut formulations perform usually better (since resulting bounds are better).
• Optionally, side constraints might be considered, e.g., node time windows, resource restrictions on total tour, precedence relations.
• The mod will not be state-of-the-art in terms of performance (best TSP solver is Concorde, variants are usually solved via sophisticated branch-and-cut algorithms with many additional sets of valid inequalities). Still, the performance will be sufficient to solve instances with up to a few hundred nodes for the basic TSP, probably much less for variants.

What will the API be?

Input data for the basic TSP is just the complete cost/distance matrix (numpy.ndarray)
tour, objective = solve_tsp(distance_matrix)
Symmetric costs/distances allow a more efficient formulation (reducing symmetry) so a differentiation might make sense.

Variants with additional side constraints might require a time matrix for arcs, time windows for edges, other resource matrices for arcs, node pairs representing precedence relations, etc.
In those cases it makes sense to use a graph representation, e.g., via a pandas dataframe.

Additional context