Evaluating LLMs for Combinatorial Optimization: One-Phase and Two-Phase Heuristics for 2D Bin-Packing
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Large Language Model-Enhanced Q-learning for Capacitated Vehicle Routing Problem with Time Windows
The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is a classic NP-hard combinatorial optimization problem widely applied in logistics distribution and transportation management. Its complexity stems from…
Combinatorial OptimizationLanguage ModelingLanguage ModellingLarge Language Model+1Graph-Theoretic Analysis of Phase Optimization Complexity in Variational Wave Functions for Heisenberg Antiferromagnets
We study the computational complexity of learning the ground state phase structure of Heisenberg antiferromagnets. Representing Hilbert space as a weighted graph, the variational energy defines a weighted XY model that, …
Improving Existing Optimization Algorithms with LLMs
The integration of Large Language Models (LLMs) into optimization has created a powerful synergy, opening exciting research opportunities. This paper investigates how LLMs can enhance existing optimization algorithms. Us…
Combinatorial OptimizationDistributed Injection-Locking in Analog Ising Machines to Solve Combinatorial Optimizations
The oscillator-based Ising machine (OIM) is a network of coupled CMOS oscillators that solves combinatorial optimization problems. In this paper, the distribution of the injection-locking oscillations throughout the circ…
Combinatorial OptimizationFeeder Load Balancing using Neural Network
The distribution system problems, such as planning, loss minimization, and energy restoration, usually involve the phase balancing or network reconfiguration procedures. The determination of an optimal phase balance is, …
Combinatorial Optimization