Let’s see if we can use code generation to construct novel solutions to interesting problems.

Jan. 29, 2025: The Handbook of Combinatorial Designs is an extensive catalog of different types of combinatorial designs: Balanced Incomplete Block Designs, Costas Arrays, Weighing Matrices, etc. For many of these, it lists open instances of the existence problem: given a set of parameters describing the design, does a solution exist with these parameters that meets the constraints required by this type of combinatorial design? These are beautiful problems, with simple constraints and instances that are described by just a few numbers (e.g. size).

The protocol CPro1 uses an LLM to generate code that attempts to construct solutions to instances of combinatorial design existence problems. For each problem, it generates and tunes 1000 candidate programs – enough to experiment with a variety of techniques and variations. Testing it on 16 different types of combinatorial designs from the Handbook, it is able to resolve small open instances for 6 of them.

Rosin, C.D. (2025) “Using Code Generation to Solve Open Instances of Combinatorial Design Problems.” https://arxiv.org/abs/2501.17725

On GitHub: Code and Result Files