Benchmark Suites

The course provides benchmark collections and experiment-running infrastructure so that Checkpoint 4 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 3 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 3 bound function.

For a minimization problem, if a row reports:

known_optimum = null
bound_value   = 117
objective     = 126

then the evidence certifies only:

117 \le OPT \le 126.

Established external benchmarks

The required core suites are already present in the repository and do not need network access. The course also provides optional installation tools for established public benchmark collections:

PACE 2019 Vertex Cover Exact instances for additional large/hard MVC experiments;
selected TSPLIB95 TSP instances with published proven optima; and
selected University of Waterloo National TSP instances, including both proven-optimal instances and larger open instances with published best-known tours and certified lower bounds.

Install optional collections with:

python tools/install_external_benchmarks.py pace2019-vc
python tools/install_external_benchmarks.py tsplib
python tools/install_external_benchmarks.py waterloo-tsp

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 published 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. Core CP4 does 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