Beyond Brute Force — CP4 Experiment Infrastructure Plan

Design principle

Checkpoint 4 should assess experimental reasoning, not whether students can build a benchmarking framework. The course should provide the required instance collections, runner, timing, validation, metadata, and result-file format. Students run the experiments, inspect the resulting data, and explain what the evidence shows.

The infrastructure should also make instructor validation easy: required results are machine-generated in a standard format, benchmark instances are course-controlled, and Gradescope can rerun a small subset of the same manifest.

Proposed student-visible layout

benchmarks/
  minimum_vertex_cover/
    manifest.json
    exact_frontier/
    quality_known/
    heuristic_scale/
    structure/
  ... one directory per problem ...

tools/
  run_experiments.py
  experiment_framework/
    runner.py
    validation.py
    problem_checks/

experiments/
  results.csv
  results.json
  run_metadata.json

benchmarks/ and tools/experiment_framework/ are COURSE INFRASTRUCTURE. Students should not need to modify them. experiments/ contains generated results that students commit with CP4.

Required benchmark suites

Each problem manifest should define four course-provided suites. The manifest, rather than student code, decides which algorithms run on which instances and what timeout/repeat policy applies. This prevents students from accidentally running exhaustive search on instances where it can never finish.

1. exact_frontier

Purpose: determine where straightforward exhaustive search becomes impractical and how much farther the improved exact solver reaches.

• Runs exhaustive and improved on an ordered family of increasingly challenging instances.
• Uses instructor-controlled wall-clock timing.
• Records TIMEOUT as a legitimate experimental outcome rather than a failed experiment.
• Uses known optima so correctness remains checkable.

2. quality_known

Purpose: measure heuristic quality and bound quality while OPT is still known.

• Runs the required heuristic(s) on instances with known optimum.
• Runs the CP3 bound function on the same instances.
• Records heuristic objective, OPT, bound, and the certified interval.
• Uses a small fixed set of course-provided seeds for randomized heuristics so variability can be observed without students manually managing runs.

3. heuristic_scale

Purpose: evaluate useful solutions after exact computation is no longer practical.

• Runs the heuristic(s) and the bound, not straightforward exhaustive search.
• The improved exact solver may be run only on instances specifically designated as feasible in the manifest.
• OPT may be unknown. The student interprets the feasible heuristic value together with the certified bound rather than claiming optimality.

4. structure

Purpose: examine how one controlled characteristic of the input affects behavior.

• The course supplies the instances and identifies the structural variable.
• Use several instances per structural setting when randomness is involved, rather than drawing conclusions from one graph.
• Keep size and other major variables fixed or documented as closely as practical.

Initial structural-family plan:

The TSP family should be finalized only after instructor pilot runs confirm that it produces an interpretable algorithmic effect; graph density is not meaningful because all TSP instances are complete.

Bound interface used by the runner

Each problem package exposes course-controlled metadata and dispatch:

BOUND_KIND = "lower"   # or "upper"

def get_bound():
    ...                 # returns the student's required bound function

The student implementation remains mathematically natural inside bound.py:

def lower_bound(instance) -> int | float:
    ...

or

def upper_bound(instance) -> int | float:
    ...

Proposed directions for the five current problems:

• Minimum Vertex Cover: lower bound
• Traveling Salesperson: lower bound
• Minimum Graph Coloring: lower bound
• Maximum Clique: upper bound
• Longest Path: upper bound

This lets a student reuse the same function inside branch-and-bound while the experiment runner can call it generically through get_bound().

Runner behavior

The intended commands are simple:

python tools/run_experiments.py --suite exact_frontier
python tools/run_experiments.py --suite quality_known
python tools/run_experiments.py --suite heuristic_scale
python tools/run_experiments.py --suite structure

A convenience --all option can run all required suites.

The runner should:

1. read assigned_problem from project.json;
2. load the course manifest for that problem;
3. run only the algorithms specified for each benchmark row;
4. measure wall-clock time independently with perf_counter();
5. retain student-reported statistics separately rather than trusting them as timing evidence;
6. run the problem’s independent course validator on every returned solution;
7. call the CP3 bound function once per instance;
8. record known OPT when supplied by the manifest;
9. use fixed manifest-provided seeds for randomized runs;
10. write both row-oriented CSV and full JSON results; and
11. never abort an entire suite because one algorithm times out on one instance.

For short-running exact cases, the manifest can request multiple repetitions and the runner can report the median instructor-timed runtime. Long-running cases should normally use one repetition to keep the CP4 workload reasonable.

Proposed result columns

At minimum, each generated row should contain:

problem
suite
instance_id
instance_sha256
size metadata (for example n and m)
structure_name
structure_value
algorithm
seed
status          # OK / TIMEOUT / ERROR
valid           # independent feasibility check
objective
known_optimum
bound_kind
bound_value
wall_time
student_time
statistics_json

The JSON output can preserve additional problem-specific metadata without making the CSV unwieldy.

What students should actually have to analyze

To keep CP4 from becoming overloaded, the required intellectual work should stay to three core comparisons plus one explanatory example:

1. Exact frontier: Where does exhaustive search stop being practical, and what does the improved exact method buy?
2. Heuristic quality: How close are heuristic results to OPT on small instances, and what can the bound certify on larger instances?
3. Structural effect: How does the one course-selected structural variable affect performance or solution quality?
4. Informative instance: Identify and explain one especially revealing case from any of the three analyses.

Students should not be required to invent additional benchmark families, write timing code, write CSV code, or build plotting infrastructure. Additional experiments remain optional extensions.

Instructor / Gradescope validation strategy

The CP4 autograder should not attempt to grade the students’ scientific conclusions. It can cheaply validate the experimental foundation:

• required generated files exist and have the expected schema;
• every required suite and instance ID is represented;
• required algorithms were run where the manifest says they should be run;
• bound values have the correct direction on known-optimum instances;
• reported solution objectives agree with independent validation;
• fixed seeds and instance hashes match the course manifest; and
• a small hidden subset can be rerun to catch fabricated or stale result files.

Instructor review then evaluates the interpretation, plots/tables, structural reasoning, and informative-instance explanation.

Suggested implementation order

1. Finish the MVC path first: create the four MVC CP4 suites and the generic runner.
2. Use MVC to settle the result schema and CP4 autograder checks.
3. Reuse the framework for Clique, Coloring, Longest Path, and TSP by supplying problem adapters, bound metadata, and manifests.
4. Pilot each structural family before publishing it to students; especially pilot the TSP weight-structure family.