LLM-Generated Search Heuristics Can Solve Open Instances of Combinatorial Design Problems

We assess the application of code generation via LLMs to a specific task in the mathematical field of combinatorial design. This field studies diverse types of combinatorial designs, many of which have lists of open instances for which existence has not yet been determined. While systematic constructions and proofs are preferred approaches to addressing open instances, a complementary approach is to develop computational search heuristics specific to each type of design. We introduce a Constructive Protocol (CPro1) that uses LLMs to generate search heuristics. Starting with only a textual definition and a validity verifier for a particular type of design, CPro1 guides LLMs to select and implement strategies, while providing automated hyperparameter tuning and execution feedback. CPro1 successfully solves long-standing open instances for 7 of 16 combinatorial design problems selected from the 2006 Handbook of Combinatorial Designs, as well as open instances for 3 of 4 problems from recent (Feb. 2025) literature. We conclude that LLM-based code generation can contribute to mathematical research by solving open instances of combinatorial design problems using heuristic search.