Evaluating LLMs for Combinatorial Optimization: One-Phase and Two-Phase Heuristics for 2D Bin-Packing
Syed Mahbubul Huq, Daniel Brito, Daniel Sikar, Chris Child, Tillman Weyde, Rajesh Mojumder · 2025
Read Evaluating LLMs for Combinatorial Optimization: One-Phase and Two-Phase Heuristics for 2D Bin-Packing by Syed Mahbubul Huq, Daniel Brito, Daniel Sikar, Chris Child, Tillman Weyde, Rajesh Mojumder (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-22255.txt.
Introduction
Syed Mahbubul Huq and five co-authors test whether large language models can design good packing strategies. The test problem is two-dimensional bin packing: fit rectangles into as few bins as possible, a classic hard optimization task. Their 2025 paper, presented at a NeurIPS workshop, introduces an evaluation framework that pairs language models with evolutionary algorithms. The model proposes heuristic rules, the evolutionary loop tests and refines them over generations.
The LLM-made heuristics were compared with two traditional ones, Finite First-Fit and Hybrid First-Fit. The models produced more efficient solutions while using fewer computing resources. One leading model reached optimal solutions within two rounds of refinement. Its packings used one fewer bin on average than the traditional methods and filled the bins more completely. The authors offer the framework as a benchmark for judging language models on specialized optimization work.
Catalog record
| CREATOR | Syed Mahbubul Huq, Daniel Brito, Daniel Sikar, Chris Child, Tillman Weyde, Rajesh Mojumder |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-22255
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Evaluating LLMs for Combinatorial Optimization: One-Phase and Two-Phase Heuristics for 2D Bin-Packing Syed Mahbubul Huq, Daniel Brito, Daniel Sikar, Chris Child, Tillman Weyde, Rajesh Mojumder Abstract This paper presents an evaluation framework for assessing Large Language Models’ (LLMs) capabilities in combinatorial optimization, specifically addressing the 2D bin-packing problem. We introduce a systematic methodology that combines LLMs with evolutionary algorithms to generate and refine heuristic solutions iteratively. Through comprehensive experiments comparing LLM generated heuristics against traditional approaches (Finite First-Fit and Hybrid First-Fit), we demonstrate that LLMs can produce more efficient solutions while requiring fewer computational resources. Our evaluation reveals that GPT-4o achieves optimal solutions within two iterations, reducing average bin usage from 16 to 15 bins while improving space utilization from 0.76-0.78 to 0.83. This work contributes to understanding LLM evaluation in specialized domains and establishes benchmarks for assessing LLM performance in combinatorial optimization tasks. \workshoptitle Evaluating the Evolving LLM Lifecycle Benchmarks, Emergent Abilities, and Scaling 1 Introduction The evaluation of Large Language Models (LLMs) extends beyond traditional natural language processing tasks to specialized domains like combinatorial optimization. The 2D bin-packing problem that is placing rectangles into the minimum number of fixed-size bins represents a challenging NP-hard optimization task that serves as an ideal testbed for evaluating LLM capabilities in mathematical reasoning and algorithmic design. Traditional heuristic approaches like Finite First-Fit (FFF) and Hybrid First-Fit (HFF) provide established baselines, but their performance limitations in scalability and solution quality create opportunities for LLM enhanced approaches. This paper evaluates how effectively LLMs can generate, refine, and optimize heuristic algorithms through an iterative evolutionary framework. Our evaluation framework addresses key questions: Can LLMs understand complex algorithmic constraints? How do LLM generated solutions compare to established heuristics? What evaluation metrics best capture LLM performance in optimization contexts? 2 Mathematical Formulation The two-dimensional bin packing problem (2D-BPP), an NP-hard problem, seeks to pack n items of size (w_{i},h_{i}) into the minimum number of bins of size (W,H) , where W>w_{i} and H>h_{i} for all i\in\{1,...,n\} waescher2007new ; martello1990knapsack ; garey1979computers . Let the indicator variable z_{ij}=1 when item i is placed in bin j and 0 otherwise; similarly, u_{j}=1 when bin j is used and 0 otherwise. By the pigeonhole principle, a maximum of n bins is needed Johnsonbaugh_2018 . The optimization problem is formulated as follows: \min\sum_{j=1}^{n}u_{j} Subject to the following constraints for all i,j\in\{1,...,n\} : \sum_{j=1}^{n}z_{ij}=1 ; 0\leq x_{ij}\leq(W-w_{i})z_{ij} ; 0\leq y_{ij}\leq(H-h_{i})z_{ij} ; u_{j}\geq z_{ij} ; together with standard non-overlap constraints, ensuring that no two items in the same bin overlap pisinger2007optimal ; seizinger2022bin . Finally, the total utilization, a common metric to evaluate performance for a given solution is measured as \rho_{\text{total}}=\frac{\sum_{i\in I}w_{i}h_{i}}{\bigl(\sum_{j=1}^{n}u_{j}\bigr)WH} iori2021two ; oliveira2023survey . 3 Evaluation Framework Problem Formulation and Constraints: We evaluate LLMs on the 2D bin-packing problem with strict constraints: bin dimensions of 200×100 units, item constraints requiring no overlap and complete containment within bins, the objective to minimize number of bins used, and an evaluation dataset of 50 randomly generated squares (10-50 units) across 20 iterations. LLM Based Evolutionary Process: Figure 1: Iterative Evolutionary Framework for Heuristic Generation Our evaluation methodology employs a six-step iterative process. First, structured prompting designs prompts that clearly specify problem constraints, input/output formats, and success criteria. Second, code generation and correctness validation systematically validates LLM generated candidate solutions against constraint satisfaction. Third, performance scoring evaluates solutions using multiple metrics: number of bins used (primary), space utilization efficiency (secondary), and execution time (tertiary). Fourth, island-based selection clusters high-performing solutions into "islands" to promote diversity. Fifth, iterative refinement uses the top performing solutions to inform subsequent prompts, creating an evolutionary feedback loop. To implement this framework, each generated script is rigorously validated for syntactic and logical correctness; only solutions that successfully pack all items according to the rules are advanced to the performance evaluation stage. The high performing solutions are clustered into distinct "islands" to preserve strategic diversity and prevent premature convergence on a single type of solution. In the refinement stage, the top three performing solutions one from each of the top three islands are used as "best-shot" examples in the prompt for the next generation cycle. This evolutionary feedback loop instructs the LLM to learn from the most successful strategies, progressively enhancing the quality of the generated heuristics over six full iterations. A detailed breakdown of each component, including full prompt design and baseline implementations, is available in Appendix B. Baseline Comparisons: We establish baselines using two established heuristics. Finite First-Fit (FFF) places items in the first available position using First-Fit Decreasing Height (FFDH) with time complexity O(n^{2}) . Hybrid First-Fit (HFF) employs a two-phase approach combining strip packing (FFDH) with bin packing (FFD) with time complexity O(n\log n) . 4 Experimental Setup: We conducted experiments using GPT-4o with BPE tokenization on an Intel Core i5-8250U processor with 8GB RAM. The dataset consisted of 20 iterations with 50 randomly generated squares per iteration, and the evaluation protocol used the same dataset for all methods to ensure fair comparison. The LLM evaluation process terminated after demonstrating convergence within 2-6 iterations, indicating rapid solution optimization capability. 5 Results and Discussion Comparative Performance Method Avg Bins Execution Time (s) Space Utilization FFF 16.05 0.002446 0.76 HFF 16.00 0.024438 0.78 LLM 15.00 0.0103 0.83 Table 1: Comparative performance across evaluation metrics The LLM-generated heuristic demonstrates superior performance across all evaluation metrics, achieving a 6.25% reduction in bin usage compared to baselines, a 6.4% improvement in space utilization over HFF, and competitive execution time despite code generation overhead. Convergence Analysis The LLM achieved optimal solutions within two iterations, suggesting efficient learning from constraint feedback. This rapid convergence indicates strong pattern recognition capabilities and effective constraint satisfaction learning. Space Utilization Patterns LLM generated solutions show more consistent space utilization across bins (83% average) compared to traditional heuristics, which exhibit declining utilization in later bins (HFF: 86.83% \rightarrow 63.54%, FFF: 87.50% \rightarrow 68.00%). LLM Capabilities Assessment Our evaluation reveals several key capabilities. LLMs successfully internalize complex geometric and logical constraints, demonstrating sophisticated constraint understanding. Generated solutions exhibit optimization intuition through sophisticated packing strategies not explicitly programmed. The results show consistent iterative improvement across evolutionary cycles, indicating effective learning mechanisms. Limitations and Evaluation Challenges Computational constraints limit iteration cycles due to API costs, constraining comprehensive evaluation. LLM non-determinism complicates reproducibility, requiring multiple evaluation runs for statistical validity. The evaluation was limited to moderate problem sizes, and larger instances may reveal different performance characteristics that could affect generalization. Evaluation Metric Considerations Traditional optimization metrics (bin count, space utilization) prove effective for LLM evaluation, but additional metrics considering code quality, algorithmic sophistication, and constraint satisfaction robustness could provide deeper insights into LLM problem-solving capabilities. Implications for LLM Evaluation This work contributes to LLM evaluation methodology through domain-specific benchmarking that demonstrates the value of specialized evaluation frameworks for assessing LLM capabilities beyond language tasks. The iterative evaluation protocols show how evolutionary feedback can systematically evaluate LLM learning and adaptation capabilities. Multi-metric assessment establishes that comprehensive LLM evaluation requires performance, efficiency, and solution quality metrics. Finally, baseline establishment provides benchmarks for future LLM evaluation in combinatorial optimization contexts. 6 Related Work The 2D bin packing problem is a fundamental NP-hard combinatorial optimization challenge where rectangular items must be packed into the minimum number of