Traveling Salesperson Problem

Given a weighted graph $G=(V,E)$ , a tour is a cycle that visits every vertex exactly once before returning to its starting vertex.

If a tour visits the vertices in the order

v_0,v_1,\ldots,v_{n-1},v_0,

then its total cost is the sum of the weights of the edges used by the tour:

w(v_0,v_1)+w(v_1,v_2)+\cdots+w(v_{n-1},v_0).

The goal of the Traveling Salesperson Problem is to find a tour with the smallest possible total cost.

Throughout this specification, Traveling Salesperson Problem is abbreviated TSP.

Your goal throughout the project will be to investigate algorithms involving TSP tours. The specific algorithmic tasks required at each stage are described in the corresponding checkpoint.

Before implementing your algorithms, review the project-wide Program Interface and Input Files specifications.

Graph Assumptions

TSP instances use weighted, undirected, complete graphs.

Vertices are numbered consecutively beginning with 0: $V=\{0,1,\ldots,n-1\}$ .
Every pair of distinct vertices is connected by exactly one edge.
Edge weights are nonnegative integers.
Because the graph is undirected, $w(u,v)=w(v,u)$ .
A valid tour visits every vertex exactly once and then returns to its starting vertex.

The weighted graph format and supplied input routines are described on the Input Files page.

Example

Consider the following complete weighted graph instance:

example-01.txt

4 6
0 1 10
0 2 15
0 3 20
1 2 35
1 3 25
2 3 30

The first line indicates that the graph contains four vertices and six edges. Each remaining line gives two endpoints followed by the weight of that edge.

One tour is

0,1,3,2,0.

Its total cost is

10+25+30+15=80.

For this instance, the three distinct tours beginning at vertex 0, ignoring reversal, have costs:

\begin{aligned} 0,1,2,3,0 &: 95,\\ 0,1,3,2,0 &: 80,\\ 0,2,1,3,0 &: 95. \end{aligned}

Therefore, the tour $[0,1,3,2,0]$ is a minimum-cost tour.

For comparison,

[0,1,2,0]

is not a valid TSP tour because vertex 3 is never visited.

TSP Solution Format

TSP uses traveling_salesperson as its project-wide problem identifier.

The solution object contains the reported tour and its total cost:

"solution": {
  "cost": 80,
  "tour": [0, 1, 3, 2, 0]
}

The order of vertices in tour is significant.

For a graph containing $n$ vertices, the tour list must contain exactly $n+1$ entries. The first and last entries must be the same, and every graph vertex must appear exactly once among the first $n$ entries.

cost must equal the sum of the weights of the $n$ edges traversed by the tour.

The starting vertex is not significant. For example,

[0,1,3,2,0]

and

[1,3,2,0,1]

represent the same cycle. Because the graph is undirected, traversing the cycle in the opposite direction also represents the same tour.

Using the common project interface,

python src/solve.py example-01.txt \
    --problem tsp \
    --algorithm exhaustive

could produce:

{
  "problem": "traveling_salesperson",
  "algorithm": "exhaustive",
  "instance": "example-01",
  "solution": {
    "cost": 80,
    "tour": [0, 1, 3, 2, 0]
  },
  "statistics": {}
}

Your program is required to report only one minimum-cost tour. If an instance has multiple minimum-cost tours, any one of them is acceptable; your program does not need to enumerate all optimal solutions.

Decision-Problem Verifier

The verifier you implement corresponds directly to the polynomial-time certificate verifier for the decision version of TSP:

Given a weighted graph $G$ and a threshold $k$ , does $G$ contain a tour whose total cost is at most $k$ ?

The proposed tour is the certificate. Your implementation must provide:

from course.common.weighted_graph import WeightedGraph

def is_valid_tour(graph: WeightedGraph, tour: list[int], k: int) -> bool:
    ...

in:

src/student/problems/traveling_salesperson/verifier.py

Two WeightedGraph interface details are especially useful when implementing this verifier:

n = graph.num_vertices       # integer attribute -- no parentheses
w = graph.weight(u, v)       # weight of edge (u, v)

