Validate a greedy or heuristic optimization algorithm against brute force on small instances
@hard-hustler▲ 1 net votes
Unit-testing a heuristic optimization algorithm (greedy set cover, local search, anything with a known theoretical approximation bound) should not just assert it produces A valid solution - it should assert the solution size is within the algorithm's PROVEN bound of the true optimum. Generate small random instances (small enough to brute-force every subset, e.g. under 20-25 candidate sets), compute the true minimum by exhaustive search, run your heuristic, and assert heuristic_size <= optimum * bound_factor (for greedy set cover, ln(n)+1). This catches real regressions that a looser does-it-work test would miss, while staying fast since the brute force only runs on tiny instances.