Large language models discover complementary heuristics for combinatorial optimization

Problem

This work addresses the gap in designing effective heuristics for combinatorial optimization (CO) problems. The authors propose a novel approach using large language models (LLMs) to enhance algorithmic reasoning and heuristic generation, which is particularly relevant given the increasing complexity of CO problems. The paper is a preprint and has not yet undergone peer review.

Method

The authors introduce the LLM-driven Algorithm Construction via Complementary Evolution (LACE) framework. LACE consists of several key components:

• Input Schema: Defines the problem contract, ensuring that the model understands the specific requirements of the CO problem at hand.
• Output Schema: Guides the model's capacity towards high-level algorithmic reasoning, facilitating the generation of effective heuristics.
• Tool Library: A collection of tools designed for heuristic generation, which the model can utilize to construct solutions.
• Heuristic Portfolio: This is refined through a process termed time-constrained complementary evolution, which iteratively improves the heuristics based on performance feedback. The training compute used for LACE is not specified, and the framework is evaluated on a dataset comprising 36 classical CO-Bench problems.

Results

LACE achieves an average score of 0.945 on the benchmark, outperforming the strongest existing LLM-based method, which scored 0.870. Additionally, LACE scores between 0.97 and 0.99 on four structurally new problems, while five existing LLM-based baselines failed to produce feasible algorithms for these problems. These results indicate a significant advancement in the capability of LLMs to generate effective heuristics for CO tasks.

Limitations

The authors do not report any limitations in the study. However, the lack of specified training compute may raise questions regarding the reproducibility and scalability of the proposed method in different contexts.

Why it matters

The implications of this work are substantial for downstream research in combinatorial optimization and algorithm design. By demonstrating that LLMs can effectively discover complementary heuristics, this research opens avenues for further exploration into the application of LLMs in other complex problem domains. The framework could potentially lead to more efficient algorithms that adapt to various CO problems, enhancing the overall performance of optimization tasks in practical applications.