Optimization finds much harder problem instances for testing algorithms
Hard Instances on Demand
Data Structures and AlgorithmsArtificial Intelligence
Summary
Testing how well computer programs solve hard problems depends a lot on the examples they try. The authors treat finding these tricky examples like a puzzle, using a tool that tweaks problem details to make the program run slower. They showed this works on four tough problems, creating examples that challenge solvers more than typical random ones or some famous benchmarks. This helps better test and improve problem-solving software.
What this means in practice
- •For algorithm developers: Create challenging test problems that better reveal strengths and weaknesses of new or existing algorithms for NP-hard challenges.
- •For operations research practitioners: Use hard scheduling and routing problem instances found by optimization to evaluate and improve commercial solvers used in logistics and production planning.
Authors
Jamie Fravel, Martin Koutecký, Pavlo Tsitsei
Abstract
The conclusions of an experimental study of algorithms are only as good as the instances they are run on. Benchmark libraries for well-studied problems took decades to curate, while evaluations of new problems often fall back on random instances, which are known to be misleading: they may say more about the random generator than about the algorithmic question at hand. We treat instance generation as an optimization problem: parameterize the instance space, take the solver's running time as the objective, and let a black-box optimizer search for hard instances. We develop a widely applicable workflow built on the Nevergrad optimization platform and demonstrate it on four NP-hard problems: satisfiability, traveling salesperson, Hamiltonian cycle, and non-permutation flow-shop scheduling. The search needs only the solver, an instance encoder, and a compute budget. Our evolved instances beat the hardest instance of a budget-matched random draw in all four case studies, by an order of magnitude or more in three. They are often competitive with long-curated benchmark sets: our SAT champion is harder (for a three-solver portfolio) than 78% of the 498 SAT Competition formulas in its size class; our 20-city TSP champions take several times longer than the hardest measured classical TSPLIB instance (229 cities); and our flow-shop champion takes 238.6 seconds of CP Optimizer time to solve to proven optimality (versus 4.5 seconds for the hardest of 100,000 random draws) while denying CP-SAT an optimality proof. The optimizer even recovers known structure from running time alone: it locates a SAT clause/variable ratio near the phase transition and finds structurally different champions for the two scheduling engines.