Large language models discover complementary heuristics for combinatorial optimization

Combinatorial optimization (CO) is essential across science, engineering and industry, but designing effective heuristics for each new problem variant demands deep domain knowledge and months of expert iteration. This paper introduces LACE (LLM-driven Algorithm Construction via Complementary Evolution), a framework that decomposes algorithm design into an input schema, output schema, tool library and heuristic portfolio—the I-O-T-H interface—and refines the portfolio through time-constrained complementary evolution. This interface defines a verified problem contract that directs the large language model's capacity toward high-level algorithmic reasoning instead of problem-specific implementation, while complementary evolution iteratively generates and selects specialist heuristics that can solve heterogeneous instances within strict runtime budgets. Across 36 classical CO-Bench problems, LACE achieves an average score of 0.945, compared with 0.870 for the strongest existing LLM-based method and 0.571 for direct LLM prompting without any framework, indicating that the gain comes from the framework rather than the model. On four structurally new problems, LACE reaches 0.97–0.99, whereas five existing LLM-based baselines fail to produce any feasible algorithm. These results demonstrate that effective algorithm discovery for such problems can be substantially automated.

(Source：Nature)