Heuristic Sets over a Space of Distributions: LLM-based Evolution of Heuristics Beyond a Single Instance Generator

Large language models can design heuristics for combinatorial problems by evolving program code, but the resulting heuristics are designed and tested on instances from a single generator, and independent evaluations report that their advantage disappears, sometimes falling behind hand-written rules, once the instances come from elsewhere. Complementary heuristic sets, as in EoH-S, answer this with several heuristics, but they too are evolved on one generator. We study this problem on online bin packing. We first show that it is not only a weakness of the search: we construct two item-size distributions and compute their optimal policies exactly, and at the same packing state the two require different actions, so no single heuristic minimizes the expected number of bins on every distribution. This grounds the set in the problem and moves the question to what it is evolved on. We construct , a family of 20000 item-size distributions selected from 180000 random candidates by farthest-point sampling in total variation distance, with measured coverage, and we propose , which extends EoH-S to evolve its set over this family: each generation is scored on a fresh mini-batch of distributions, on which surviving members are re-scored before comparison. To use the set online, a selector chooses a member from a prefix of the item stream, by retrieval under TV or $W_1$ or by lookahead simulation. On a BPPLIB suite of 6,064 instances, where six published heuristics designed on Weibull instances are all behind Best Fit, the sets have the lowest gap ($5.92\%$ against $7.11\%$ for Best Fit and $6.32\%$ for EoH-S on its fixed instance set), and on the Weibull benchmark they never saw they are ahead of Best Fit; a lookahead selector realizes part of this online, beating or matching the best fixed choice made in hindsight.