Thus, for example, iterate over the vertices with range(graph.num_vertices) rather than calling graph.num_vertices(). The complete shared weighted-graph interface is documented on the Program Interface page.

The verifier must return True exactly when:

tour is a valid TSP tour of graph; and
the total cost of that tour is at most k.

The verifier must compute the tour cost from graph and tour; it must not trust a separately reported solution cost.

For the example graph, [0, 1, 3, 2, 0] has cost 80. Therefore:

is_valid_tour(graph, [0, 1, 3, 2, 0], 80)  # True
is_valid_tour(graph, [0, 1, 3, 2, 0], 79)  # False

A malformed tour must still be rejected regardless of the threshold:

is_valid_tour(graph, [0, 1, 2, 0], 1000)    # False: vertex 3 is missing

The verifier does not determine whether the tour is minimum-cost. It checks whether the supplied certificate proves a YES answer for the particular decision threshold k, and it must run in polynomial time without calling one of the solving algorithms.

Gradescope may import is_valid_tour() directly and test both tour feasibility and the threshold condition independently of src/solve.py.

Checkpoint 3 Bound Function

TSP is a minimization problem, so the required bound is a lower bound on the minimum tour cost. Implement:

from course.common.weighted_graph import WeightedGraph

def lower_bound(graph: WeightedGraph) -> int | float:
    ...

in:

src/student/problems/traveling_salesperson/bound.py

The function must run in polynomial time and never return a value larger than the true optimal tour cost. An MST-based lower bound is one natural design to consider during Checkpoint 2. Teams may propose a different valid polynomial-time bound during the algorithm-design meeting.

The same bound may be reused inside an improved exact branch-and-bound solver, but the experiment framework also calls it independently so that it can be used to evaluate heuristic solutions when OPT is unavailable.

Course Benchmark Suites

The project template contains TSP benchmark suites under:

benchmarks/traveling_salesperson/

The required suites are designed around different experimental questions:

readiness checks the Checkpoint 3 interfaces on small instances;
exact_frontier compares exhaustive and improved exact search over increasing sizes and three different edge-weight structures;
quality_known evaluates early heuristic and bound quality where OPT is known;
heuristic_scale checks heuristic behavior on coordinate-backed instances far beyond the practical exact-search range; and
structure holds n fixed while comparing uniform Euclidean, clustered Euclidean, and non-geometric random-weight instances.

For randomized heuristics, the course runner uses several fixed seeds and preserves every run. This allows Checkpoint 4 to examine variation in both solution value and running time instead of drawing conclusions from one lucky or unlucky run.

Large coordinate-backed instances

Large Euclidean TSP benchmarks are stored as coordinates rather than as an explicit list of all $\binom{n}{2}$ weighted edges. Student code still receives the normal course WeightedGraph and calls:

graph.weight(u, v)

to obtain the integer edge weight. Students do not parse TSPLIB files or compute TSPLIB rounding themselves.

Optional leaderboard and reach instances

The benchmark manifest also defines optional public TSP challenges from the University of Waterloo National TSP Collection.

leaderboard_known contains increasingly large instances whose optimal tour values have been proven. These can be scored by percentage gap from OPT.
reach_known contains still larger proven-optimal instances.
reach_open contains very large open instances. These have a published best-known tour and a published certified lower bound, but no known OPT.

Install the optional Waterloo files with:

python tools/install_external_benchmarks.py waterloo-tsp

For an open instance, report a gap to the published best-known tour, not a gap to OPT. The course-generated result data records the published lower bound separately so that the status of the instance remains clear.

For the known-OPT leaderboard, each instance is run under the same fixed course seeds. The recommended scoreboard score is the median percentage gap to OPT for each instance, averaged equally across the leaderboard instances. Lower is better. This reduces the influence of one unusually lucky randomized run. The best tour found and runtime summaries are reported separately.

See the Benchmark Suites page and benchmarks/traveling_salesperson/README.md in the repository for the complete suite definitions.