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.
Figures & tables
Figure 2.1: The evaluation pipeline. Bottom: one evaluation – the optimizer asks for a genome, the encoding decodes it into an instance, the solver solves it k times, the aggregated time is transformed into a loss and told back to the optimizer. Top: the screening stage (Stage 1) runs this loop for every optimizer with budget B and several independent runs per configuration (task, encoding, loss transform F ).
Case
Champion train/held-out
Random control train/held-out
Context: external benchmarks and properties
SAT portfolio
12.0
0.47
phase-transition random 0.94; van der Waerden >60 ; SAT Comp: only expert-designed families harder
TSP, Shiwa U=103
13.5 / 7.99
0.70 / 0.79
gr229 2.34 / 2.24; Hard-TSPLIB >60
HAM
1.12 / 0.48
0.35 / 0.28
density-matched random G(20,0.22) : 0.26 / 0.17; FHCP is stronger at larger sizes
NPFS, CP-Opt 10×5
238.6 / 235.3
4.50
proven optimal on all 30 seeds; CP-SAT finds no proof within 600 s; hardest official VRF 10×5 under NPFS: 3.8 s; hardest official Taillard 20×5 : 4.5 s (seeds 1–7)
NPFS, CP-Opt 8×4
7.24 / 7.03
0.67 / 0.65
bred on CP-Opt , exceeds CP-SAT ’s cap; Taillard starts at 20×5 , Demirkol at 20×15
Table 3.1: Primary results in seconds on the reference machine. A slash separates train from held-out; single entries have no held-out value. The TSP control is the conservative best-held-out RandomSearch result.
family
n
m
minisat
BID+cdc
CMS
kissat
march
random, ratio 4.27
200
854
0.94
1.06
6.31
1.18
0.12
PHP 1112
132
738
> 60
0.009
> 60
36.2
59.6
Tseitin expander
150
400
> 60
0.008
0.80
10.4
> 60
W(2;3,13)
160
7308
> 60
> 60
> 60
> 60
> 60
RS (kcnf)
200
1000
0.07
0.10
0.16
0.19
0.02
RS (mprefix)
200
852
0.47
0.62
2.45
0.59
0.08
Table 3.2: SAT: per-solver times in seconds on the reference machine, cap 60 s; each entry is the median of five sequential evaluations. The portfolio objective is the minimum over the first three solvers (bold); kissat and march are context only. All listed instances are unsatisfiable. The first row (phase-transition) is one measured random formula; the RS rows are the hardest instances found by budget-matched RandomSearch . The Tseitin row is a fresh formula of the same size class from the Global Benchmark Database.
family
N
train
held-out
random Euclidean, hardest of draw
20
0.08
0.07
TSPLIB, median
≤ 300
0.097
–
TSPLIB, hardest (gr229)
229
2.34
2.24
clustered Euclidean (our generator), median
50–200
0.17
–
Hard-TSPLIB, hardest solved
20
33.8
28.7
Hard-TSPLIB (23 of 40)
10–76
> 60
–
Table 3.3: TSP: median Concorde process time in seconds on the reference machine, cap 60 s. Train = breeding seeds 1–7; held-out = unseen seeds 8–30. Generated instances and the two fixed comparators (gr229, hardest solved Hard-TSPLIB) use three repetitions per seed; the broad TSPLIB, clustered, and Hard-TSPLIB scans use one solve per seed. Random draws use budget 100,000 , matching the U=1000 setup and twice the DiagonalCMA budget.
family
N
train
held-out
random G(20,0.22)
20
0.26
0.17
random cubic
20
0.04
0.01
FHCP, hardest solved on all seeds
108
7.88
–
FHCP, 6 of 11 scanned members
90–150
> 60
–
RandomSearch , best of three encodings
20
0.35
0.28
champion TwoPointsDE (scores + threshold)
20
0.61
0.27
Table 3.4: HAM: median Concorde process time in seconds, cap 60 s. Train = breeding seeds 1–7, held-out = seeds 8–30. Generated instances use three repetitions per seed; the FHCP scan uses one solve per seed.
family
n×m
CP-SAT
CP-Opt
held-out
champion, CP-SAT arm
6×4
18.2
0.33
16.3
RandomSearch , same arm
6×4
0.21
0.02
0.25
champion, CP-Opt arm
6×4
0.78
0.54
0.52
RandomSearch , same arm
6×4
0.14
0.18
0.18
RandomSearch , uniform
8×4
–
0.67
0.65
champion (DiagonalCMA)
8×4
> 60
7.24
7.03
Table 3.5: Non-permutation flow shop: median process time in seconds per engine, cap 60 s except 600 s for 10×5 . Engine columns use evaluation seeds 1–7; the last column uses the champion’s own engine on seeds 8–30. Random rows are the hardest of 100,000 fresh draws (for the CP-SAT arm this exceeds the search budget, a conservative comparison). In the > -entries, CP-SAT found a feasible schedule but no optimality proof within the cap.
encoding / optimizer
−t
−logt
−t2
HAM, adjacency matrix (triv)
NGOptRW
1.14
0.82
–
NgIohMLn
0.83
1.05
0.63
RecombiningDiscreteLenglerOnePlusOne
0.56
0.99
0.80
HAM, edge scores + edge count (pint)
NgIohRS
0.89
0.87
0.86
Table A.1: Screening (budget 15,000, 2 runs): best instance hardness in seconds after the screening campaign’s own clean rebench (not the final reference machine of section B ), per loss transform. Only rankings and relative magnitudes are used from this table. Three best optimizers per encoding; “–” = combination not sampled.