Checkpoint 4: Experimental Investigation

Goal: Use the completed algorithms and bound to determine where the methods are practical, how solution quality changes when exact computation is no longer available, and what characteristics of an instance affect algorithm behavior.

Checkpoint 4 shifts the emphasis from implementation to controlled experimental investigation. The course provides the required benchmark collections and experiment-running infrastructure. You are not required to write a benchmark harness or create the required benchmark universe yourself.

Part A: Extend the Algorithm Portfolio

A1. Second heuristic for three-person teams (heuristic2.py)

Three-person teams must implement a functioning heuristic2 that is meaningfully different from heuristic1.

A second heuristic must differ in algorithmic strategy, not merely in parameters, time limits, restart counts, random seeds, or other tuning choices. It may be deterministic if the underlying method is genuinely different.

Two-person teams are not required to implement a second heuristic. They may do so as an approved extension.

Part B: Investigate Algorithm Behavior

The project template provides a course-controlled experiment runner and problem-specific benchmark suites. The required suites are organized around different computational regimes and experimental questions. The runner records the instance, algorithm, seed, course-controlled wall-clock time, returned objective value, bound value, known optimum when available, and other metadata needed for later analysis.

Students are responsible for running the required experiments, checking the resulting data, and interpreting what the data means. You may add your own instances or experiments, but the course-provided suites are sufficient to satisfy the core Checkpoint 4 requirements.

B1. Exact-search frontier

Use the course-provided exact-search benchmark suite to compare the exhaustive solver (exhaustive.py) with the improved exact solver (improved.py).

Identify where exhaustive search becomes impractical and how much farther the improved exact method extends exact computation. Your analysis should focus on the change in practical solvability, not merely on reporting individual running times.

B2. Heuristic quality and certified bounds

Use the course-provided quality suites to evaluate the first heuristic (heuristic1.py) and, for three-person teams, the second heuristic (heuristic2.py).

For instances whose optimum is known, compare heuristic solution quality directly with the optimum and examine how informative the implemented bound is.

For larger instances where the exact optimum is not available within the allowed computation time, use the bound on the optimal solution value implemented in Checkpoint 3 (bound.py) together with the best feasible solution found by the heuristic. Interpret the resulting interval correctly. Do not describe an unknown value as optimal merely because the exact solver did not finish.

B3. Effect of instance structure

Instance structure can affect algorithm behavior for exact solvers and solution quality for heuristic approaches. In this section, you will investigate one such effect using the course-provided structure benchmark suite for your assigned problem.

The benchmark suite identifies the structural characteristic being varied and provides instances designed to vary that characteristic while controlling other important aspects of the instances as much as practical.

Analyze how that characteristic affects at least one of the following:

The required structural characteristic is specified with the benchmark family for your problem. You are not required to invent a structural variable or generate the required instances yourself.

B4. Informative instance and explanation

Select at least one instance or small group of related instances that reveals something important about the algorithms. Examples include an unexpectedly difficult instance, an unexpectedly easy instance, a case where the heuristic performs unusually well or poorly, a sharp change in exact running time, or a case where the bound is particularly strong or weak.

Explain what the evidence shows and give a plausible algorithmic explanation. Distinguish measured evidence from hypotheses about why the behavior occurred.

Checkpoint report

Focus on what the experiments reveal rather than repeating the implementation descriptions from earlier checkpoints. Organize reports/checkpoint4.pdf around the four investigation topics above. For three-person teams, briefly describe the second heuristic where it is needed to interpret the comparison.

The report should emphasize a small number of well-supported observations rather than a large collection of unexamined tables.

Presentation outline

Prepare a concise outline of the final presentation in:

presentation/outline.pdf

The outline should identify the intended story of the presentation: the problem, where straightforward exhaustive search became impractical, what the improved exact method changed, how the heuristic or heuristics behaved, the role of the bound when OPT was unavailable, the most informative structural or instance-level result, and the conclusions the team expects to emphasize.

Submission checklist

Assessment. Gradescope will verify the required algorithm interfaces, bound interface, experiment-result artifacts, and other mechanical requirements. Instructor review will focus on the quality of the experimental comparisons, correct interpretation of optima and bounds, evidence about structural effects, and the explanations supported by the observed data.