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.