The conclusions of experimental studies depend on the quality of the instances used. Traditional benchmark libraries take decades to curate, while evaluations of new problems often rely on random instances that can be misleading because the results may reflect the generator rather than the algorithm itself. We treat instance generation as an optimization problem: parameterize the instance space, use the solver's running time as the objective, and let a black‑box optimizer search for hard instances. Built on the Nevergrad platform, we propose a generic workflow and validate it on four NP‑hard problems—satisfiability (SAT), traveling salesperson (TSP), Hamiltonian cycle, and non‑permutation flow‑shop scheduling. The search requires only a solver, an instance encoder, and a compute budget.
In all four case studies the evolved instances outperform a budget‑matched random draw, with three of them improving by an order of magnitude or more. 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 the same size class; our 20‑city TSP champions take several times longer than the hardest classical TSPLIB instance (229 cities); and our flow‑shop champion needs 238.6 seconds of CP Optimizer time to prove 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‑to‑variable ratio near the phase transition and discovers structurally different champions for the two scheduling engines.
Review: This approach demonstrates the feasibility of using black‑box optimization to directly generate high‑quality hard instances, providing a more reliable tool for algorithm evaluation and pointing toward automated benchmark construction.