Experiments

1 - 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.

2 - Experimental Evaluation

This page provides guidance for the experimental work required by Checkpoint 2 and the Final Project. The checkpoint pages define which experiments and analyses are required; this page explains how to measure algorithm behavior, compare results fairly, characterize instances, organize experimental artifacts, and make the results reproducible.

The course experiment runner combines your algorithm results with benchmark metadata from the problem manifest. In addition to your returned solution and statistics, the generated result files record information such as known optima when available, published or class best-known values, bounds, instance size and structure, algorithm, seed, and timing information. This lets you focus on interpreting the experiment rather than manually reconstructing benchmark metadata.

Measuring Solution Quality

A heuristic should be evaluated by more than whether it returns a valid solution. The appropriate quality measurement depends on what is known about the instance.

When the optimum is known

If a benchmark has a proven optimum, compare the heuristic result directly with that optimum. Useful measurements may include:

• absolute gap from OPT;
• relative or percentage gap from OPT;
• whether the heuristic reached OPT; and
• best, worst, mean, or median quality across repeated randomized runs.

For example, for a minimization problem, the percentage gap is $100\cdot(\text{solution}-OPT)/OPT$.

One useful summary across a benchmark collection is coverage: the fraction of tested instances on which the heuristic finds an optimal solution. Coverage is not sufficient by itself. Two heuristics can have the same coverage while producing very different errors on the instances they miss.

When the optimum is unknown

For larger or open benchmark instances, do not infer that the best solution you have seen is optimal.

Instead, distinguish among:

• your best feasible solution;
• a valid lower or upper bound on OPT;
• a published or class best-known feasible solution, when one exists; and
• a proven optimum, when one is actually known.

For example, if a minimization problem has a valid lower bound of 121 and your best feasible solution has value 137, then the evidence establishes $121 \le OPT \le 137$. A later feasible solution of 132 improves the best known solution, but does not by itself prove that $OPT=132$.

The experiment runner records the relevant reference and bound metadata when it is available in the benchmark manifest. Use those fields to state what the experiment actually establishes.

Randomized heuristics

Do not draw a conclusion from one unusually lucky or unlucky seed. When the course provides a fixed seed set, summarize behavior across those runs. Depending on the question, useful summaries include:

• best, worst, mean, and median objective value;
• variability across seeds;
• fraction of runs reaching OPT when OPT is known; and
• improvement as more restarts, attempts, or computation are allowed.

Measuring Computational Effort

Running time matters, but timing alone often does not explain why two algorithms behave differently.

For exact algorithms, collect one or more work measures appropriate to the implementation, such as:

• complete candidates tested;
• recursive calls;
• states expanded;
• branches explored or pruned;
• bound computations;
• memoized states; or
• another clearly defined measure of search effort.

Use these measurements to help explain how the improved exact algorithm avoids work performed by the exhaustive baseline.

For heuristics, useful measurements may include:

• time to first feasible solution;
• number of attempts or restarts;
• improvement over time or attempts; and
• time required to reach the best solution found.

When comparing timing, prefer comparisons made on the same machine and under the same course-defined budget. Small timing differences should not be overinterpreted.

Characterizing Benchmark Instances

Input size alone may not explain algorithm difficulty. When required by the checkpoint, examine at least one meaningful structural characteristic in addition to size.

For graph problems, examples include:

• number of vertices and edges;
• graph density;
• degree distribution;
• connectivity or component structure; and
• another problem-specific structural feature identified by the benchmark suite.

For an undirected graph $G=(V,E)$, density is $d = 2|E|/(|V|(|V|-1))$.

Treat relationships between structure and difficulty as empirical questions. Do not assume in advance that sparse, dense, highly connected, or otherwise structured instances must be easier or harder. Use the measured results to support the conclusion.

Informative and Difficult Instances

Aggregate summaries can hide important algorithmic behavior. Identify individual instances or small groups of related instances that help explain what an algorithm is doing.

Examples include:

• an instance where a heuristic performs unusually poorly;
• an instance where two heuristics behave very differently;
• an instance where pruning is unusually effective or ineffective;
• an instance that takes much longer than others of similar size;
• an instance where the bound is especially strong or weak; or
• another surprising case that reveals something about the algorithm.

