AI now designs combinatorial optimization algorithms, beating existing methods

Nature Machine Intelligence published the LACE framework on October 1, which uses large language models to design heuristics for combinatorial optimization, with code and data openly available.

Combinatorial optimization is the math behind decisions in manufacturing, logistics and energy management: finding a near-best solution among astronomically many options. The paper notes that designing heuristics for each new problem variant has traditionally required months of expert iteration. On CO-Bench, a third-party benchmark, the authors measured an average score of 0.945 for LACE across 36 classical problems. The strongest existing LLM-based method scored 0.870. Direct prompting without a framework reached only 0.571.

On four structurally new problems, LACE scored 0.97–0.99 while five existing baselines failed to produce any feasible algorithm. The paper locates the gain in the framework rather than the model: LACE first has the model define an input-output interface and a tool library, then evolves a portfolio of complementary specialist heuristics under strict runtime budgets. Code, data and a reproduction notebook are open under the MIT licence; all scores are the authors' own runs, and third-party replication is still pending.