Challenges & Leaderboards

Once your heuristic reliably returns valid solutions, the next question is not merely whether it works. It is:

How much better can you make the solution, and what can you actually say about its quality?

The project uses optional challenge benchmarks and leaderboards to give you a reason to keep improving a heuristic after you already have a feasible answer. The leaderboard is intended as a design challenge and source of experimental evidence, not as the primary basis for your grade.

You may be competing with another team, a published best-known result, or simply your own previous best solution. On the most interesting challenge instances, the true optimum may be unknown.

A greedy answer is a starting point

A simple greedy construction is often a useful first heuristic. In this project, however, heuristic1 is designed to support repeated improvement rather than one deterministic pass.

Depending on the problem, useful techniques may include:

• randomized tie-breaking or randomized construction;
• multiple starts or random restarts;
• iterative improvement or local search;
• rebuilding from promising partial solutions;
• keeping the best solution found so far; and
• an anytime strategy that can return a valid solution now and continue searching for a better one while more computation is available.

Checkpoint 2 requires best-so-far behavior for randomized/repeated heuristics. The challenge benchmarks give that requirement a purpose: extra attempts should have the opportunity to improve the solution instead of replacing a good result with a worse one.

Three kinds of comparison

1. Known optimum

If the benchmark has a proven optimum, solution quality can be measured directly.

For a minimization problem, for example, the percentage gap is $100\cdot\frac{\text{solution}-OPT}{OPT}$.

For a maximization problem, use the analogous gap in the correct direction.

Repeated randomized runs should be summarized across the fixed course seeds rather than by selecting one unusually lucky run.

2. Open challenge: OPT is unknown

For an open challenge, do not invent an optimum.

Suppose a minimization problem has:

team's best feasible solution = 137
valid lower bound            = 121
known OPT                    = none

Then the evidence supports $121 \le OPT \le 137$.

If another team later finds a feasible solution of 132, that is a better known solution, but it still does not prove that $OPT=132$.

For an open challenge, a leaderboard should therefore distinguish among:

• the team’s best feasible objective value;
• the best feasible value currently known to the class or published externally;
• the team’s independently computed bound; and
• whether an optimum has actually been proven.

3. Competing with yourself

A useful challenge does not require multiple teams on the same problem. Track the progress of your own method:

initial greedy result
best after local improvement
best after 10 restarts
best after 100 restarts
best within the course time limit

This makes the tradeoff between additional computation and solution quality visible and gives you evidence for deciding whether an improvement technique is actually worthwhile.

Fair comparisons

When results are compared on a class leaderboard, use the same:

• benchmark instance;
• course-specified time limit or attempt budget;
• fixed seed set when randomization is being compared; and
• objective definition and verifier.

The goal is not to reward whoever happened to run the algorithm longest on the fastest computer. The course experiment runner records the benchmark metadata needed to make comparisons reproducible.

Current challenge collections

The core benchmark suites remain the required basis for the Final Project. The repository also provides problem-specific challenge collections installed through python tools/setup_project.py:

• Traveling Salesperson: known-OPT leaderboard and reach instances plus a 20-instance University of Waterloo VLSI open challenge. Every selected VLSI instance has a published best-known tour; six also have published Concorde lower bounds, while the remaining instances rely on the team’s own valid lower bound for the certified lower side of the interval.
• Minimum Vertex Cover: 20 PACE 2019 Vertex Cover Exact instances selected from rows for which the cited PACE result tables did not publish a minimum-cover value.
• Minimum Graph Coloring: 20 DIMACS/COLOR challenge instances, including long-standing open DIMACS cases and real optical-network coloring instances.
• Maximum Clique: 20 SNAP social-network graphs used as open challenge instances.
• Longest Path: 20 SNAP collaboration, communication, Internet-routing, and social-network graphs used as open challenge instances.

For any challenge entry with known_optimum = null, treat OPT as unknown to the course and report the feasible solution together with the appropriate valid bound. A published or class best-known feasible result is not an optimum certificate.

See Benchmark Suites for the required benchmark structure and Experimental Evaluation for how challenge results can support the final analysis.

Leaderboard position is not the conclusion

A leaderboard can make the search engaging, but a number by itself is not an algorithmic explanation.

If your result improves substantially, ask:

• What change produced the improvement?
• Does the improvement occur consistently across seeds or instances?
• How much additional computation was required?
• Did the bound improve too, or only the feasible solution?
• What can you claim about the remaining distance to OPT?
• What kinds of instances still defeat the heuristic?

The strongest project does not merely reach the top of a leaderboard. It explains why the algorithm behaves as it does and what the evidence does—and does not—establish.