Experimental Evaluation

The experimental study is a team activity and is the point where the different algorithmic approaches come back together.

Your team will compare:

the exhaustive exact algorithm;
the improved exact algorithm;
heuristic 1; and
heuristic 2, for three-person teams.

The goal is not simply to determine which program is fastest or which heuristic wins the most benchmark cases. The goal is to understand where each approach works, where it struggles, and why.

Ground Truth and Bounds

Whenever possible, compare heuristic solutions with an exact optimum.

The instructor may provide precomputed optimal values for part of the benchmark collection. These values allow heuristic development and analysis to proceed independently of the speed of your team’s exact implementation.

When an exact optimum is unavailable, use a valid lower or upper bound when appropriate for your problem.

Coverage

For a heuristic, one useful measurement is the fraction of benchmark instances on which the heuristic finds an optimal solution:

\mathrm{coverage} = \frac{N_{\mathrm{opt}}}{N_{\mathrm{tested}}}

where $N_{\mathrm{opt}}$ is the number of benchmark instances on which the heuristic finds an optimal solution and $N_{\mathrm{tested}}$ is the number of instances tested.

Coverage is not sufficient by itself. Two heuristics can have the same coverage while behaving very differently on the instances they miss. You should also measure the magnitude of the error or gap from the optimum.

Depending on your problem, useful measurements may include:

absolute gap from OPT;
relative or percentage gap from OPT;
best, worst, mean, and median result across repeated trials;
time to first feasible solution;
improvement as additional trials or time are allowed; and
variability across random seeds.

Input Structure

Input size alone may not explain algorithm difficulty.

Your experiments should therefore examine at least one meaningful structural characteristic of the input in addition to its size.

For an undirected graph $G=(V,E)$ , graph density is:

d = \frac{2|E|}{|V|(|V|-1)}

A density of 0 represents a graph with no edges, while a density of 1 represents a complete graph.

For graph problems, benchmark collections may include all non-isomorphic graphs of selected sizes. This permits a systematic study of questions such as:

Does the heuristic behave differently on sparse, intermediate-density, and dense graphs?
Are there density ranges where finding an optimum is unusually difficult?
Does pruning effectiveness depend on density or another structural feature?
Do two different heuristics fail on the same graphs?
Is the number of vertices alone a good predictor of difficulty?

Do not assume in advance that sparse, intermediate, or dense instances must be easier or harder. Treat these as empirical questions and let the data support your conclusions.

Problem specifications for non-graph problems will identify analogous structural measurements when appropriate.

Exact-Search Measurements

Running time is important, but it often does not explain why an improved exact algorithm performs differently.

Collect statistics appropriate to your implementation, such as:

recursive calls;
states expanded;
branches pruned;
candidate solutions considered;
bound computations;
maximal partial solutions reached; or
another meaningful measure of search effort.

Use these measurements to compare the exhaustive and improved exact algorithms.

Interesting and Difficult Instances

Your team must identify at least one benchmark instance that helps explain an important feature of your algorithms.

Examples include:

a small instance that causes a heuristic to perform poorly;
an instance where two heuristics behave very differently;
an instance where pruning is unusually effective;
an instance where pruning provides almost no benefit;
an instance that takes much longer than other inputs of similar size; or
another surprising or informative case.

You should be able to show or describe this instance and explain what happens algorithmically.

For a graph problem, this may mean drawing the graph and tracing the choices that cause a heuristic to succeed or fail.

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 the scripts and instructions needed to reproduce the important experiments reported in the final submission.

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

which benchmark instances were used;
which algorithm and parameters were run;
which random seeds were used when relevant; and
how the reported tables or figures were produced.

Benchmark Evaluation

Some benchmark evaluation may be run using instructor-provided infrastructure.

The benchmark is intended to provide a consistent collection of inputs and to encourage robust algorithm design. A leaderboard may be used, but leaderboard position is not the primary goal of the project.

A strong final analysis explains the behavior behind the numbers rather than merely reporting a score.