Re-evaluating LLM-based Heuristic Search: A Case Study on the 3D Packing Problem
This work addresses the challenge of automating heuristic design for complex optimization problems, but it is incremental as it builds on prior LLM applications with new supports and insights into limitations.
The study tackled the problem of using LLMs for automated heuristic design in the 3D Packing Problem, finding that with supports like constraint scaffolding and iterative self-correction, the LLM-generated heuristic performed comparably to human-designed algorithms and rivaled established solvers when integrated into a metaheuristic, though effectiveness decreased with tighter constraints.
The art of heuristic design has traditionally been a human pursuit. While Large Language Models (LLMs) can generate code for search heuristics, their application has largely been confined to adjusting simple functions within human-crafted frameworks, leaving their capacity for broader innovation an open question. To investigate this, we tasked an LLM with building a complete solver for the constrained 3D Packing Problem. Direct code generation quickly proved fragile, prompting us to introduce two supports: constraint scaffolding--prewritten constraint-checking code--and iterative self-correction--additional refinement cycles to repair bugs and produce a viable initial population. Notably, even within a vast search space in a greedy process, the LLM concentrated its efforts almost exclusively on refining the scoring function. This suggests that the emphasis on scoring functions in prior work may reflect not a principled strategy, but rather a natural limitation of LLM capabilities. The resulting heuristic was comparable to a human-designed greedy algorithm, and when its scoring function was integrated into a human-crafted metaheuristic, its performance rivaled established solvers, though its effectiveness waned as constraints tightened. Our findings highlight two major barriers to automated heuristic design with current LLMs: the engineering required to mitigate their fragility in complex reasoning tasks, and the influence of pretrained biases, which can prematurely narrow the search for novel solutions.