Describe the measured behavior first, then give an algorithmic explanation or hypothesis. Be clear about the difference between evidence and a plausible explanation for that evidence.

Fair Comparisons

When comparing algorithms or revisions, keep the experimental conditions as consistent as possible. Use the same:

• benchmark instances;
• course-specified timeout, attempt budget, or other resource limit;
• fixed seed set when randomization is involved;
• objective definition and solution verifier; and
• machine when wall-clock time is being compared directly.

Do not select only favorable instances or seeds after seeing the results. If a run times out or fails, record that outcome rather than silently dropping it.

Using the Course Experiment Runner

Course benchmark manifests describe the supplied instances and experiment suites. External benchmark entries also preserve provenance: the source collection, original instance name, source URL/citation, and—when different—the source supporting a published optimum, best-known value, or bound. Depending on the problem and instance, the manifest may provide metadata such as:

• known_optimum;
• best_known;
• published_lower_bound;
• n and m;
• structure_name and structure_value;
• algorithms to run;
• fixed random seeds; and
• timeout policy.

The experiment runner combines that metadata with the result of each run and writes enriched output under experiments/results/. Each suite has its own stable JSON and CSV files. For example:

experiments/results/quality_known.json
experiments/results/quality_known.csv

Timestamped copies are retained in the same directory. Because suites are stored separately, you can run the required experiments at different times without overwriting results from earlier suites.

Result rows include the algorithm result together with the relevant benchmark metadata, reference value, gap to the reference when one can be computed, bound information, seed, timing, validity, and reported algorithm statistics.

You should therefore use the generated result files as the starting point for analysis rather than trying to determine known optima by running the exact solver until it stops finishing. A missing known optimum means that the course is not claiming an optimum for that instance; it does not mean that your exact solver is expected to discover one.

Challenge Benchmarks

The project also includes optional challenge instances intended to encourage continued heuristic improvement after a valid solution is already available. Some have known optima; others are open instances for which only bounds or best-known feasible solutions are available.

See Challenge Benchmarks and Leaderboards for how those comparisons are reported and how to distinguish a best-known solution from a proven optimum. Challenge results may support your experimental analysis, but the checkpoint page determines which experiments are required.

Where Experiment Files Belong

The repository provides three student-owned experiment locations:

experiments/
├── scripts/
├── results/
└── local/

Use experiments/scripts/ for team-created scripts that run, summarize, or analyze experiments. Commit scripts needed to reproduce important results.

Use experiments/results/ for results that are required by a checkpoint or needed to support the conclusions in your report or presentation. These files are part of the repository and should be committed when appropriate.

Use experiments/local/ only for disposable or machine-local intermediate files. Except for the README already in that directory, its contents are ignored by Git. Files placed there are therefore not backed up by GitHub and are not included in normal repository submissions. Do not place required code, benchmark instances, required results, or anything needed to reproduce your conclusions there.

Course-provided benchmark collections remain under benchmarks/ and are part of the repository.

Reproducibility

Your repository should contain enough information to reproduce the important experiments reported in the final submission.

You do not need to commit every temporary file or every intermediate run. You do need to preserve enough information that another person can determine:

• which benchmark instances were used;
• which algorithms and parameters were run;
• which random seeds were used when relevant;
• which resource limits were applied;
• how important summary statistics were computed; and
• how the reported tables or figures were produced.

The goal is not merely to produce numbers. The goal is to make a defensible experimental claim and leave enough evidence for someone else to understand how that claim was obtained.

3 - Challenges & Leaderboards

Once your heuristic reliably returns valid solutions, the next question is not merely whether it works. It is:

How much better can you make the solution, and what can you actually say about its quality?

The project uses optional challenge benchmarks and leaderboards to give you a reason to keep improving a heuristic after you already have a feasible answer. The leaderboard is intended as a design challenge and source of experimental evidence, not as the primary basis for your grade.

You may be competing with another team, a published best-known result, or simply your own previous best solution. On the most interesting challenge instances, the true optimum may be unknown.

