Final Project: Experimental Investigation and Synthesis

Goal: Use the completed algorithms and bound to determine where the methods are practical, how heuristic solution quality behaves, what characteristics of an instance affect algorithm behavior, and what conclusions are justified by the evidence.

Points: 30

The Final Project combines the experimental investigation and final synthesis into one submission. 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.

Checkpoint 1 and Checkpoint 2 already assessed the exhaustive baseline, improved exact solver, bound, and first heuristic. Those components remain necessary because the final experiments depend on them, and the final submission may run mechanical continuity checks, but the Final Project does not award a second set of points simply for re-demonstrating work that was already graded.

Part A: Complete the Remaining Team-Size Requirement

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 its algorithmic strategy is genuinely different.

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

The goal is not to guarantee that the second heuristic is better. A well-motivated heuristic that performs poorly on some instances can still produce valuable experimental evidence. For three-person teams, the Final Project assesses whether heuristic2 is valid, meaningfully different, and incorporated thoughtfully into the experimental comparison.

Part B: Investigate Algorithm Behavior

The project template provides a course-controlled experiment runner and problem-specific benchmark suites. 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 analysis.

Before beginning the final investigation, review Experimental Evaluation for guidance on benchmark comparisons, repeated randomized trials, bounds, structural experiments, and reproducibility.

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 Final Project requirements.

B1. Exact-search frontier

Use the course-provided exact_frontier 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 and scale suites to evaluate heuristic1 and, for three-person teams, heuristic2.

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 2 (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.

For randomized heuristics, use the repeated course-provided seeds to discuss variability rather than drawing conclusions from a single lucky or unlucky run.

Optional challenge/leaderboard results may strengthen this analysis, especially when they show how a heuristic improves with additional restarts, local search, or algorithm revisions. Leaderboard position alone is not sufficient evidence. For open instances, clearly distinguish a best-known feasible solution from a proven optimum and use the appropriate bound to describe what remains unknown.

B3. Effect of instance structure

Use the course-provided structure benchmark suite for your assigned problem. The benchmark suite varies one meaningful structural characteristic while controlling other important aspects of the instances as much as practical.

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

• exhaustive or improved-exact computational effort;
• the practical boundary of exact computation;
• heuristic solution quality; or
• the gap between a feasible heuristic solution and the certified bound.

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

Part C: Synthesize and Communicate the Investigation

C1. Final report

Store the report in:

reports/final.pdf

Aim for approximately three pages of text, not counting figures, tables, and references. Do not repeat the checkpoint reports. Instead, synthesize the investigation around four questions:

1. What approaches did you try? Briefly identify the exhaustive exact, improved exact, and heuristic approaches needed to understand the results.
2. What happened? Present the most important experimental evidence rather than an inventory of every run.
3. Where did the methods work or fail? Discuss the exact-search frontier, heuristic quality, what the bound certifies when OPT is unavailable, and the effect of input structure.
4. What did you learn? State the most important conclusions supported by the evidence.

Your informative instance or related group of instances should appear in the final report or presentation.

C2. Class presentation

Tell the story of the investigation rather than reproducing the report section by section. Address the problem studied, where exhaustive search became impractical, what the improved exact approach changed, how the heuristic strategy or strategies behaved, what the bound could certify when OPT was unavailable, the most informative structural or instance-level result, and what surprised the team.

Every team member must present a meaningful portion of the project. Figures, tables, or example instances should be readable and chosen because they support the story rather than because they happen to be available.

Store the final slides in:

presentation/slides.pdf

C3. Peer questions and discussion

Each team will be assigned at least one other team’s problem or presentation to examine and will submit three substantive questions:

• one about an algorithmic decision;
• one about experimental evidence; and
• one about whether an idea could transfer between the two problems, or why the problems behave differently.

Formative Experimental Check

Before the Final Project is due, there will be a lightweight formative check rather than another graded checkpoint. Be prepared to show that the required experiment pipeline is running, bring at least one preliminary result or figure, and explain the story you currently expect the final presentation to tell.

The purpose of this check is to identify experimental or presentation problems while there is still time to correct them. It does not create another Gradescope submission or another set of project points.

Grading

Submission checklist

• The previously graded required algorithms and bound still run through the documented interfaces so that the final experiments are reproducible.
• Three-person teams have a valid, meaningfully different heuristic2 and include it in the heuristic comparison.
• The required course-provided experimental suites have been run using the provided infrastructure.
• The exact-search frontier is analyzed using the exhaustive and improved exact solvers.
• Heuristic quality is evaluated against known optima where available.
• On larger instances, heuristic results are interpreted together with the implemented bound rather than treating an unknown optimum as known.
• The required problem-specific structural benchmark family is analyzed.
• At least one informative instance or related group of instances is identified and explained.
• reports/final.pdf is complete.
• presentation/slides.pdf is complete.
• All current work and generated experiment results have been committed and pushed to GitHub.
• The repository has been submitted to the Final Project Gradescope assessment with all team members included in the Gradescope group.

Assessment. Gradescope may be used for mechanical validation of interfaces, required artifacts, and experiment-result structure. The substantive Final Project points are instructor-reviewed according to the table above.