{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.22637",
  "author_total": 3,
  "authors": [
    {
      "name": "Jamie Fravel"
    },
    {
      "name": "Martin Koutecký"
    },
    {
      "name": "Pavlo Tsitsei"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/apxvd8q0h785q.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.22637",
  "fulltext_url": null,
  "id": "apxvd8q0h785q",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.22637",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.AI"
    ],
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.OC"
    ],
    [
      "openalex",
      "1705|Constraint Satisfaction and Optimization"
    ]
  ],
  "openalex": "W7222956178",
  "pdf_url": "https://arxiv.org/pdf/2610.22637",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-15",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/apxvd8q0h785q.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:30:37Z",
      "native_id": "2610.22637",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.22637"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    }
  ],
  "title": "Hard Instances on Demand",
  "title_text": "Hard Instances on Demand",
  "type": "preprint",
  "updated_at": "2026-10-30T12:33:31Z",
  "url": "https://research.draconitic.com/paper/apxvd8q0h785q",
  "venue": "arXiv",
  "versions": []
}