Benchmark Suites

The course provides benchmark collections and experiment-running infrastructure so that the Final Project can focus on algorithmic interpretation, not on writing a benchmark harness.

The benchmark definitions live in the team repository under:

benchmarks/

and are controlled by problem-specific manifest.json files. The manifest records which algorithms should run, time limits, fixed random seeds, structural metadata, and a known optimum when the exact value is available.

Required suites

Each fully supported problem provides:

• readiness — a small Checkpoint 1 smoke test;
• exact_frontier — straightforward exhaustive versus improved exact;
• quality_known — heuristic and bound quality where OPT is known;
• heuristic_scale — large instances where exact computation may be unavailable;
• structure — a course-selected structural comparison.

Run a suite from the repository root:

python tools/run_experiments.py --suite readiness
python tools/run_experiments.py --suite exact_frontier

Generated results are written under experiments/ in CSV and JSON form.

Known answers and bounds

A manifest field named known_optimum is instructor benchmark metadata. The bound_value in generated results is not supplied by the course; it is the value returned by your Checkpoint 2 bound function.

For a minimization problem, if a row reports:

known_optimum = null
bound_value   = 117
objective     = 126

then the evidence certifies only:

Challenge and leaderboard use

The required suites are designed for controlled analysis. Some benchmark collections can also be used as challenge instances after a heuristic is working reliably.

Challenge instances serve a different purpose from the required known-answer tests:

• they give repeated/randomized heuristics a reason to continue improving a best-so-far solution;
• they can support a class leaderboard when multiple teams work on the same problem;
• they can measure a team’s progress against its own earlier results; and
• open instances create an authentic setting where the quality of a feasible solution must be discussed without pretending that OPT is known.

For a challenge with known OPT, a score may use a gap from OPT. For an open challenge, report the feasible solution, the relevant valid bound, and any external or class best-known feasible result as separate quantities.

See Challenge Benchmarks and Leaderboards for the comparison rules.

External benchmark setup

The required core suites are committed with the repository. Larger benchmarks from established public collections are downloaded after your team has been assigned a problem. Once assigned_problem is set in project.json, run:

python tools/setup_project.py

The setup tool reads your assigned problem and installs the external benchmark collection configured for that problem. You do not need to know or pass collection-specific names such as PACE, DIMACS, or TSPLIB. The command is safe to rerun and skips files that are already installed.

Downloaded files are stored under:

benchmarks/<problem>/external/

and are ignored by Git. The tracked benchmark manifest retains the metadata needed to identify and evaluate those instances.

Provenance

Every externally sourced benchmark records its origin in the manifest, including the source collection, original instance name, source URL, and citation. When a published optimum, best-known solution, or bound comes from a different reference, that reference is recorded separately. A missing known_optimum means the course is not claiming a proven optimum for that instance.

The external collections include established sources such as PACE, TSPLIB/Waterloo TSP, SNAP, and the DIMACS/COLOR graph-coloring benchmark collection. Longest Path and Maximum Clique each use curated 20-instance SNAP open-challenge collections; Minimum Graph Coloring uses a curated 20-instance DIMACS/COLOR open challenge; Minimum Vertex Cover uses 20 PACE 2019 exact-track instances for which the cited PACE result tables did not publish a minimum-cover value; and Traveling Salesperson uses a curated 20-instance University of Waterloo VLSI open challenge, alongside smaller known-OPT Waterloo/TSPLIB comparison suites. The exact curated set is controlled by the course manifests and setup tool rather than by a collection name students type on the command line.

Large Euclidean TSP instances remain in coordinate form. The course WeightedGraph computes the required integer edge weight when graph.weight(u, v) is called rather than expanding a complete graph into $\binom{n}{2}$ stored edges.

For a TSP instance with a proven optimum, experiment output may report a percentage gap from OPT. For an open instance, the output instead identifies its published best-known tour and, when Waterloo publishes one, its certified lower bound. A best-known tour must not be described as optimal unless optimality has been proven.

The optional TSP leaderboard aggregates repeated randomized trials by taking the median percentage gap for each known-OPT instance and then averaging those instance medians. The open reach suite is reported separately and is never scored as though its best-known tours were proven optimal.

Randomized heuristic trials

Required heuristic suites use several fixed course-provided seeds. The runner preserves every run rather than collapsing them into one number. Your analysis should therefore consider variation across runs, especially variation in returned solution value and, where meaningful, wall-clock time.

You are not required to perform formal statistical inference. Useful summaries may include the best and worst result, mean or median, range, or another clearly explained summary that helps characterize how stable the heuristic is.

geng and non-isomorphic graphs

For the four unweighted graph problems, the course wrapper can call Brendan McKay’s geng program from nauty to generate non-isomorphic graphs. The core Final Project requirements do not require geng; required structural instances are already supplied.

geng is not used for TSP benchmark generation. Every symmetric TSP instance in this project is a complete graph, so if weights are ignored the underlying graph is simply $K_n$ and there is only one unweighted graph up to isomorphism. The important TSP variation is in the edge weights: geometric layout, clustering, weight distribution, and related structure. TSP benchmark families are therefore generated by varying those weight-producing mechanisms rather than by enumerating non-isomorphic unweighted graphs.

After installing nauty, an optional graph-problem suite can be generated with, for example:

python tools/generate_geng_suite.py \
    --n 9 --edges 12:20 --connected --limit 300

The wrapper detects both the geng command used by Homebrew installations and the nauty-geng command used by Ubuntu packages.