Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems

2025-05-29 · Christopher D. Rosin

Large Language Models (LLMs) with reasoning are trained to iteratively generate and refine their answers before finalizing them, which can help with applications to mathematics and code generation. We apply code generation with reasoning 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. The Constructive Protocol CPro1 uses LLMs to generate search heuristics that have the potential to construct solutions to small open instances. Starting with 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 with reasoning LLMs successfully solves long-standing open instances for 7 of 16 combinatorial design problems selected from the 2006 Handbook of Combinatorial Designs, including new solved instances for 3 of these (Bhaskar Rao Designs, Symmetric Weighing Matrices, Balanced Ternary Designs) that were unsolved by CPro1 with non-reasoning LLMs. It also solves open instances for several problems from recent (2025) literature, generating new Covering Sequences, Johnson Clique Covers, Deletion Codes, and a Uniform Nested Steiner Quadruple System.

📄 PDF Abstract BibTeX arXiv:2505.23881

Code (2)

Kvantify/johnson-clique-cover

constructive-codes/cpro1

Tasks

Code Generation

Learning Splitting Heuristics for Parallel String Solvers

2026-06-09 · Chenhao Gao, Peisen Yao arxiv

String constraint solvers are crucial for reasoning about string-manipulating programs. However, many practical string constraints are undecidable, and real-world applications often present complex constraints that chall…

LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning

2026-05-28 · Elliot Gestrin, Jendrik Seipp arxiv

Heuristic search is the dominant paradigm in symbolic AI planning, and the strongest heuristics are the result of decades of work by planning researchers. Recent work has shown that large language models (LLMs) can desig…

Reasoning Topology Matters: Network-of-Thought for Complex Reasoning Tasks

2026-03-21 · Fan Huang arxiv

Existing prompting paradigms structure LLM reasoning in limited topologies: Chain-of-Thought (CoT) produces linear traces, while Tree-of-Thought (ToT) performs branching search. Yet complex reasoning often requires mergi…

Logical Reasoning

Learning Heuristics for Automated Reasoning through Reinforcement Learning

2019-05-01 · ICLR 2019 5 · Gil Lederman, Markus N. Rabe, Edward A. Lee, Sanjit A. Seshia

We demonstrate how to learn efficient heuristics for automated reasoning algorithms through deep reinforcement learning. We focus on backtracking search algorithms for quantified Boolean logics, which already can solve f…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Learning Heuristics for Quantified Boolean Formulas through Reinforcement Learning

2020-05-01 · ICLR 2020 1 · Gil Lederman, Markus Rabe, Sanjit Seshia, Edward A. Lee

We demonstrate how to learn efficient heuristics for automated reasoning algorithms for quantified Boolean formulas through deep reinforcement learning. We focus on a backtracking search algorithm, which can already solv…