A greedy answer is a starting point

A simple greedy construction is often a useful first heuristic. In this project, however, heuristic1 is designed to support repeated improvement rather than one deterministic pass.

Depending on the problem, useful techniques may include:

• randomized tie-breaking or randomized construction;
• multiple starts or random restarts;
• iterative improvement or local search;
• rebuilding from promising partial solutions;
• keeping the best solution found so far; and
• an anytime strategy that can return a valid solution now and continue searching for a better one while more computation is available.

Checkpoint 2 requires best-so-far behavior for randomized/repeated heuristics. The challenge benchmarks give that requirement a purpose: extra attempts should have the opportunity to improve the solution instead of replacing a good result with a worse one.

Three kinds of comparison

1. Known optimum

If the benchmark has a proven optimum, solution quality can be measured directly.

For a minimization problem, for example, the percentage gap is $100\cdot\frac{\text{solution}-OPT}{OPT}$.

For a maximization problem, use the analogous gap in the correct direction.

Repeated randomized runs should be summarized across the fixed course seeds rather than by selecting one unusually lucky run.

2. Open challenge: OPT is unknown

For an open challenge, do not invent an optimum.

Suppose a minimization problem has:

team's best feasible solution = 137
valid lower bound            = 121
known OPT                    = none

Then the evidence supports $121 \le OPT \le 137$.

If another team later finds a feasible solution of 132, that is a better known solution, but it still does not prove that $OPT=132$.

For an open challenge, a leaderboard should therefore distinguish among:

• the team’s best feasible objective value;
• the best feasible value currently known to the class or published externally;
• the team’s independently computed bound; and
• whether an optimum has actually been proven.

3. Competing with yourself

A useful challenge does not require multiple teams on the same problem. Track the progress of your own method:

initial greedy result
best after local improvement
best after 10 restarts
best after 100 restarts
best within the course time limit

This makes the tradeoff between additional computation and solution quality visible and gives you evidence for deciding whether an improvement technique is actually worthwhile.

Fair comparisons

When results are compared on a class leaderboard, use the same:

• benchmark instance;
• course-specified time limit or attempt budget;
• fixed seed set when randomization is being compared; and
• objective definition and verifier.

The goal is not to reward whoever happened to run the algorithm longest on the fastest computer. The course experiment runner records the benchmark metadata needed to make comparisons reproducible.

Current challenge collections

The core benchmark suites remain the required basis for the Final Project. The repository also provides problem-specific challenge collections installed through python tools/setup_project.py:

• Traveling Salesperson: known-OPT leaderboard and reach instances plus a 20-instance University of Waterloo VLSI open challenge. Every selected VLSI instance has a published best-known tour; six also have published Concorde lower bounds, while the remaining instances rely on the team’s own valid lower bound for the certified lower side of the interval.
• Minimum Vertex Cover: 20 PACE 2019 Vertex Cover Exact instances selected from rows for which the cited PACE result tables did not publish a minimum-cover value.
• Minimum Graph Coloring: 20 DIMACS/COLOR challenge instances, including long-standing open DIMACS cases and real optical-network coloring instances.
• Maximum Clique: 20 SNAP social-network graphs used as open challenge instances.
• Longest Path: 20 SNAP collaboration, communication, Internet-routing, and social-network graphs used as open challenge instances.

For any challenge entry with known_optimum = null, treat OPT as unknown to the course and report the feasible solution together with the appropriate valid bound. A published or class best-known feasible result is not an optimum certificate.

See Benchmark Suites for the required benchmark structure and Experimental Evaluation for how challenge results can support the final analysis.

Leaderboard position is not the conclusion

A leaderboard can make the search engaging, but a number by itself is not an algorithmic explanation.

If your result improves substantially, ask:

• What change produced the improvement?
• Does the improvement occur consistently across seeds or instances?
• How much additional computation was required?
• Did the bound improve too, or only the feasible solution?
• What can you claim about the remaining distance to OPT?
• What kinds of instances still defeat the heuristic?

The strongest project does not merely reach the top of a leaderboard. It explains why the algorithm behaves as it does and what the evidence does—and does not—establish.