In a recent paper, Camilo Chacon Sartori and Christian Blum explore the intersection of Large Language Models (LLMs) and optimization algorithms, demonstrating that these models can not only understand but also improve upon complex, expert-designed code. Their work focuses on the Construct, Merge, Solve & Adapt (CMSA) algorithm, a hybrid metaheuristic for combinatorial optimization problems, specifically applied to the Maximum Independent Set (MIS) problem—a classic NP-hard challenge with applications in network design and bioinformatics.
The authors leverage GPT-4o to enhance CMSA, starting with a 400-line C++ implementation. Through iterative prompting, the LLM proposes novel heuristics, such as incorporating the "age" parameter—a measure of how long a solution component has been part of the subproblem—into the vertex selection process. This dynamic heuristic, which balances vertex degree and age, outperforms the original expert-designed heuristic, particularly on larger and denser graphs. The LLM further suggests entropy-based adjustments to increase selection diversity, though this refinement proves less effective in practice.
Beyond algorithmic improvements, the authors explore code-level optimizations, prompting GPT-4o to suggest more efficient data structures and low-level techniques. While the resulting code is more complex and occasionally buggy, it compiles and runs, though without significant performance gains. The study highlights the potential of LLMs as collaborative tools for researchers, capable of uncovering overlooked heuristics and refining implementations, albeit with limitations.
The paper concludes with a call for specialized benchmarks to evaluate LLMs in optimization, the development of autonomous code agents, and the exploration of language translation for optimization algorithms. While the LLM's contributions are impressive, the authors caution against overstating its role, noting that prompt design and iterative feedback remain crucial.
In essence, this work underscores the transformative potential of LLMs in optimization research, not as replacements for human expertise, but as versatile assistants capable of pushing the boundaries of what existing algorithms can achieve.