Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Authors: Huigen Ye
Hua Xu
An Yan
Yaoyang Cheng
Venue: ICML 2025 spotlightposter (2025)
Keywords: Mixed Integer Linear Programming
Large Neighborhood Search
Large Language Model
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: This paper introduces a dual-layer self-evolutionary LLM agent to automate neighborhood selection, discovering effective strategies with scant small-scale training data that generalize well to large-scale MILPs.

Abstract: Large Neighborhood Search (LNS) is a widely used method for solving large-scale Mixed Integer Linear Programming (MILP) problems. The effectiveness of LNS crucially depends on the choice of the search neighborhood. However, existing strategies either rely on expert knowledge or computationally expensive Machine Learning (ML) approaches, both of which struggle to scale effectively for large problems. To address this, we propose LLM-LNS, a novel Large Language Model (LLM)-driven LNS framework for large-scale MILP problems. Our approach introduces a dual-layer self-evolutionary LLM agent to automate neighborhood selection, discovering effective strategies with scant small-scale training data that generalize well to large-scale MILPs. The inner layer evolves heuristic strategies to ensure convergence, while the outer layer evolves evolutionary prompt strategies to maintain diversity. Experimental results demonstrate that the proposed dual-layer agent outperforms state-of-the-art agents such as FunSearch and EOH. Furthermore, the full LLM-LNS framework surpasses manually designed LNS algorithms like ACP, ML-based LNS methods like CL-LNS, and large-scale solvers such as Gurobi and SCIP. It also achieves superior performance compared to advanced ML-based MILP optimization frameworks like GNN&GBDT and Light-MILPopt, further validating the effectiveness of our approach.

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Huigen Ye 12
Hua Xu 12
An Yan 12 Yaoyang Cheng" 1
Abstract
plex optimization problems across various domains, includ- ing transportation management (Klanšek, 2015), bin pack- ing (Fleszar, 2022), and production planning (Adrio et al., 2023). MILPs are challenging to solve efficiently due to their NP-hard nature (Kim al., 2021) and the exponen- tial growth of the search space as problem size increases (Vázquez et al., 2018). To address these challenges, re- searchers have developed two primary approaches (Zhang et al., 2023): exact algorithms,, such as branch-and -arehh--nn--bund and heuristic- -ased approximation methods.
Large Neighborhood Search (LNS) is a widely used method for solving large-scale Mixed Inte- ger Linear Programming (MILP) problems. The effectiveness of LNS crucially depends the choice of the search neighborhood. However, ex- isting strategies either rely on expert knowledge or computationally expensive Machine Learning (ML) approaches, both of which struggle to scale effectively for large problems. To address this, we propose LLM-LNS, a novel Large Language Model (LLM)-driven LNS framework for large- scale MILP problems. Our approach introduces dual-layer self-evolutional LLM agent to au- tomate neighborhood selection, discovering ef- fective strategies with scant small-scale training data that generalize well to large-scale MILPs. The inner layer evolves heuristic strategies to en- sure convergence, while the outer layer evolves evolutionary prompt strategies to maintain di- versity. Experimental results demonstrate that the proposed dual-layer agent outperforms state- of-the-art agents such as FunSearch and EOH. Furthermore, the full LLM-LNS framework sur- passes manually designed LNS algorithms like ACP, ML-based LNS methods like CL-LNS, and large-scale solvers such Gurobi and SCIP. It also achieves superior performance compared to advanced ML-based MILP optimization frame- works like GNN& and Light-MILPopt fur- ther validating the effectiveness of our approach.
While exact algorithms like branch-and-boumt (Boyd Mattingley, 2007: Morrison et al., 2016) are effective for small to medium-sized problems, they struggle with the computational demands of larger instances. This has led to the rise of heuristic methods, particularly Large Neighbor- hood Search (LNS) (Ahuja et al., 2002; Mara et al., 2022), which iteratively improves solutions by destroying and re- pairing parts of the current solution, allowing for exploration of large neighborhoods without full re-optimization (Song et al., 2020; Ye al., 2023a). However, LNS performance depends heavily on neighborhood selection, which is often hand-crafted and requires significant domain expertise. De- signing these operators can be labor-intensive and prone to cold-start issues, where limited prior knowledge is available to guide the search (Zhang et al., 2023).
In recent years, machine learning (ML) techniques, includ- ing reinforcement learning (Wu al., 2021; Song al., 2020) and imitation learning (Sonnerat et al., 2021; Nair et al., 2020), have been applied to automate the design of neighborhood selection strategies. These methods aim to learn heuristic strategies from training datasets, reducing reliance on expert knowledge and allowing the algorithms to adapt to new, homogeneous instances. However, ML-based LNSS approaches come with their own challenges. For re- inforcement learning, slow convergence is common issue (Beggs, 2005), particularly in large-scale MILP problems, due to the vast search space and the need for extensive exploration before identifying effective strategies. On the other hand, imitation learning requires large amounts of high-quality, labeled data, which can be computationally expensive generate using expert algorithms (Huang et al., 2023b). As result, both hand-crafted and ML-based meth- ods struggle to efficiently solve large-scale MILP problems.
1. Introduction
Mixed Integer Linear Programming (MILP) is versatile and widely used mathematical framework for solving com-
'Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China *Beijing National Research Center for Information Science and Technology, Beijing 100084, China. Correspondence to: Hua Xu <xuhua@ www.ee@iiinnnguuuucoom
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
The rise of Large Language Models (LLMs) offers promis- ing solution these challenges. Unlike traditional hand- crafted methods, LLMs come pretrained with vast general knowledge, allowing them to reason about complex tasks and learn problem structures with minimal training data, thus avoiding cold-start issues. Additionally, LLMs can adapt to new problems through interactive reasoning, reduc- ing the need for extensive exploration and addressing the slow convergence of reinforcement learning. Furthermore, LLMs can dynamically generate heuristic strategies with- out relying on large labeled datasets, which significantly reduces the computational overhead typically associated with imitation learning (Yang et al., 2024; Lange et al., 2024). While LLMs have shown potential in generating strategies for combinatorial optimization problems( Ye et al., 2024; Elhenawy et al., 2024), they often lack the problem- specific refinement needed to produce efficient heuristics without additional guidance (Plaat et al., 2024). Approaches like FunSearch (Romera-Paredes et al., 2024) and Evolu- tion of Heuristic (EOH) (Liu et al., 2024) combine LLMs with evolutionary algorithms (Simon, 2013), but rely on fixed strategies, limiting solution diversity and leading to poor convergence due to insufficient directionality. This underscores the need for more adaptive framework to fully harness LLMs for large-scale MILP problems.
apply the proposed dual--ayer LLM agent to the neigh- borhood selection strategy generation in LNS. By uti- lizing only small amount of training data from small- scale problems, the LLM agent can discover new neigh- borhood selection strategies that generalize well to large-scale MILP problems.
Comprehensive Experimental Validation: We val- idate the effectiveness of our proposed LLM-LNS at two levels. First, we test its agent's performance on heuristic generation tasks of combinatorial opti- mization problems, demonstrating its superiority over state-of-the-art methods such as FunSearch and EOH. Second, we evaluate its performance on large-scale MILP problems, where it outperforms traditional LNS methods, ML-based LNS methods, and leading solvers. Furthermore, our proposed LLM-LNS surpasses mod- emn ML-based optimization frameworks for large-scale MILP, confirming the effectiveness of our LLM-LNS solving large-scale optimization problems.
2. Related Work
2.1. Mixed Integer Linear Programming
Mixed Integer Linear Programming (MILP) problems rep- resent a class of combinatorial optimization problems char- acterized by a linear objective function subject to a set of linear constraints, where some or all decision variables are restricted to integer values. An MILP can be defined as follows:
In this paper, we propose LLM-LNS, a novel Large Lan- guage Model-driven Large Neighborhood Search framework designed specifically for solving large-scale MILP problems, which can discover effective neighborhood selection strate- gies for LNS with scant small-scale training data that gener- alize well to large-scale MILPs. The code of LLM-LNS is open-sourced at https://github.e https//giitub.com/uuirLLLLLL key innovations are as follows:
min of x, s.t. S. x
S. E.EEE. iEI, (I)
Our
where x represents the decision variables, with n E Z denot- ing the dimensionality of the integer variables and I, u, c R" corresponding the lower bounds, upper bounds, and coefficients of the decision variables, respectively. The trix A E Rmxx and the vector b E RT define the linear constraints of the problem. The set I S 21. n} de- notes the indices of variables that are constrained to integer values. A feasible solution to the MILP problem satisfies all constraints, and the optimal solution minimizes the objective function value. (Artigues et al., 2015; Pisaruk, 2019)
Dual-layer Self-evolutionary LLM Agent: We pro- pose novel LLM agent with a dual-layer self- evolutionary mechanism for automatically generat- ing heuristic strategies. The inner layer evolves both thoughts and code representations of heuristic strate- gies, ensuring convergence, while the outer layer evolves evolutionary prompt strategies to maintain diversity, preventing the search process from getting trapped in local optima.
Differential Memory for Directional Evolution: We introduce differential evolution in the agent to guide both crossover and variation. By feeding the fitness val- ues of parent strategies back into the LLM, we leverage its memory to learn how to evolve from less effective to more effective strategies. This feedback mechanism enables the LLM to act as an optimizer, identifying promising directions and leading to more efficient im- provements.
2.2. Large Neighborhood Search
Large Neighborhood Search (LNS) is widely used heuris- tic for solving MILP problems. It iteratively improves so- lutions by exploring predefined neighborhoods around current solution. However, the effectiveness of LNS heav- ily relies on the neighborhood selection strategy, as poor choices can lead to stagnation in local optima.
Several approaches have been proposed to address this chal- lenge. One common method is random-LNSs (Song et al.,
Application to Neighborhood Selection in LNS: We
2

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
2020), which randomly partitions integer variables into dis- joint subsets and optimizes one subset in each iteration while fixing the others. However, random-LNS uses fixed neighborhood size and overlooks correlations between de- cision variables, limiting its performance. To overcome these drawbacks, the Adaptive Constraint Partitioning (ACP) framework (Ye et al., 2023a) introduces a dynamic strategy that adjusts the neighborhood size, optimizing all decision variables associated with randomly selected constraints in each iteration. This ensures that highly correlated variables are optimized together, improving performance. Similar strategies have been explored in other works (Huang et al., 2023a; Han et al., 2023), but they still rely on manually designed heuristics, requiring expert knowledge and lacking adaptability to new problem instances.
Table I. Comparison of Features Between Difference Methods
SunSearch
FOH
LLM-LNS
Heuristic Evolution
Thought Evolution
Prompt Evolution
XX
Directional Evolution
X
X
(EOH) (Liu et al., 2024), builds on the strengths of LLMs and evolutionary computation while addressing some of FunSearch's 's limitations. EOH introduces novel evolu- tionary paradigm where heuristics, represented as natural language "thoughts," are translated into executable code by LLMs. These thoughts and their corresponding code are evolved within an EA framework, enabling the efficient generation of hegh-performance heuristics. As shown in Table 1, while FunSearch and EOH have advanced the in- tegration of LLMS with evolutionary algorithms,, they still have limitations. All methods focus on Heuristic Evolution for generating strategies, but FunSearch evolves only at the code level and lacks Thought Evolution. Meanwhile, FOH incorporates Thought Evolution but uses fixed evolutionary strategies, lacking Prompt Evolution to enhance solution diversity. Additionally, both methods lack Directional Evo- lution, where crossover operations are guided by differential memory to improve efficiency and adaptability. These lim- itations reduce their ability to guide the search effectively, often leading to premature convergence. These challenges highlight the need for more adaptive frameworks to fully harness LLMs in large-scale optimization tasks.
To address this limitation, machine learning methods have been applied to automate neighborhood selection. Rein- forcement learning (RL) approaches define reward functions based on solution improvements, allowing models to learn promising neighborhoods through interaction with the prob- lem (Wu et al., 2021; Song et al., 2020; Nair et al., 2020). Imitation learning, on the other hand, uses large amount of large-scale sampling (Huang al., 2023b; Zhou al., 2023) or expert algorithms (Sonnerat et al., 2021) to guide the se- lection process. While these techniques reduce reliance on handcrafted strategies, RL struggles with convergence in large-scale MILP problems, and imitation learning requires extensive sampling, making it computationally expensive. This highlights the need for more efficient, automatically designed neighborhood selection strategies.
3. Method
2.3. Large Language Model for Heuristic Design
In this section, we introduce LLMM-LN,, a Large Language Model-driven Large Neighborhood Search framework de- signed to solve large-scale MILP problems. As shown in Figure the framework composed of two main compo- nents: Dual-layer Self-evolutionary LLM Agent and Adaptive Large Neighborhood Search process. For the framework's detailed pseudocode, see Appendix B.1.
The rise of Large Language Models (LLMs) has opened new possibilities for generating heuristic strategies solve combinatorial optimization problems (Yang et al., 2024; Lange et al., 2024). LLMs excel at generating high-level ideas and reasoning over complex tasks, but they often lack problem-specific knowledge, limiting their ability to cre- ate effective heuristics without additional guidance (Plaat et al., 2024). To overcome these limitations, recent works have integrated LLMs with evolutionary algorithms (EA) to iteratively refine heuristics.
3.1. Dual-layer Self-evolutionary LLM Agent
The Dual-layer Self-evolutionary LLM Agent is the core component of our framework, responsible for generating and evolving heuristic and prompt strategies. The Dual- layer Self-evolutionary Structure consists of an Inner Layer that evolves heuristic strategies to accelerate conver- gence, and an Outer Layer that evolves evolutionary prompt strategies to enhance diversity in heuristic generation. An- other key innovation is the incorporation of Differential Memory for Directional Evolution, which accelerates con- vergence by learning the direction of improvement from less effective strategy to better ones. Together, these innova- tions ensure a balance between exploration and exploitation, significantly improving the efficiency and preventing stag-
FunSearch Kkomera-Paredee et al., 2024) is notable at- tempt that combines LLMs with evolutionary frameworks. FunSearch uses LLMs to generate functions, which are then evolved through an evolutionary search process. This approach has demonstrated success in outperforming hand- crafted algorithms on specific optimization problems. How- ever, FunSearch is computationally expensive, often requir- ing millions of LLM queries to identify effective heuristic functions, which limits its practicality in many real-world ap- plications. A more recent approach, Evolution of Heuristic
3

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Dual-layer Self-evolution LLM Agent
Outer Layer: Evolutionary Pronptt Stretagy Exelution
Fopdistor..o Crcttiive Strnnys
Fopuadtrr Eatio Se soagy
Evolution of Panmpr
FRemA Volue
Stowey Shantyy
Inner Layer: Hauriaiic Strategy Exalution
Hearss pibeetag
For dinten Hourhee
Defestonny Foonet
Eve Beuting
Pario Seeccio
Hoai
GUROBI
Bodk aud
0C 00000 Alletee
(12...9)
SOrts)
Selectio
MILP Dataset
Adaptive Large Neighborhood Search
Figure 1. An overview of the proposed LLM-LNS framework. The framework consists of a dual-layer self-evolutionary LLM agent for solving large-scale MILP problems. In the outer layer, evolutionary prompt strategies generated and passed the inner layer, where heuristic strategies are evolved. A differential memory mechanism uses fitness feedback to refine these strategies across iterations. The refined strategies are fed into the Adaptive Large Neighhorhood Search process, which iteratively improves solutions.
nation local optima.
Evaluation and Final Selection: After new heuristic strategies are generated, they are evaluated by inte- grating them into the Adaptive Large Neighborhood Search process, where each heuristic is applied to solve small-scale instances from the training dataset. The performance of each strategy is measured by its objec- tive function value, which serves as its fitness score. After multiple iterations of evolution and evaluation, the best- rest-performing heuristic strategies are identified based on their fitness.
3.1.1. DUAL-LAYER SELF-TVOLUTIONARY STRUCTURE
The Dual-layer Self-evolutionary Structure is the com- ponent of the LLM-LNS framework. It is designed to evolve both evolutionary prompt strategies and heuristic strategies in a synergistic manner, leveraging LLMs for automated heuristic design and refinement. This dual-layered structure mimics the heuristic development process of human experts, ensuring balance between exploration and exploitation throughout the search process.
Outer Layer: Evolutionary Prompt Strategy Evolution. The Outer Layer focuses on evolving evolutionary prompt strategies, which guide the LLM in generating new heuristic strategies. The emphasis in this layer is on exploration to maintain diversity and prevent premature convergence in the heuristic strategy population. The key stages of Outer Layer, as illustrated in Figure 1, include:
Inner Layer: Heuristic Strategy Evolution. The Inner Layer focuses on evolving heuristic strategies, which consist of both natural thought and corresponding code implemen- tations, with an emphasis on convergence. Key aspects of Inner Layer, as illustrated in Figure 1, include:
Initialization of Heuristic Strategies: The initial set of heuristics is generated by feeding the structural infor- mation from small-scale training problems, along with initialization prompt strategy, into the LLM. This produces the first generation of heuristic strategies.
Initialization of Prompt Strategies: The initial set of evolutionary prompt strategies is handcrafted and de- signed to perform basic crossover and variation op- erations, instructing the LLM on how to combine or modify existing heuristic strategies in the inner layer.
Evolution of Heuristic Strategies: In each generation, new heuristic strategies are evolved by selecting parent strategies from the current heuristic population. As detailed in Appendix B.3, strategies with higher fitness values are more likely to be selected as parents. These parents are then combined with evolutionary strate- gies, selected from the Outer Layer's 's population of prompt strategies (c.g., crossover or variation prompts), to guide the I.L.M in generating offspring strategies.
Evolution of Prompt Strategies: As the evolution pro- gresses, more complex prompt strategies are intro- duced to address stagnation in the heuristic population. Specifically, if the top-/ individuals in the heuristic population remain unchanged for t consecutive genera- tions, we infer that the evolution may have converged to a local optimum. This triggers the evolution of new prompt strategies. This systematic evolution of prompt

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Pronge Strakgg
Evolution Evolutionnyy
Cisedt Beiign axconed complctty odderize
Creak: Dondap arand hamblic by sysiloiiity exchokicciio sakes li odgattic lancien. Creei: Cruma heristi using uniqu de denere sad wtymin lamning for exstmbouice.
Fitness Value(Performaa
Dosett Seggor new hwretts here uthinigg
Varaaaar: Recordges con prncepai tor now sereets wtytte larning
Satuaed: Aspalsonc lteckin parendas coppaiac smmupss
uang Looencsuand untaagis opiiniaaiiss
0 0.9942
0.9942
Kreterboa Heurriie Strangy
0.9934
Aakel povce sndgrniiell yenalins
coceqitus > itee time Aauutt Eustee marrg
Evaletion llrarietic Strategy
Swares inddlignae dratlane susnllng
0,9918
0,9916
Actradjate 30unter
0.9911
0.9911
(glicos car
rondors edperreent
Mas sgensentt of Evalatiaturs Pronet Strategy
Evcution of Heuridic Strelegs Added randersoon for exploratee
-everroed thange wwweeeeeddddeeeeeeeeoo www.eeedddeeeeeeeeeeeooo
soresfbee dtmn Lovrirt
adquhe leriing
Evalutian Hlreriitic Strategy
Ieaializatian of Heariste Strotegy Capecity rala with poralty
1yteid apdadzzttee nith saseii slpeitae abu sard porrsijauu i iten Sustee
hitorypeaaly
currejhue Icee)
Inkiilization of Eveletansry Promat Strslgg
Evalation Elearietic Strategy
Crall: Cruns zo mompttttnnn thes.
Randeenteed aljinitann for direrity
0,9595
diurddnninggtddd Vatiianl: Mocil agentler.
gran
zonnsrabbu nen] auseeee
Variiaed: Crong the of Uhe givnn dgariiis
10 Number of generations
Figure Evolution of Dual-layer Self-evolutionary LLM Agent for online bin packing. We outline the key thoughts of the best heuristics produced in some generations during the evolution of heuristic strategies. Additionally, we highlight the evolution of evolutionary prompt strategies, which dynamically adapt the prompt strategies to guide the LLM in generating more effective and diverse heuristics.
strategies helps ensure that the heuristic population does not get trapped in local optima.
in heuristic performance. This dual-layered approach en- sures efficient exploration and exploitation, enabling the LLMM-NS framework to tackle large-scale problems with minimal human intervention. For more detailed example of the evolution process, please refer to Appendix B.2.
Evaluation and Management of Prompt Strategies: To ensure the efficiency and effectiveness of the prompt strategy population, each prompt strategy is evaluated based on the performance of the heuristic strategies it generates. Specifically, for each prompt strategy, the top-k performing heuristic strategies it produces are tracked, and the average fitness score of these heuristics is used as the fitness score for the prompt strategy itself. This fitness-base evaluation allows us to manage the prompt population and control its size, As the number of prompt strategies increases over generations, under- performing strategies pruned to prevent excessive growth and focus on the most effective strategies. This pruning process ensures that only the most effective prompt strategies continue to evolve, maintaining both diversity and efficiency in the evolutionary process. For parameter details, see Appendix C.
3.1.2. DIFERENTIAL MEMORY FOR DIRECTIONAL EVOLUTION
In our Dual-layer Self-evolutionary LLM Agent, both heuris- tic strategies and evolutionary prompt strategies evolve through a process that incorporates Differential Memory for Directional Evolution. This mechanism allows the LLM to leverage the fitness history of strategies, learning from the differences between higher- and pevre-perforing strategies to guide the generation of improved candidates. Differential memory enables the LLM to act as both a generator and an optimizer, dynamically refining strategies over successive generations.
At each generation t, the LLM is provided with a set of m saantegy-thouhhttteee tuples:
The synergy between the Inner Layer and Outer Layer drives rapid evolution of effective heuristics and novel evo- lutionary prompt strategies, as shown in Figure 2. Early generations focus on basic principles, but with the intro- duction of advanced prompt strategies, such complexity reduction and adaptive learning, the system quickly adapts to overcome local optima. Notably, the sharp performance improvements between generations 5 to 15 demonstrate the framework's 's ability to autonomously discover and re- fine creative strategies, leading to continuous enhancements
s( = ("H,") (H, >m
(2)
where H." represents the i-th parent heuristic strategy se- lected for this generation, thought, is its corresponding nat- ural language description, and (HH(()) ) is its fitness score. The size of S(t) is m, which is a predefined parameter rep- resenting the number of parent strategies used in a single evolutionary operation. These tuples encapsulate both the structural and performance information of the selected par-
5

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
ent strategies, providing the necessary context for generating offspring strategies.
The key innovation of ALNS lies in the use of the LLM agent to generalize variable selection strategies. Trained on small-scale MILP problems, the LLM agent learns to rank variables based on their impact on the objective function, en- abling the generalization of these strategies to larger, more complex problems. This transfer of knowledge ensures that neighborhood selection is both adaptive and intelligent, dynamically balancing exploration and exploitation. By focusing computational resources on the most promising re- gions of the solution space, ALNS efficiently navigates the vast search space of large-scale MII.Ps. For a detailed de- scription of the process and the corresponding pseudocode, please refer to Appendix B.4.
To generate the next generation of strategies H(++1, the LLM employs a meta meta--rompp Pmota- which combines two key components: a directive Pleam that instructs the LLM to learn from the differences between higher- and lower- performing strategies, emphasizing traits that contribute to higher fitness; and an evolutionary prompt strategy Pevo. provided by the Outer Layer, which specifies the goals and rules for the evolutionary operation, such as crossover, mu- tation, or hybrid operations. The generation process can be formalized as:
H 1++ = (M(PmeaalS(())
(3)
4. Experiment
where MM is the LLM model, Pmota (Picam. Pevo) is the meta- petatprompt, and ((() represents the strategy-thought- fitness tuples from the current generation. By integrating these components, the LLM generates new strategies ((+1) that are informed by past evolutionary performance and aligned with the objectives defined by the Outer Layer. This iterative beedback-refinement loop ensures that the LLM dynamically balances exploration and exploitation. Differ- ential memory accumulates across generations, enabling the LLM to focus on areas of the search space that demon- strate promise while avoiding stagnation in local optima. The result is an increasingly proficient evolution process, accelerating convergence toward optimal solutions while maintaining population diversity.
To validate the effectiveness of the proposed LLM-LNS framework, we conduct two sets of experiments. First, we evaluate our proposed Dual-layer Self-evolutionary LLM Agent on heuristic generation tasks for combinatorial opti- mization problems, comparing it against methods like Fun- Search (Romera-Paredes et al., 2024) and EOH (Liu et al., 2024). Second, we assess the full LLM-LNS framework on large-scale MILP problems, where it is compared against traditional LNS methods (e.g., ACP (Ye et al., 2023a)), ML-based LNS approaches (e.g.. CL-LNS (Huang et al., 2023b)), the SOTA solvers like Gurobi (Gurobi Optimiza- tion, LLC, 2023) and SCIP (Maher et al., 2016), and mod- ern ML optimization frameworks such as GNN&GBDT (Ye et al., 2023c) and Light-MILPopt (Ye et al.. 2023b). More experimental results and details are provided in the Appendices C to F.
3.2. Adaptive Large Neighborhood Search
Adaptive Large Neighborhood Search (ALNS) dynamically adjusts neighborhood size and leverages the Dual-layer Self- evolutionary I.LM Agent for variable scoring and selection. At each iteration t, the LLM agent computes scores s! for decision variables xi based on their potential to improve the objective value. The top-k variables are selected form the neighborhood Art);
4.1. Heuristic Generation for Combinatorial Optimization Problems
In this section, evaluate the performance of the Dual- layer Self-evolutionary LLM Agent in generating heuristic strategies for well well- combinatorial optimization prob- lems. We focus on two widely studied problems: Online Bin Packing (Seiden, 2002) and the Traveling Salesman Prob- lem (TSP) (Hoffman et al., 2013). Our method is compared against several hand-crafted heuristics, state-of-the-arr MI. based methods, and other automatically designed heuristics.
AT = {z; rank(s(") S k}.
(4)
where (1 is the neighborhood at iteration f, and l is the current neighborhood size. A subproblem is then solved within A/()), and the solution x is updated if an improvement is found.
4.1.1. ONLINE BIN PACKING
The neighborhood size is adaptively adjusted based on search progress. If the improvement in the objective value falls below a threshold e for p consecutive iterations, l is expanded to explore a broader search space k <- min(kmax
The objective of the Online Bin Packing problem is to al- locate a collection of items into the fewest possible bins of fixed capacity. We follow the experimental setup from Komera-Paredes et al. (2024), using Weibull distribution instances with varying numbers of items (1k to 10k) and bin capacities (100 and 500). The performance of each method is measured by the fraction of excess bins used, where lower values indicate better performance. We compare our method
k + [u% - nz]), where 4% is the adjustment rate and n is the total number of decision variables. Conversely, if the time spent solving subproblems within the neighbor- hood exceeds a predefined limit, & is reduced to focus on a smaller subset of variables <- max max(kmin k- - fu% m) ml]).
6

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
Table Online Bin Packing Heuristic Comparison. This table compares the performance of various bin packing heuristics based on
the fraction of excess bins (lower values indicate better performance) across different Weibull distribution instances.
Ik C100
CT00
lok C100
Ik C500
5k C500
10k C500
Avg
First Fut
5.32%
4.40%
4,44%
4.97%
4.27%
4,28%
4.61%
Best Fit
4.87%
4.08%
4.09%
4.50%
3.91%
3.95%
4.23%
FunSearch
3.78%
0.80%
0.33%
6.75%
1.47%
0.74%
2.31%
EOH
4.48%
0.88%
0.83%
4.32%
1.06%
0.97%
2.09%
Ours
3.58%
0.85%
0.41%
3.67%
0.82%
0.42%
1.63%
Table 3. Traveling Salesman Problems Heuristic Performance Evaluation. This table provides comparison of the relative distance the best-known solutions for different routing heuristics (lower values indicate hetter performance) on a subset of TSPLib benchmark instances.
rd100
pr124
bier127
kroA150
u159
kroB200
Avg
NT
19.91%
15.50%
23.21%
18.17%
23.59%
24.10%
20.75%
FI
9.38%
4.43%
8.04%
8.54%
11.15%
7.54%
8.18%
Or: Tools
0.01%
0.55%
0.66%
0.025
1.25%
2.57%
0.93%
AM
3.41%
3.68%
5.91%
3.78%
7.55%
7.11%
5.24%
POMO
0.01%
0.50%
13.72%
0.70%
0.95%
1.58%
2,93%
LEHD
0.01%
1.11%
4.76%
1.40%
1.13%
0.64%
1.51%
BOH
0.01%
0.00 %
0.42%
0.29%
-0.01%
0.26%
0.16%
Ours
0.01%
0.00%
0.01%
0.00%
-0.01%
0.44%
0.08%
against several baselines, including hand-crafted heuristics First Fit (Tang et al., 2016) and Best Fit (Shor, 1991), which are widely used in practice, as well as automatically gen- erated heuristics FunSearch Coomera-Paredes et al., 2024) and EOH (Liu et al., 2024), which represent state-of-the-art approaches.
et al., 2023), all of which are ML-based methods.
As shown in Table 3, our method achieves the best aver- age performance with a 0.08% gap to the best-known solu- tions, outperforming both hand-crafted heuristics and neural network-based methods. Notably, on the bier instance, our method achieves relative distance of just 0.01% to the best-known solution, significantly outperforming EOH (0, (0.42%) and other baselines, including LEHD (4.76%) and AM (5.91 %). This substantial improvement highlights the effectiivnness of our approach in solving challenging in- stances of the TSP.
As shown in Table 2, our method consistently achieves the best performance across different problem sizes and capacities, with an average excess bin fraction of 1.63%, outperforming both hand-crafted heuristics and automati- cally generated methods. In particular, our approach excels on the 10k items, capacity 500 instance, achieving a fraction of excess bins of 0.42%, outperforming FunSearch (0.74%) and EOH (0.97%), highlighting the strong scalability and generalization ability of our method, making it particularly effective in handling large-scale, high-capacity scenarios.
It is important note that both the Online Bin Packing and TSP problems use the same GPT-4o-mini LLM, with identical settings: 20 iterations and population size of 20 for Online Bin Packing, and 10 for the TSP problem. De- spite these identical settings, our method consistently out- performs BOH in both problems, showcasing the superior efficiency of the dual-layer self-evolutionary mechanism in exploring the solution space. This mechanism allows our method to dynamically adapt and refine solutions, resulting in better overall performance with the same computational resources. These results underscore the robustness and scal- ability of our approach, offering a promising direction for solving large-scale combinatorial optimization problems using L.MMs.
4.1.2. TRAVELING SALESMAN PROBLEM
The Traveling Salesman Problem (TSP) a classic com- binatorial optimization problem where the goal is to find the shortest route that visits all given locations exactly once. We evaluate our method on a subset of TSPLib benchmark instances (Reinelt, 1991), with performance measured by the relative distance to the best-known solutions (lower val- ues indicate better performance). We compare our method against two types of baselines: hand-crafted heuristics and Al- Al-generated heuristies. The hand-crafted heuristics in- clude Nearest Insertion (NI) and Farthest Insertion (FI) (Rosenkrantz et al., 1977), two widely used constructive heuristics. We also include Google OR-Tools (Perron &
4.2. Performance of L.M--LSS on Large-Scale MILP Problems
To validate the effectiveness of the proposed LLM-LNS framework for large-scale MILP problems, we evaluate its performance on four widely-used benchmark datasets: Set Covering (SC) (Caprara et al., 2000), Minimum Vertex Cover (MVC) (Dinur& & Safra, 2005), Maximum Indepen-
Furnon), a popular solver, using its default settings and the recommended local search option. Beyond EOH (Liu et al., 2024), we compare against the Attention Model (AM) (Kool et al., 2018), POMO (Kwon et al., 2020), and LEHD (Luo
7

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
Table Comparison of objective values on large-scale MILP instances across different methods. For each instance, the best- performing objective value is highlighted in bold. The symbol indicates that the method was unable to generate samples for any instance within 30,000 seconds, while * indicates that the GNN&GBDT framework could not solve the MILP problem.
(Mi(M
SCa(Min)
(MCn(
MVCn(Minn)
(Max)
(MXx(Max)
(MaX)
(TKSg(Max)
Random-LNS
T6140.6
169417.5
27031.4
276467.5
22892.9
223748.6
36011.0
351964,2
ACP
17672.1
182359.4
26877.2
274013.3
23058.0
226498.2
34190.8
332235.6
CL-LNS
31285.0
15000.0
Gurobi
17934,3
320240.4
28151.3
283555.8
21789.0
2165913
32960.0
329642,4
SCIP
25191.2
385708.4
31275.4
491042.9
18649.9
9104.3
29974,7
168289.9
GNN&
16728.8
252797.2
27107.9
2717772
22795.7
227000.4
Light-MII,POP
16108.1
160015.5
26950.7
269571.5
22966.5
230432.9
36125.5
362265.1
LLM LNS(Ours)
15602.7
158878.9
26725.3
268033.7
23169.3
231636.9
36479.8
363749.5
dent Set (MIS) (Tarjan & Trojanowski, 1977), and Mixed Integer Knapsack Set (MIKS) (Atamtürk, 2003). Initially, LLM-LNS is trained on smalle-scale problems with tens of thousands of variables and constraints and then tested on large-scale instances with millions of variables and con- straints to assess its scalability and generalization.
complete sampling within an acceptable time for large-scale instances, and even when results are obtained, the solution quality is significantly lower. This highlights the challenges faced by existing LNS-based methods when dealing with large and complex MILP problems, while underscoring the robustness and adaptability of LLM-LNS.
We compare LLM-LNS with several state-of-the-art base- lines, including heuristic LNS methods like Random-LNS (Song et al., 2020), Adaptive Constraint Propagation (ACP) (Ye et al., 2023a), and the searning-baser CL-LNS frame- work (Huang et al., 2023b). Additionally, we include tra- ditional solvers like Gurobi (Gurobi Optimization, LLC, 2023) and SCIP (Maher et al., 2016), as well modern ML-based frameworks such GNN&GBDT (Ye et al., 2023c) and Light-MILPopt ( (Ye et al., 2023b). To ensure a fair comparison, Gurobi is used as the sub-solver in the neighborhood search step across all methods. For LLM- LNS, the neighborhood selection strategy is trained over 20 iterations on smaller problems before being applied to larger instances. Detailed results and discussions provided in the Appendix F.
In addition, LLM-LNS shows clear advantage over tra- ditional solvers like Gurobi and SCIP, as well as learning- based methods such as GNN&GBDT and Hight-MILPope While traditional solvers perform competitively on smaller instances, their performance degrades significantly as the problem size increases. Similarly, learning-based methods struggle with large-scale MILPs, finding it difficult to ef- ficiently explore the exponentially growing solution space. In contrast, LLM-LNS consistently delivers superior re- sults across both small and large-scale problems, offering a scalable and efficient solution. These findings suggest that LLM-LNS not only bridges the gap between traditional and burning-based methods, but also opens new avenues for scalable optimization in large-scale MILPs.
4.2.2. EFFICIENCY AND CONVERGENCE ANALYSIS
4.2. 1. EFFECTIVENESS COMPARISON
To further assess the efficiency and convergence behavior of LLM-LNS on large-scale MILP problems, we analyze both the objective- trajectories and the primal integrals of all evaluated methods. The objective-time plots, shown in Figure 3, illustrate how quickly each method improves the solution quality over time, while the primal integral values, common way in the MILP literature to quantify heuristic performance over time, summarized in Table 5, provide a holistic measure of convergence efficiency over the entire optimization period. Across all benchmark instances, L.M-- LNS demonstrates the fastest convergence and most stable performance, consistently reaching high-quality solutions earlier than all baselines. This is particularly evident on large and complex instances like SC₂, MVC2, and MIKS,, where traditional solvers and marning-based methods either converge slowly or stagnate. LLM-LNS shows sharp drop (for minimization) or rapid rise (for maximization) in the objective value early in the optimization process, indicating superior efficiency. The primal integral results (Table 5) fur- ther highlight its effectiveness, with LLM-LNS achieving
In this section, we evaluate the effectiveness of LLM-LNS by comparing its performance with various state-of-the methods across different problem instances. To ensure a fair comparison, all methods are evaluated under the same computational time limit, and the final objective function values are used as the primary metric for comparison. This allows us to assess not only the solution quality but also the efficiency with which each method converges to the optimal or near-optimal solutions. The results, summarized in Table 4, show that LLM-LNS consistently outperforms traditional LNS-based heuristics and learning-bast based methods. Unlike hand-crafted LNS strategies, which are typically static and less effective problem complexity increases, LLM-LNS dynamically adapts through its dual-layer self-evolutionary mechanism, enabling more efficient exploration of the solu- tion space. Even compared to state-of-the-art learning-basse LNS methods like CL-LNS, LLM-LNS demonstrates supe- rior performance. Although CL-LNS represents one of the most advanced learning-basee based approaches, it often fails to
8

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
MVC1
151
MIKSI
10
5xIP
Objectove
Obloctbr
3x
1x377
LA
2.330
2:307
2-
2000
2003
3000
1500
533
3500
3000
Time
SC2
MVC2
I52
MIK52
105
1.10
$+-30
Olppettio
oNvectvv
00:00
4000 Time
2000
Time
Time
Time
Random-UNS
CL-UNS
Gurobi
GNNAGBOT
Ligh-MILPOPT
LUN-UNSIOUrS)
Figure 3. Convergence curves of objective values over time on large-scale MILP instances. Each subplot corresponds to one benchmark instance, illustrating how the objective value evolves over time for different methods using Gurobi as optimizer.
Table 5. Comparison of primal integral on large-scale MILP instances across different methods. For each instance, the best- performing primal integral is highlighted in bold.
(Mi))
SC2(Min)
(VC
MVC2(Min)
MIS,
(MX,(Max)
(MKX,
(MKX,(Max)
Random-
3.41c407
1.6e+099
5,50e407
2.29cc409
4.47c+07
L733+09
7.08+007
4.06c409
ACP
5,43e+07
1.71e+09
5.90e-007
2.41e+09
4. 4.1let07
160e+09
6.02e+07
3.50c+09
CI.INNS
7.3ee407
3.17e+07
Gurobi
3.8le+07
2.65ee009
5.69e407
2.36c409
4.25e+07
L.55+099
6.45ee07
3.86e409
SCIP
5.18e+07
6.33e+09
6.39e+07
3.92e+09
3,34++07
7.26+407
5.77e+07
7.03e+08
GNN&GBDT
5552+477
3,75ex09
3,85e407
2.55c409
4.0ex077
140ex09
Light-MILPOPT
3.73c+07
180c+09
5,44-407
2,27c+09
4.30c+07
1.70+409
6,78c+07
4,03c+09
LIMALNS(OUrS)
3.27e+07
1.3ee099
5,42e407
2.19cv09
4.48cv07
1.8cv09
7.17e+07
4.18ev09
the best scores all instances, outperforming both classic solvers and learning- bearning-based frameworks. Notably, it achieves over 20% improvement in primal integral compared to the closest competitor on SC₂ and MVC2, while CL-LNS fails to produce results on most large-scale instances, underscor- ing the scalability limitations of existing learning-baas based LNS frameworks.
ability to balance exploration and exploitation, as guided by the Differential Memory for Directional Evolution. In the second set, we apply the LLM-INS framework to large-scale MILP problems. LLM-LNS not only out- performs traditional LNS methods and advanced solvers like Gurobi and SCIP but also shows superior scalability compared to modern MI--based frameworks. It achieves faster convergence and better solution quality, especially on large instances like SC, and MIKS,, where other methods struggle. These results highlight the success of our LLM agent to neighborhood selection in LNS, showcasing its ability to generalize across complex problems with minimal training data, while demonstrating clear advantages in both efficiency and convergence.
While LLM-LNS offers advantages in efficiency and conver- gence, its simplicity also brings practical deployment bene- fits over traditional MI. methods. LLM-based approaches often require less infrastructure and are easier to implement and maintain compared to neural networks, which need ex- tensive training data and ongoing updates. This trade-off between performance and ease of deployment makes LLMs compelling choice for real-world applications.
5. Conclusion
Overall, the experimental results demonstrate the effec- tiveness of our proposed innovations. In the first set of experiments, we validate the capability of the Dual-layer Self-evolutionary LIM Agent to autonomously generate competitive heuristic strategies for combinatorial optimiza- tion problems, consistently outperforming state-of- of-the-art methods such as FunSearch and EOH. Further supporting this, the ablation experiments presented in Appendix G confirm the effectiveness of each component of the Dual- layer Self-cvolutionary Agent. This confirms the agent's
In this paper, we propose LLM-LNS, a Large Language Model-driven LNS framework for solving large-scale MILP problems, utilizing a dual-layer self-evolutionary LLM agent automate heuristic strategy generation. Experi- ments show that LLM-LNS consistently outperforms tradi- tional solvers, learning- based methods, and state-of-the-an LNS frameworks. Future work will explore new agent archi- tectures and broader problems, aiming to further enhance the integration of LLMs with optimization techniques.

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Impact Statement
Elhenawy, M., Abutahoun, A., Alhadidi, T. Jaber, A., Ashqar, H. I., Jaradat, S., Abdelhay, A., Glaser, S., and Rakotonirainy, A. Visual reasoning and multi-agent ap- proach in multimodal large language models (mllms): Solving tsp and misp combinatorial challenges. arXiv preprint arXiv:2407.00093 2024.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
References
Fleszar, K. milp model and two heuristics for the bin packing problem with conflicts and item fragmentation. European Journal of Operational Research, 303 53, 2022.
Adrio, G., Villorai,,, A., Juanpera, M., and Pastor, R. Milp model for the mid-term production planning in chemical company with non non-constant consumption of raw materials. an industrial application. Computers & Chemical Engineering, 177:108361, 2023.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https:://// www.//wwwwoooooo..oo. gurobi........ com.
Ahuja, R. K., Ergun, Ö., Orlin, J. B., and Punnen, A. P. A survey of very large-scale neighborhood search tech- niques. Discrete Applied Mathematics, 123(1-3):75-102, 2002.
Han, Q. Yang, L., Chen, Q., Zhou, X., Zhang, D., Wang, A., Sun, R., and Luo, X. A gnn-guided predict-and-sentt framework for mixed-integer linear programming. arXiv preprint arXiv:2302.05633 2023.
Angelopoulos, S. Online search with a hint. Information and Computation, 295: 195010,,,,, 2023.
Hoffman, K. L., Padberg, M., Rinaldi, G., et al. Traveling salesman problem. Encyclopedia of operations research and management science, 1:1573-1578, 2013.
Arnold, F. and Sörensen, K. Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research, 105:32-46, 2019.
Huang, T., Ferber, A., Tian, Y., Dilkina, B., and Steiner, B. Local branching relaxation heuristics for integer linear programs. In International Conference Integration of Constraint Programming. Artificial Intelligence, and Operations Research, pp. 96-113. Springer, 2023a.
Artigues, C., Koné, O., Lopez, P., and Mongeau, M. Mixed- integer linear programming formulations. Handbook on project management and scheduling vol. 1, pp. 17-41, 2015.
Huang, T., Ferber, A. M., Tian, Y., Dilkina, B., and Steiner, Searching large neighborhoods for integer linear pro- grams with contrastive learning. In International Con- ference on Machine Learning, pp. 13869-13890. PMLR, 2023b.
Atamtürk, A. On the facets of the mixed-integer knapsack polyhedron. Mathematical Programming, 98(1-3):145 175, 2003.
Kim, M., Park, J., et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 14:10411-10430 2021.
Beggs, A. W. On the convergence of reinforcement learning. Journal of economic theory, (22(1):1-36 2005.
Berthold, T. Primal heuristics for mixed integer programs. PhD thesis, Zuse Institute Berlin (ZIB), 2006.
Klanšek, U. A comparison between milp and minlp ap-
proaches to optimal solution of nonlinear discrete trans- portation problem. Transport, 30(2):135-144 2015.
Boyd, S. and Mattingley, J. Branch and bound methods. Notes for EE364b, Stanford University, 2006:07, 2007.
Kool, W., Van Hoof, H., and Welling, M. Attention, learn to solve routing problems! arXiv preprint arXiv: httv:/803.rk 803.08475.. 2018
Caprara, A., Toth, P., and Fischetti, M. Algorithms for the set covering problem. Annals of Operations Research, 98:353-371, 2000.
Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Informa- tion Processing Systems, 33:21 118888189118.8811181111811181118 2020.
Danna, E., Rothberg, E., and Pape, C. L. Exploring relax- ation induced neighborhoods to improve mip solutions. Mathematical Programming. 102:7 1-90, 2005.
Lange, R., Tian, Y., and Tang, Y. Large language models as evolution strategies. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 579-582, 2024.
Dinur, I. and Safra, S. On the hardness of approximating minimum vertex cover. Annals of mathematics, pp. 439- 485, 2005.
10

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Liu, F., Xialiang, T., Yuan, M., Lin, X., Luo, F., Wang, Z., Lu, Z.,, and Zhang. Q. Evolution of heuristics: To- wards efficient automatic algorithm design using large language model. In Forty-first International Conference on Machine Learning, 2024.
Shor, P. W. How pack better than best fit: tight bounds for average-case online bin packing. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp. 752-759. IEEE Computer Society, 1991.
Simon, D. Evolutionary optimization algorithms. John
Luo, F., Lin, X., Liu, F., Zhang. Q., and Wang, Z. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Informa- tion Processing Systems, 36:8845-8866 8864, 2023.
Wiley & Sons, 2013.
Song, J., Yue, Y., Dilkina, B., et al. A general large neigh- borhood search framework for solving integer linear pro- grams. Advances Neural Information Processing Sys- lems, 33:20012-20023, 2020.
Maher; S., Miltenberger, M., Pedroso, J. P., Rehfeldt, D., Schwarz, R., and Serrano, F. PySCIPOpt: Mathematical programming in python with the SCIP optimization suite. In Mathematical Software - ICMS 2016, pp. 301-307. Springer International Publishing, 2016. doi: 10.1007/
Sonnerat, N., Wang, P., Ktena, I., Bartunov, S., and Nair, V. Learning a large neighborhood search al- gorithm for mixed integer programs. arXiv preprint arXiv:2107. 100.:0000.000,,, 2021.
778-3-319-42452-3.31
Tang, X., Li, Y., Ren, R., and Cai, W. On first fit bin packing for online cloud server allocation. In 2016 IEEE Inter- national Parallel and Distributed Processing Symposium (IPDPS), pp. 323-332. IEEE, 2016.
Mara, S. T. w., Norcahyo, R., Jodiawan, P., Lusiantoro, L., and Rifai, A. P. A survey of adaptive large neighbor- hood search algorithms and applications. Computers & Operations Research, 146: 105903, 2022.
Tarjan, R. F. and Trojanowski, A. E. Finding a maximum independent set. SIAM Journal on Computing, 6(3):537- 546, 1977.
Morrison, R., Jacobson, S. H., Sauppe, J. J., and Sewell, E. C. Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19:79-102, 2016.
Vázquez, D., Fernández-Torres, M. J., Ruiz-Femenia, R.,
Jiménez, L., and Caballero, J. A. Milp method for objec- tive reduction in multi-objective optimization. Computers & Chemical Engineering, 108:382-394, 2018.
Nair, V., Alizadeh, M., et al. Neural large neighborhood search. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020.
Voudouris, C., Tsang, E. P., and Alsheddy, A. Guided local search. In Handbook of metaheuristics, pp. 321-361. Springer, 2010.
Perron, L. and Furnon, V. Or-tools. URL https:// developers. google.
zation//
Pisaruk, N. Mixed integer programming: Models and meth- ods. Minsk: BSU, 2019.
Wu, Y., Song, W., Cao, Z., and Zhang, J. Learning large neighborhood search policy for integer programming. Ad- vances in Neural Information Processing Systems, 34: 30075-30087, 2021.
Plaat, A., Wong, A., Verherne, S., Broekens, J., van Stein, N., and Back, T. Reasoning with large language models, survey, arXiv preprint 1511 2024.
Yang, C., Wang, X., Lu, Y., Liu, H., Q. V., Zhou, D., and Chen, X. Large language models as optimizers. In The Twelfth International Conference on Learning Represen- tations, 2024. URL https: http///ppeeeeeeeeeeeeeeeeeeeeeee .ettreviieeeeee/eeeeeeee Borum?id-Bb4vooRUe
Reinelt, G. Tsplib-a traveling salesman problem library. ORSA journal on computing, 3(4):376-384, 1991.
Camera-Paredess B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J., Ellenberg, S., Wang, P., Fawzi, O., et al. Mathematical discoveries from program search with large language models. Nature, 625 (7995):468-477) 2024.
Ye, H., Wang. H., Xu, H.,, Wang. C., and Jiang, Y. Adap- tive constraint partition based optimization framework for large-scale integer linear programming (student abstract). Proceedings of the AAAI Conference on Artificial In- telligence, volume 37, pp. 16376-16377, 2023a.
Rosenkrantz, D. J., Stearns, R. E., and Lewis, II, P. M. An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, ((3):563-581. 1977.
Ye, H., Xu, H., and Wang, H. Light-milpopt: Solving large- scale mixed integer linear programs with lightweight op- timizer and small-scale training dataset. In The Twelfth International Conference on Learning Representations, 2023b.
Seiden, S. S. On the online bin packing problem. Journal of the ACM (JACM), 49(5):640-677 2002.

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Ye, H., Xu, H., Wang, H., Wang, C., and Jiang, Y. GNN&GBDT-guun -guuidd fast optimizing framework for large-scale integer programming. In Proceedings of the 40th International Conference on Machine Learning, vol- ume 202, pp. 39864-39878. PMLR, 2023c.
Ye, H., Wang, J., Cao, Z.., and Song, G. Reevo: Large language models as hyper-heuristics with reflective evo- lution. arXiv preprint arXi::2402.01145, 2024.
Zhang. J., Liu, C., Li, X., Zhen, H.-L., Yuan, M., Li, Y., and Yan, J. A survey for solving mixed integer programming via machine learning. Neurocomputingg 519:205-217, 2023.
Zhou, J.. Wu, Y., Cao, Z., Song, W., Zhang, J., and Chen, Z. Learning large neighborhood search for vehicle routing in airport ground handling. IEEE Transactions on Knowl- edge and Data Engineering, 35(9):969-99782 2023.
12

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
A. Overview of Appendix
This Appendix contains four sections, each addressing a specific aspect of the experimental setup and results. Below is a brief overview of each section:
Detailed Methodology of the Proposed LLM-LNS Framework (Appendix B): This section provides a detailed explanation of the LLM-LNS framework, including the pseudocode of the framework, a detailed example of the dual- layer evolution process, the population management strategy, and the pseudocode of the Adaptive Large Neighborhood Search (ALNS) algorithm.
Parameter Settings (Appendix C): This section describes key experimental parameters, including the number of top- performing heuristic strategies evaluated, thresholds for stagnation detection, and criteria for evolutionary convergence. Parameter values for Bin Packing (BP), Maximum Vertex Covering (MVC), and Mixed Integer Knapsack Set (MIKS) are also outlined.
Evolutionary Process of LLM-LNS (Appendix D): This section explains the co-evolution of the inner and outer layers in the Dual-layer Evolutooou LLM Agent. includes comparisons between the Evolution of Heuristic (EoH) method and the proposed dual-layer approach for problems like Bin Packing and Traveling Salesman Problem (TSP).
Convergence Analysis of LLM-LNS (Appendix E): This section analyzes the convergence behavior of the LLM-LNS method compared to EoH. Faster convergence rates, superior solution quality, and greater stability in problems like Online Bin Packing and Traveling Salesman Problem are demonstrated through graphs and figures.
Supplementary Experiments for LLM-LNS on Large-Scale MILP Problems (Appendix F): This section presents the performance of LLM-LNS on large-scale Mixed Integer Linear Programming (MILP) problems, evaluated with different subsolvers (e.g., SCIP) and compared traditional and learning-basse methods. Error bar comparisons highlight solution consistency and reliability.
Ablation Study of the Dual-Layer Self-evolutionary LLM Agent (Appendix G): This section evaluates the contribu- tions of the dual-layer framework, analyzing the roles of Prompt Evolution (outer layer) and Directional Evolution (inner layer). Results from small- and large-scale datasets highlight their complementary effects on convergence, diversity, and performance.
Additional Validation Experiments (Appendix H): This section presents experiments validating the stability, general- ization, and robustness of LLM-LNS, with deeper insights into its scalability and consistency.
Limitations and Future Directions (Appendix I): This section discusses the limitations of the proposed framework and outlines potential future directions to enhance its scalability and applicability.
These appendices provide a comprehensive overview of the experimental setup, evolutionary process, convergence analysis, and supplementary experiments, offering deeper understanding of the performance and robustness of the LLM-LNS method in solving complex combinatorial optimization problems.
B. Detailed Methodology of the Proposed LLM-LNS Framework
This appendix provides a detailed explanation of the methodology used in the LLM-LNS framework, with a focus on the evolutionary process and optimization strategies. The section is divided into four parts:
1. Pseudocode of the Proposed LLM-LNS Framework: A pseudocode representation of the overall LLM-LNS framework, providing an overview of its dual-layer self-evolutionary structure and integration with the Adaptive Large Neighborhood Search process.
2. Detailed Example of Dual-layer Evolution Process: A detailed example of the evolutionary process, highlighting the evolution of heuristic strategies and evolutionary prompt strategies over generations, as illustrated in Figure 4.
3. Population Management Strategy: A comprehensive description of the population management strategy employed to balance exploration and exploitation during the evolution.
4. ALNS Pseudocode: The complete pseudocode of the Adaptive Large Neighborhood Search (ALNS) algorithm, which was omitted from the main text due to space constraints.
13

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Algorithm 1 Pseudocode of the Proposed LLM-LNS Framework
Require: Small-scale MILP training dataset Pumin, large-scale MILP testing dataset Pisa. maximum outer iterations Tomer. maximum inner iterations Tiner. stagnation threshold Estanatioon. population size N, ALNS parameters
1: Step 0: Initialization
2: Initialize heuristic strategy population Ho using the LLM with initialization prompt strategies
3: Initialize prompt strategy populations Penss and Pou with handcrafted prompts
4: Set stagnation counter Eno_improse <- and best fitness best fitness f- oo
5: for louter = 1 to Taser do
> Outer Layer: Prompt Strategy Evolution
6: Fix current prompt strategies Peroes and Pvur
7: for fumner 1 to T Timee do
Inner Layer: Heuristic Strategy Evolution
8: Step Generate New Heuristic Strategies
9:
for each selected heuristic strategy H in H do
10:
Use fixed prompt strategies (from Powss or Psw) to guide the LLM
11:
Generate new heuristic strategies through crossover, variation, hybrid operations end for
12:
13:
Add newly generated heuristic strategies to Higar and prune to maintain population size
14:
Step 2: Evaluate Heuristic Strategies
15:
for each heuristic strategy H in Him.. do
16:
Apply H in the ALNS process to solve small-scale MILP instances from Duain Compute fitness score fHH based on objective values
17:
18:
end for
19:
Update Hemner by selecting top-N heuristic strategies based on their fitness scores Increment Ln improeee if no improvement in best_fitnes, end for
20:
21:
End of Inner Layer
22:
Step Evaluate Prompt Strategies and Avoid Stagnation
23:
if no improvement in best_fitness for Esmgaation outer iterations then
24:
for each prompt strategy P in [Perss, } do
25:
Use LLM to generate new prompt strategies through crossover/variation prompts Evaluate new prompt strategies based the fitness scores of the heuristics they generate end for Prune underperforming prompt strategies and retain top-N strategies
26:
27:
28:
29:
Reset Lao improve f- 0
30: end if
31: end for
End of Outer Layer
32: Step 4: Apply ALNS with Best Heuristic Strategy (Testing on Drest
33: Select the best hcuristic strategy H" from Hime
34: Use H' to guide the ALNS process for solving large-scale MILP instances from Diesi
35: return Best heuristic strategy H² and corresponding solution
B.1. Pseudocode of the Proposed LLM-LNS Framework
The pseudocode outlined in Algorithm follows dual-llyer structure, with an Outer Layer responsible for evolving prompt strategies maintain diversity and an Inner Layer focusing on evolving heuristic strategies for improved convergence. The process is divided into the following steps:
Initialization. The framework initializes two key populations: (1) the heuristic strategy population Ho. generated by the LLM using initial prompt strategies and small-scale MILP problem structures; and (2) the prompt strategy populations Penoss and Pear. handcrafted perform basic crossover and variation operations. A stagnation counter and the best fitness value are also initialized to monitor the evolution process.
Outer Layer: Prompt Strategy Evolution. This layer maintains and evolves the prompt strategy populations Perss and Par At the beginning of each outer iteration, the current prompt strategies are fixed and passed to the Inner Layer for heuristic strategy evolution. After the inner loop completes, the Outer Layer evaluates whether the prompt strategies need to evolve to avoid stagnation. If no improvement in fitness is observed over multiple outer iterations, new prompt strategies are generated using the LLM, evaluated, and updated to ensure diversity in heuristic generation.
Inner Layer: Heuristic Strategy Evolution. Under the guidance of fixed prompt strategies, the Inner Layer evolves the heuristic strategy population H. This process involves:
- Generating New Heuristic Strategies. Using prompt strategies (crossover or variation) from the Outer Layer, the L.M generates offspring heuristic strategies by applying operations such as crossover or mutation to parent
14

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
strategies. The offspring strategies added to the population, and low-performing strategies are pruned to maintain a fixed population size N.
Evaluating Heuristic Strategies. Each heuristic strategy is integrated into the ALNS process and applied to small-scale MILP instances. The fitness of each strategy calculated based on its performance (e.g.. objective value). Hligh-performin strategies are selected form the next generation, ensuring the population improves over time.
Step 4: Apply ALNS with Best Heuristic Strategy. After the dual-layer evolution completes, the best-performing heuristic strategy H* is selected from the final heuristic strategy population H. This strategy is applied large-scare scale MILP problems in the testing dataset Des using the ALNS process. The heuristic guides the ALNS framework in dynamically selecting and exploring variable neighborhoods, enabling efficient navigation of the solution space for large-scale optimization problems.
The dual-layer framework provides robust method for solving large-scale MILP problems by combining the exploration capabilities of prompt strategy evolution in the Outer Layer with the optimization power of heuristic strategy evolution in the Inner Layer. This structure ensures a balance between exploration and exploitation, while the LLM efficiently generates creative and effective strategies for both layers.
B.2. Detailed Example of Dual-layer Evolution Process
This subsection provides detailed example of the evolution process for the Dual-layer Self-evolutionary LLM Agent, corresponding to Figure 4. This example illustrates how heuristic strategies and evolutionary prompt strategies are iteratively refined over generations to improve performance, with specific focus on the interplay between the Inner and Outer Layers.
B.2.1. INNER LAYER: HEURISTIC STRATEGY EVOLUTION
The Inner Layer evolves heuristic strategies iteratively, starting from basic initializations and progressively incorporating advanced techniques. The evolution process includes the following key stages:
Generation 0: Initialization. The heuristic strategies are initialized using simple capacity- -base methods derived from problem structures. For instance, a heuristic employs a capacity ratio with penalties:
scores[bing > item] bins
item
X
(5)
bins
index of bin + 0.5
At this stage, the fitness value 0.9595. The Outer Layer initializes basic prompt strategies (e.g., Cross1 and Variation to generate variations of these heuristics, creating a foundation for further exploration.
Generation 5: Exploration with Randomness. To encourage exploration, randomness is introduced into the heuristic scoring functions. This adjustment enables the system to escape local optima, resulting in fitness value of 0.9916. For example:
scores(bins > item] bins item
hins 10
hins 2 (1 (1- 30
bins item max(bins) ) + randomness x 0.1.
(6)
bins + 10 max
This improvement is guided by Outer Layer prompts such as Cross2, which emphasizes "creating algorithms inspired by existing ones," and Variation2, which "adjusts parameters of given algorithms for better exploration."
Generation Hybrid Optimization. Advanced hybrid optimization methods, such as genetic algorithms combined with tabu search, are introduced. These methods allow the system to explore more diverse solutions while avoiding local optima. The fitness value improves to 0.9934. An example heuristic adapts historical penalties refine its search direction:
bins item
(bins/ / 11)
scores[bins > item]
history penalty
bins 10-3
max (bins/ 11)22)
mutation variance (1
-11-max(bi)) max(bins) 10 -
bins - item
15

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Fitness Value (erffrmmro
Evalution of Evalutionary Prompt Straiegy
Cres3: Design as advanced digor dus wah complexit relaction.
Evolution of Evalationary Prompt Strategy
Cross: Develop novel heureti by syntheiiing methodroogies to reduce the otycceve fination.
Cross: Sugaest teuristi
efficesey.
Croad: Cratza hearitic using unigue elementeand sttptin laminng mimmiration
Varadeu3: Recentiguze
beuisso.
Varidion:: Adjoct scorc function papemckrs optimie cap oprratioon simlajix
Varaties: Ad nochasso elenents adayave learning
Variatin6: Invalipte and ralesign haridiio usng insumsationa techiiuus fir bolks optiniosiaa.
0.9942
0.9942
Evolation lleuristic Strategy
0.9934
0.9934
Adkall power and prisimity penaláx
scores(bies (tewa] (iseittes)
ausste-s
Evolution of Heurstii Stralegy Swarm intd iycnce
simolated amnealing
0.9916
0.9916
0,9918
scomrssBin items Dassede-
Dhsestion)
temperattrr was (270)
Oht ato?
0.9911 0.9911
(ginbal best scomes) x 0.1 randore udjustmment
Management of Evelationnry Prompt Straiegy
Evalution of Heuràttic Strategy
-Cnnsll comalee-smmppllllly now noweggeellen
Added mademmees explonation
-Gross Design edvenoed elgrrihmm-ette weterrimmwwe-eeerpleee www.weeweeeeeetteeeeeeeeoee
Varizfonn: parometors the givnalgoriemm-
xtoresfblne >- (hers]
ttaa 1 ma
Vasuiiinn Add
VustERou + ratdommess D.1
Lissiitens
Evedution of Hearistic Stratogy
Hybrid optimication with gonetic alporithu + tabu warch
Initiallzation Hluriitic tic Strategy ratie with ontertion
pastorypemslyy
scor eojoss > item]
Desusa" vaor 1000//m/ mutotion varimeee
InHinlization Evalutionnry Prompt Strategy
Evolution of Heariste Strategy
Cross:: Create completely new alpor thmn.
Randlmiizall adjastmmnt far divendty
0.9595
Cross: Create sinww algorthim inspired by the given ones.
Varation:: Modiy the given alporthmm
scor coress > icem] - Oite-itee) Dansitar
maon Baay
Mideelets maxtivs)
random alistteen
Varenon2: Change the prrameters of the given algortthm.
10 Number of generations
15
Figure 4. Evolution of Dual-layer Self-evolutionary LLM Agent for online bin packing. We outline the key thoughts of the best heuristics produced in some generations during the evolution of heuristic strategies. Additionally, highlight the evolution of evolutionary prompt strategies, which dynamically adapt the prompt strategies to guide the L.M in generating more effective and diverse heuristics.
Outer Layer prompts evolve introduce complexity-reducing techniques (e.g., Cross3: "Reconfigure heuristic principles to reduce computational complexity while maintaining effectiveness"). enabling the generation of lighter yet more powerful heuristics.
Generation 12:
Swarm Intelligence and Diversity Increase. By combining swarm intelligence methods (e.g.. simulated annealing) with randomized adjustments, the heuristic strategies achieve fitness value of 0.9942. The scoring function now incorporates global optimization techniques:
bins item
(bins/12)
(1
bins - item max(bins)
)
scores/bins > item]
bins 10-5 temperature max (abxxx/b/////aa (bins/12)2)) 12)22
(8)
+ (global best - scores) x 0.1 + random adjustment.
Prompts such as Variation4 ("Add stochastic elements and adaptive learning") guide this evolution, introducing diversity and enabling broader exploration of the solution space.
B.2.2. OUTER LAYER: EVOLUTIONARY PROMPT STRATEGY EVOLUTION
The Outer Layer evolves evolutionary prompt strategies to guide the LLM in generating new heuristic strategies. The evolution of prompts adapts to the performance of the Inner Layer, as follows:
Generation 1: Initialization. Basic prompt strategies, such as Crossl ("Create a completely new algorithm") and Variationl ("Modify the given algorithm""), are handcrafted initialize the system. These prompts enable the LLM to generate simple heuristics based on problem structures.
Generation 6: Addressing Stagnation. As performance stagnates, advanced prompt strategies introduced. For example, Cross3 emphasizes reducing algorithmic complexity:
- Example Prompt: "Reconfigure heuristic principles to reduce computational complexity while maintaining effectiveness."
16

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Generation 10: Adaptive Learning. Prompts such VariationS and Variation6 incorporate stochastic adjustments and adaptive learning overcome local optima:
Example Prompt: "Enhance diversity by introducing stochastic elements refine exploration strategies."
These prompts enable the generation of heuristics that combine exploration and exploitation effectively.
Generation 18: Pruning Underperforming Strategies. Underperforming prompt strategies pruned based their fitness scores, ensuring that only the most effective prompts are retained. This step streamlines the search process and focuses computational resources on high-performing strategies.
B.2.3. SYNERGY BETWEEN LAYERS
The synergy between the Inner and Outer Layers is evident in the performance improvements across generations, as shown in Figure 4. Each major improvement corresponds to a refinement of both heuristic strategics and prompt strategies:
Between Generations and 5, randomness introduced by Variation2 enables broader exploration, significantly boosting fitness from 0.9595 to 0.9916.
Between Generations and 8, hybrid optimization techniques (e.g., genetic algorithms) guided by Cross3 prompts enable heuristics to escape local optima, achieving a fitness of 0.9934.
Between Generations 8 and 12, swarm intelligence combined with stochastic adjustments (guided by Variation4) further enhances diversity, pushing the fitness 0.9942.
Overall, the Outer Layer's refinement of prompt strategies drives the Inner Layer's 's ability to generate increasingly sophisti- cated heuristics, demonstrating the power of the dual-layer evolution process.
B.3. Population Management Strategy
To ensure the effectiveness and diversity of strategies within the LLM-LNS framework, we employ a population management strategy that balances exploration and exploitation during each generation. This strategy governs the selection of parent strategies for evolutionary operations (c.g., crossover and mutation) and the replacement of poorly performing strategies to maintain a high-quality population.
B.3.1. SELECTION EVOLUTIONARY STRATEGIES
At each generation, the framework uses probabilistic sampling mechanism to select m parent strategies from the population for crossover and mutation. The probability of selecting a strategy is determined by its fitness value, which reflects its performance in achieving the optimization objective. Specifically, let the population contain n strategies with fitness values ranked in descending order as fi.J2..... fn. The probability of selecting the i-th strategy is given by:
P i+1+n 1
where i represents the rank of the strategy (starting from 0), and n is the population size. This ranking-based probability distribution ensures that higher-fitness fitness strategies are more likely to be selected while preserving some randomness to allow lower-fitness strategies to participate. Such randomness enhances exploration by preventing premature convergence to local optima.
Using this probability distribution, we sample m parent strategies for evolutionary operations. These operations generate new candidate strategies, which are evaluated and integrated into the population based on their fitness values.
B.3.2. MANAGEMENT OF POORLY PERFORMING STRATEGIES
After each generation, the population is updated to maintain a fixed size while ensuring diversity and quality. Let the current population be P = {$1, $2...., }, where each strategy s; has a fitness value f(s:). The goal is to construct a new population P' such that:
17

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Algorithm 2 Adaptive Large Neighborhood Search (ALNS)
Require: Initial solution Xa, initial neighborhood size k, time limit threshold c, iteration limit p. minimum and maximum neighborhood sizes kmin, kmax. decision variable count n, adjustment rate a% (percentage)
1: Initialize solution x f- Xg, set time t <- 0
2: while < T do
3: Compute variable scores 8, using the L.M agent
4: Select top-k variables to form neighborhood N
5: Solve subproblem within N using a solver
6: Update solution x if an improvement is found
7:
if time spent in neighborhood exceeds predefined limit then
k + ( k [u%- ni) else if improvement objective value < for consecutive iterations then 10: k 4- miin(kmax, & + [4% n])
8:
P Reduce neighborhood size by u% of
9:
b Expand neighborhood size by 4% of m
11:
end if
12: Update time
end while
14:
return x
Pl contains at most size strategies, where size is predefined parameter,
Strategies with duplicate fitness values are removed,
The highest-fitness strategies are retained.
The population update process is as follows: 1. Remove strategies with invalid or undefined fitness values. 2. Eliminate duplicate strategies by retaining only one instance of strategies with the same fitness value. 3. Rank the remaining strategies by fitness value descending order and select the top size strategies to form the new population p'
This management process ensures that the population remains diverse while focusing on high-quality strategies, avoiding redundancy and inefficiency. By preserving the highest-fitne fittesttiitesss strategies and introducing new candidates through evolutionary operations, the framework achieves balance between exploration and exploitation.
B.3.3. FITNESS EVALUATION
The fitness value of a strategy is determined by its optimization performance on a set of small-scale training problems. Specifically, the fitness value fs: for a strategy s; calculated as the average objective value achieved across multiple problem instances:
((x)) = T
Σ
Obj(st (bj(s;,T)) 4,), JET
(10)
where I is the set of training problem instances, and Obj(s; I,) represents the objective value achieved by strategy 8; on instance 1j. This evaluation method ensures that strategies are assessed based on consistent and robust performance metrics.
B.3.4. SUMMARY
The population management strategy in the L.M--LNS framework combines fitness-based selection, diversity preservation, and rigorous fitness evaluation. By maintaining high-quality and diverse population, the framework progressively improves the quality of strategies across generations. This strategy, together with the LLM's ability generalize and optimize, enables the LLM-LNS framework efficiently navigate large and complex search spaces, balancing exploration and exploitation to achieve superior optimization performance.
B.4. ALNS Pseudocode
This subsection presents the pseudocode for the Adaptive Large Neighborhood Search (ALNS) algorithm, which dynamically adjusts the neighborhood size and leverages the Dual-layer Self-evolutionary L.MM Agent to efficiently solve large-scale MILP problems.
Explanation of the ALNS Algorithm. The Adaptive Large Neighborhood Search (ALNS) algorithm is designed to iteratively improve solutions for large-scale MILP problems by dynamically adjusting the search space based on feedback
18

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
from the optimization process. The key steps of the algorithm are as follows:
Initialization:
The algorithm begins with an initial solution Xo and an initial neighborhood size k. A time limit 7 and other parameters, such as threshold e, iteration limit p. and neighborhood size bounds kimin and kmax, are predefined.
Variable Scoring and Neighborhood Selection: At each iteration, the Dual-layer Self-evolutionary LLM Agent computes scores 8; for the problem's ' decision variables z;, indicating their potential to improve the objective value. The top-k variables are then selected to form the neighborhood .V:
N
(a3 rank(s;) S k)-
(11)
Subproblem Solving: Within the selected neighborhood N,, subproblem is solved using solver. If the solution improves the objective value, the solution is updated.
Dynamic Adjustment of Neighborhood Size:
Reduction: If the time spent solving subproblems within the neighborhood exceeds predefined limit, the neighborhood size i is reduced to focus on smaller subset of variables:
k + max(kimin k - [u% - r2]),
(12)
where 4% is the adjustment rate and n is the total number of decision variables.
Expansion: If the improvement in the objective value is less than e for p consecutive iterations, the neighborhood size is expanded explore a broader search space:
h <- min(kmax, ks + [u% (om6n.]) n2)-
(13)
Termination: The process continues until the time limit T is reached, at which point the best solution x is returned.
The ALNS algorithm's dynamic adjustment of neighborhood size ensures efficient exploration and exploitation of the solution space. By leveraging the L.LM agent to score variables, the algorithm generalizes variable selection strategies learned from small-scale MILP problems, enabling its application to larger, more complex problems. The combination of intelligent variable scoring and adaptive neighborhood adjustment allows ALNS to efficiently navigate the vast search space, improving solution quality while maintaining computational efficiency.
C. Experimental Settings
In this section, we detail the parameter settings used in our experiments for both the Dual-layer Self-evolutionary LLM Agent and the Adaptive Large Neighborhood Search (ALNS). We also provide an overview of the standard MILP problem instances used in this study. Furthermore, we will describe the specific function signature that our self-evolutionary LLM agent is designed to evolve.
C.1. Dual-layer Sell-evolutionary LLM Agent Parameters
The following key parameters were used for the evolutionary process of the LLM agent:
h: Represents the number of pop-perforning heuristic strategies used to evaluate each prompt strategy. For each prompt strategy, the top-h heuristics it generates are tracked, and their average fitness score is used as the fitness score for the prompt strategy. In our experiments, h is set to half of the population size. Specifically:
For Bin Packing (BP) and Traveling Salesman Problem (TSP), the population sizes are 20 and 10, respectively, so h is set to 10 and 5.
For the four MILP Pobbless-Mxxmmnn Vertex Covering (MVC), Set Covering (SC), Independent Set (IS), and Mixed Integer Knapsack Set (MIKS) population size is 4, h is set to 2.
I: Denotes the number of top individuals in the heuristic population that are monitored for stagnation. If the top-/ individuals remain unchanged for t generations, we infer that the evolution has potentially converged to local optimum, triggering the introduction of new prompt strategies. In all our experiments, is set to 4.
t: The number of consccutive generations during which the top-/ individuals must remain unchanged before stagnation is detected. In all our experiments, f is set to 3.
19

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
C.2. Adaptive Large Neighborhood Search (ALNS) Parameters
For ALNS, we use the following parameters:
Neighborhood size k: Set to half of the decision variable count n. This represents the number of decision variables selected to form the search neighborhood in each iteration.
Time limit T: To ensure robustness and avoid excessive computation, we impose a maximum time limit per LNS iteration: 100 seconds for problems with approximately 100K variables and 200 seconds for problems with around IM variables. This time limit is applied uniformly across all LNS-based baselines to prevent slow subproblem solves, ensuring efficiency and fair comparison in our experiments.
Threshold e: Represents the minimum improvement in the objective function to continue exploring the current neighborhood. We set = 1e-3.
Iteration limit p: The number of consecutive iterations with improvements below the threshold before expanding the neighborhood size. We set 3.
Minimum and maximum neighborhood sizes kimin k These are set to kmin = and kmax = n. (the total number of decision variables the problem).
Adjustment rate a%: Specifies the percentage of decision variables by which the neighborhood size is adjusted during expansion or reduction. In our experiments, we set u% = 10.
C.3. Datasets for Heuristic Evolution
To ensure a fair comparison with state-of-the-art methods such as EOH, we adopted the same dataset configurations as those used in EOH for heuristic evolution. For example, the online bin packing problem, the evaluation dataset consists of five sets of instances, each containing 5,000 items generated from a Weibull distribution. These instances cover wide range of item counts and container capacities, ensuring the diversity and representativeness of the problem settings. Similarly, for the traveling salesman problem (TSP), we utilized 64 randomly selected instances from TSP100, which were also used in EOH's experiments. These instances provide well-established basis for evaluating heuristic performance in combinatorial optimization tasks.
For MILP problems, we followed a similar design approach to that used in the online bin packing problem. Specifically, we employed five small-scale MILP problems, each involving tens of thousands of decision variables and linear constraints. These smaller-scale problems serve as a foundation for heuristic evolution, allowing the method to generalize effectively to larger-scale MILP problems with hundreds of thousands or even millions of decision variables. This demonstrates the scalability and practical applicability of our approach when addressing large-scale optimization challenges.
C.4. Experimental Settings for Algorithm Design
Our proposed dual-layer agent framework is designed to evolve heuristics for solving combinatorial optimization problems, specifically targeting Online Bin Packing (BP) and the Travelling Salesman Problem (TSP). The dual-layer architecture is responsible for learning and refining heuristic strategies for these problems, enabling efficient and scalable solutions. Below, we provide detailed descriptions of the experimental settings for each problem.
For Online Bin Packing, we adopt the settings described in PRorera-Paredes et al., 2024) and (Liu et al., 2024) to design heuristics for determining suitable bin allocations for incoming items (Angelopoulos, 2023). The task of the dual-layer agent is to design scoring function that assigns items to bins. The inputs to the agent include the size of the item and the remaining capacities of the bins, while the output is set of scores for the bins. The item then assigned the bin with the highest score. This process is iterated for each incoming item, allowing the agent to dynamically adapt its scoring strategy based on the evolving state of the bins.
For the Travelling Salesman Problem (TSP), we use the dual-layer agent to design heuristics for Guided Local Search (GLS) (Voudouris et al., 2010). GLS introduces perturbations and dynamically adjusts the objective landscape to help escape local optima, enabling broader exploration of the solution space. A critical task in GLS is updating the distance matrix to guide the local search towards more promising regions. In this context, the dual-layer agent tasked with producing
20

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Table 6. The size of one wealdworld case study in the internet domain and four widely used NP-hard benchmark MILPs.
Number Variables
Number
Problem
Scale
Constraints
SC
SC₁
200000
200000
(Minimize)
SC2
2000000
2000000
MVC
MVC1
100000
300000
(Minimize)
MVC2
1000000
3000000
MIS
MIS
100000
300000
(Maximize)
MIS
3000000
MIKS
MIKS 1
200000
200000
(Maximize)
MIKS²
2000000
2000000
heuristics for updating the distance matrix. The inputs include the current distance matrix, the current route, and the number of edges, while the output is an updated distance matrix. GLS then applies local search operators iteratively on the updated landscape to refine the solution. In our experiments, we utilize two common local search operators: the relocate operator and the 2-opt operator, which are widely recognized for their effectiveness in TSP optimization (Arnold & Sörensen, 2019).
These settings are aligned with those used in EOH to ensure fair comparisons and reproducibility. Detailed descriptions of the inputs, outputs, and operators are provided in the appendix of the manuseript further clarify our experimental configurations.
We also emphasize that seed heuristics, expert-written code, or prior knowledge were manually introduced during the experiments. All heuristic strategies were initialized automatically by the large language model (LLM), ensuring fairness in the comparisons.
C.5. MILP Problem Overview
We use set of standard problem instances based on four canonical MILP problems: Maximum Independent Set (MIS), Minimum Vertex Covering (MVC), Set Covering (SC), and Mixed Integer Knapsack Set (MIKS). Below are the formal definitions of these problems.
To ensure the robustness and fairness of our evaluation, the generation and selection of these instances follow a rigorous procedure. The instances are not arbitrarily selected but are systematically generated based standard formulations of these canonical MILP problems. For each problem class and size category, a substantial set of instances is initially generated by randomly sampling parameters from consistent underlying distribution specific to that problem class. Subsequently, these generated instances are randomly partitioned into training and testing sets, preventing selection bias and ensures a more reliable assessment of our framework's generalization capabilities across different problem types and scales.
To evaluate the scalability and generalization ability of our framework, we design experiments on both small-scale training instances and large-scale testing instances. Specifically:
The small-scale training instances are designed with sizes corresponding to 1% of the decision variables and constraints of the large-scale testing instances. These small-scale problems are used to train and evolve heuristic and prompt strategies.
The large-scale testing instances are significantly larger, featuring up to 10 decision variables and 3 10 constraints (as shown in Table 6). These instances are used to evaluate the generalization ability of the strategies evolved during training.
Our experimental results demonstrate that the proposed framework achieves strong generalization. effectively solving large-scale MILP problems even when trained solely small-scale instances. This highlights the ability of the framework to transfer knowledge learned from small-scale problems to much larger, real-world problems.
Maximum Independent Set problem (MIS): The Maximum Independent Set problem has applications in network design, where one might need to select the largest subset of mutually non-interacting entities, such as devices a wireless network to avoid interference. Another common application is in social network analysis, where independent sets can represent groups of users who do not have direct connections, useful for targeting non-overlapping communities.
21

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Consider undirected graph g (V,E), where subset of nodes S V is called an independent set if edge exists between any pair of nodes in S. The MIS problem seeks find an independent set of maximum cardinality. The binary decision variable zy indicates whether node V is part of the independent set (z, 1) or not (x, 0), The problem can be formulated as:
Σ Zv
max
BEV
(14)
s.t.
Zu + 2v S 1, v(u,v) EE, Tv. E [0,1),
Ve V.
Minimum Vertex Covering problem (MVC): The Minimum Vertex Covering problem is widely used in resource allocation, where one needs ensure that every interaction (edge) between pairs of objects (nodes) is covered by a resource. For example, in network security, this problem can be used to efficiently place security agents sensors such that all communication links are monitored.
Given an undirected graph G = (V,E), subset of nodes S S V is called covering set if for any edge E E, at least one of its endpoints is included in S. The MVC problem aims to find a covering set of minimum cardinality. The binary decision variable Zu indicates whether node v E V's part of the covering set (z, = 1) or not (x, = 0). The problem is formulated as:
min
Σ Z
(15)
s.t.
Tu + Fe 2 1,
V(u,u) EE,
Fy E (0,1) V.EV.
Set Covering problem (SC): The Set Covering problem is fundamental in facility location, where must select the minimum number of locations (subsets) serve all customers (elements of the universal set). It is also used in airline crew scheduling, where the goal is to assign the minimum number of crews cover all flights.
Given a finite universal set U4 = .., n and a collection of m subsets , Sn Uf each subset S; is associated with cost ç,. The SC problem involves selecting a combination these subsets such that every element in 2/ is covered by least one of the selected subsets, while minimizing the total cost. The binary decision variable æ; indicates whether subset S, is selected (z; 1) not (z; 0). The problem is formulated as:
min
C
i=1
(16)
s.t. Σ 04 LJES 21, YjEu,
E 10.
Vi f1......., m}
Mixed Integer Knapsack Set problem (MIKS): The Mixed Integer Knapsack Set problem arises in various applications such as logistics, resource allocation, and portfolio optimization. It captures scenarios where some items can selected fractionally, while others must be either fully selected excluded. For instance, in supply chain management, certain goods can be split and shipped in parts, whereas others must be shipped complete units.
The MIKS problem extends the classical knapsack formulation by incorporating both continuous and binary decision variables, along with multiple capacity constraints. Given N items and M resource dimensions, each item consumes capacity one or more dimensions, and the total usage in each dimension must not exceed the available capacity. The objective is to maximize the total value of selected items. Let x; denote the selection variable for item i, where 2; = 1 indicates full selection, and S x; S allows partial selection. The problem is formulated as:
22

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
N
max
C
im
S.t.
Σ J; 1
Vj (1,,...,
(17)
0 < 24 S1,
Vi 2 ....,. .N. T [0,1] or [0, vi E (1,2..... N}.
C.6. MILP Problem Generation Process
The generation of MILP problems follows a structured approach to ensure consistency and diversity across problem instances. The process is broken down into several steps, as outlined below.
Step 1: Random Graph and Set Generation
For the generation of the problems, we first define the underlying structure of the problem using random graphs or sets, depending the problem type. Specifically,
For the Maximum Independent Set (MIS) and Minimum Vertex Covering (MVC) problems, we randomly generate an undirected graph G = (V, where V is a set of vertices and & is set of edges. The number of vertices and edges is chosen based on the desired problem scale.
For the Set Covering (SC) problem, we generate a collection of sets S covering elements from a universal 24 Each subset is randomly selected, and the number of sets is based the problem size.
For the Mixed Integer Knapsack Set (MIKS) problem, we generate a list of items with associated weights, profits, and capacities. The items are randomly selected, with some variables being continuous and others integer-based.
Step 2: Define Objective Function and Constraints
Once the underlying graph or sets are generated, the objective function and constraints are formulated based on the problem type:
In the MIS and MVC problems, the objective function is formulated to either maximize the number of nodes in the independent set (MIS) or minimize the number of nodes in the vertex cover (MVC), Constraints are added to enforce the independence or covering conditions.
For SC, the goal is to minimize the total cost of selected subsets while ensuring all elements in U are covered. Constraints are added to ensure that each element covered by least one subset.
In MIKS, we define prefit-weight relationship for each item, where we aim maximize the profit while ensuring the total weight does not exceed a given capacity.
Step 3: Randomization and Scaling
The parameters such as the number nodes, edges, sets, and constraints are randomly scaled to generate problem instances of varying sizes. The scaling process ensures that problem instances span broad range complexities and sizes:
For each problem class, the number of nodes (or sets) and edges (or item types) randomly sampled from predefined distribution, such uniform or Gaussian, to create diverse instances.
The size of the instances is controlled to generate both small-scale and large-scale problem instances, where small-scale instances are used for training and large-scale instances are used for testing.
Step 4: Validation and Evaluation
23

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Finally, the generated problem instances validated to ensure they adhere to the correct problem formulations. This includes checking if the constraints are satisfied and whether the generated instances match the intended problem characteristics. The performance of the model is then evaluated on the testing instances, assessing both solution quality and computational efficiency.
This systematic process ensures that the generated MILP instances cover a wide range of problem types and sizes, providing a reliable basis for evaluating optimization algorithms and models.
C.7. Evolved Heuristic Function Signature
To evaluate the effectiveness our proposed dual-layer self-evolutionaryy LLM agent, we tested its ability to design heuristic functions across three distinct classes of optimization problems: Online Bin Packing (bp_online), Traveling Salesman Problem (TSP), and general Mixed Integer Linear Programming (MILP) instances. Below, we detail the specific input and output signature of the function that our agent evolved for each problem type.
C.7.1. ONLINE BIN PACKING (BP (P_ONNINEE)
For the Online Bin Packing problem, the self-evolutionary agent was tasked with designing heuristic scoring function with the signature def score (item, bins): :.
The fundamental goal of this function is to evaluate a set of available bins and assign a score to each, indicating its suitability for the current em that needs be packed. In each step of the packing process, the i item is placed into the bin that receives the highest score among feasible options. According the problem specification, bins whose remaining capacity equals the overall maximum bin capacity are not considered for placing the current item, effectively prioritizing the use of already partially filled bins. The overarching objective is to minimize the total number of bins ultimately utilized.
Inputs::
ittem (int): The size of the current item be placed.
- bins (NumPy array): An array representing the remaining capacities of all feasible bins. These are bins that have sufficient space to accommodate the current etem.
Output:
scores (NumPy array): An array of the same dimension as bins, where each element is the calculated score for the corresponding bin.
The agent was encouraged to develop scoring logic of sufficient complexity to potentially outperform simpler heuristics and to ensure the internal consistency of the evolved function.
C.7.2. TRAVELING SALESMAN PROBLEM (TSP)
For the Traveling Salesman Problem, the agent's task was to devise a heuristic strategy for dynamically updating the edge distance matrix. The evolved function has the signature def update.edge. sedge.distance, Local_opt.tour, edgein_used): :.
(edge.di
stace,,,,
The primary objective of this function is to modify the perceived distances between nodes based on the characteristics of a recently found local optimal tour and historical edge usage. By altering the edge distance matrix, the heuristic aims to help the search process escape local optima and explore different regions of the solution space, ultimately facilitating the discovery of a tour with a minimized total distance. The function is expected to return the modified distance matrix.
Inputs:
edge.disttamee (NumPy array): The current matrix representing the distances between nodes.
local_opt.tour (NumPy array): An array of node IDs constituting the local optimal tour found in a previous iteration.
- -edge_ng edge_n_used (NumPy array): A matrix detailing the frequency with which each edge has been included in explored solutions or permutations.
24

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Output:
updateddedde..distane (NumPy array): The new edge distance matrix, adjusted by the evolved heuristic.
All imput and output arrays are NumPy arrays. This dynamic adjustment is crucial for guiding the neighborhood search effectively.
C.7.3. MIXED INTEGER LINEAR PROGRAMMING (MILP)
For Mixed Integer Linear Programming (MILP) problems, the self-evolutionary agent was tasked with designing a heuristic to guide the neighborhood selection process within a Large Neighborhood Search (LNS) framework. The objective to intelligently score decision variables to determine which ones should relaxed and re-optimized to improve the current solution. The signature of the evolved function is:
def select_neighoorhood (n, m, k, site, value, constraint, initial.soluiion
current-solution objecttiv..coeeficcentt
The primary goal of this function is to analyze the current state of the MILP problem-inehudee its structure, con- straints, objective function, and current solution-an and assign a numerical score to each decision variable. These scores (ne wwwggggbbooooooee subsequently inform LNS mechanism on which variables to include in the neighborhood (i.e., to "free" for re-optimization). The agent was encouraged to develop strategies that could consider variable correlations (e-g.. by assigning similar scores to variables involved in the same constraint) or incorporate randomness to escape local optima, aiming iteratively enhance the current solution.
Inputs:
(int): The total number of decision variables in the MILP instance.
(int): The total number of constraints in the MILP instance.
k (NumPy array): An array of length m, where k [1] denotes the number of decision variables participating in the i-th constraint.
site (list of NumPy arrays): A list of m NumPy arrays. For the i-th constraint, site [i] indicates the index (ID) of the j-th decision variable involved in that constraint.
value (list of NumPy arrays): A list of m NumPy arrays. For the i-th constraint, value [i] [d] specifies the coefficient of the j-th decision variable (as identified by site [i] [i]) in that constraint.
constraint (NumPy array): An array of length m, where constraint. [i] is the right-hand side (RHS) value for the i-th constraint.
initial solsoutt i on (NumPy array): An array length n, holding the values of the decision variables from an initial feasible solution.
current-sol lin (NumPy array): An array of length n, representing the values of the decision variables in the current incumbent solution that LNS aims to improve.
ob ject ive_coeff f cient (NumPy array): An array of length n, where ob the coefficient of the i-th decision variable in the objective function.
[1]
Output:
ne neighbor score (NumPy array): An array of length n, generated by the evolved function. Each element neighbor.score [i] corresponds to the calculated score for the i-th decision variable, influencing its likeli- hood of being selected for the LNS neighborhood.
All inputs are provided as NumPy arrays, except for n and m (integers), and site and value (lists NumPy arrays). The evolved function is responsible for creating and populating the nei neighbor.scom NumPy array.
C.8. Training Setup and Generalization TSP and Bin Packing
To ensure fair comparisons and demonstrate the generalization ability of our approach, we closely followed the experimental setups used in prior work such as EOH and FunSearch.
25

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
For the TSP experiments, we used the same five TSPLib Instances-d188, eil76, rat99, r81889, and u1060-as as the training set for evolving our policies. None of the other TSPLib instances used in evaluation were included in training. This separation guarantees that performance improvements are not due to overfitting specific instances. We will update Table 17 to clearly mark the training instances. For the Bin Packing task, we adopted the Weibull 5k test dataset as the training data, consistent with the setup in EOH and FunSearch. This ensures a comparable training environment across methods while allowing us to test the ability of our LLM agent to generalize to different instance distributions and sizes.
D. Evolutionary Process of LLM-LNS
D.1. Evolutionary Process Overview
In this appendix, we provide detailed breakdown of the experimental results and the evolution of heuristic strategies generated by our proposed Dual-layer Self-Evolutionars LLM Agent. The following sections offer a comprehensive analysis of how the inner and outer layers of the LLM agent collaborate to generate and refine heuristic strategies across various combinatorial optimization problems, including Online Bin Packing (bp_onil) oop_oniin), the Traveling Salesman Problem (TSP), and large-scale MILP instances such as Maximum Vertex Covering (MVC), Set Covering (SC), Independent Set (IS), and Mixed Integer Knapsack Set (MIKS).
Inner and Outer Layer Prompt Initialization and Evolution: As shown in Sec. D.2, our approach leverages a dual-layer architecture, where the inner layer evolves heuristic strategies by modifying solution components, while the outer layer evolves the prompt structure guiding the inner layer, balancing exploration and exploitation. The inner layer prompts iteratively generate heuristics by scoring decision variables based on their contributions to the objective function and constraints, with randomness included to avoid local optima. This enables the LLM to reason about the problem structure and generate high-quality strategies, even without extensive domain expertise. The outer layer maintains diversity by evolving prompt structures to prevent premature convergence on suboptimal solutions. Both layers adapt based on past performance, allowing the LLM to refine its strategy generation over time.
Heuristic Improvement Through Dual-layer Self-evolutionary LLM Agent:
As shown in Sec. D.3, we demonstrates the progression of heuristic strategies, starting from initial random strategies and gradually evolving into more effective ones through the dual-layer self- celf-evolutionary process. The initial strategies are simple and focus on ranking decision variables based on their contributions to the objective function and constraints. Over time, the LLM agent introduces additional complexity, such as incorporating randomness and penalizing larger deviations from the current solution, improving the robustness of the generated heuristics. The progression of the population is guided by the outer layer, which adjusts the structure and focus of prompts to encourage exploration and avoid premature convergence. The inner layer then refines specific solution components in response to the prompts, iteratively improving the performance of the heuristic strategies. As seen from the evolution of objective scores, the dual-layer system enables the generation of increasingly effective heuristics, balancing exploration with exploitation to achieve superior results in various problem instances.
Heuristic Strategies for Bin Packing Online: EoH vs. Dual-Layer Self-Evolution LLM Agent: As shown in See. D.4, both the Evolution of Heuristic (EoH) method and our Dual-layer Self-Evolution LLM Agent utilize LLMdbased evolutionary processes to generate heuristic strategies for the Bin Packing Online problem. The strategy generated by EoH approach, while leveraging LLM to evolve heuristics, focuses primarily on hybrid scoring system that combines utilization ratios, dynamic adjustments, and an exponentially decaying factor. This method is effective but tends to rely on more static set of features and parameters, which limits its adaptability across diverse problem instances. In contrast, our Dual-layer Self-Evolution LLM Agent incorporates a more dynamic and adaptive strategy. By combining nonlinear capacity scaling, relative size assessment, and historical penalties for overutilized bins, our approach allows for greater flexibility and adaptability. Specifically, the generated heuristics dynamically adjust based on remaining capacity, item size, and previous bin usage, thereby balancing local search with global optimization. This adaptability enables our agent discover and refine more efficient strategies that minimize the number of bins used. The results clearly demonstrate that while both methods use I. LLaed evolution, our dual-layer approach consistently outperforms the EoH method in terms of solution quality and computational efficiency. The dual-layer system's 's ability to evolve both the heuristic strategies and the prompt structures ensures that it can fine-tune solutions more effectively, leading to superior bin utilization and fewer bins required overall. This highlights the strength of our approach in generating more robust and context-aware heuristics.
26

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Heuristic Strategies for Traveling Salesman Problem (TSP): EoH vs. Dual-Layer Self-Evolution LLM Agent: Similar to the Bin Packing Online problem, both the Evolution of Heuristic (EoH) method and our Dual-layer Self- Evolution LLM Agent use LLM-based evolutionary processes to generate heuristic strategies for the Traveling Salesman Problem (TSP). As shown in Sec. D.5, the strategy generated by EoH method employs a randomized approach that adjusts the edge distance matrix by increasing the distances of a random proportion of edges, while rewarding a smaller subset of unused edges. This method encourages exploration but tends to apply uniform adjustments without fully accounting for the global structure of the solution. In contrast, strategy generated by our Dual-layer Self-Evolute LLM Agent introduces a more sophisticated edge distance adjustment mechanism. It dynamically explores alternative routes by incorporating an inverse frequency factor, which penalizes frequently used edges and rewards less frequently used ones. This adaptive mechanism gradually resets excessively amplified distances, promoting diversification and improving the exploration of the solution space. Furthermore, it balances exploitation by focusing on refining the most promising routes based on past tours, leading to faster convergence towards a global optimum. The results clearly demonstrate that while both methods are effective in exploring new routes, the dual-layer approach consistently outperforms the EoH method in terms of solution quality and convergence speed. By incorporating a more nuanced edge adjustment process and dynamically adapting to the problem context, the Dual-layer Self-Evolution LLM Agent achieves superior results in minimizing the total distance, making it more robust and efficient solution for the TSP.
Evolutionary Path of the Dual-Layer Self-Evolution LLM Agent: As illustrated in Sec. D.6, we trace the evolutionary process of the LLM agent in solving Maximum Vertex Cover (MVC) problem, detailing how heuristic strategies evolve step by step through the inner and outer layers, gradually converging optimized solutions. Initially, the agent generates simple heuristics that focus ranking decision variables based on their impact the objective function and constraint violation, incorporating randomness to encourage exploration. These early strategies serve as a foundation for further refinement. As the process evolves, the outer layer refines the prompt instructions, guiding the inner layer to develop more sophisticated heuristics. The LLM begins to incorporate additional factors, such as the absolute difference from the initial solution and a more nuanced treatment of constraints. This results in improved exploration of the solution space, as well as better handling of both the objective function and constraints. In the later stages, the agent integrates more advanced techniques, such as hybrid methods combining genetic algorithms with local search, to enhance convergence speed and solution quality. The final heuristics represent a co-evolutionary approach that balances exploration and exploitation, leading to significantly optimized solutions. The evolution of prompts, from the initial simplistic forms to highly specialized instructions, demonstrates the power of the dual-layer architecture in improving both the heuristic strategies and the problem-solving process itself.
Finally, we present the results achieved by the LLM agent after the completion of the entire evolutionary process across three challenging combinatorial optimization problems: Set Covering (SC), Maximum Independent Set (MIS), and Mixed Integer Knapsack Set (MIKS). As detailed Sec. D.7, the final heuristics generated by the Dual-layer Self-Evolution LLM Agent are compared with those produced by traditional methods and state-of-the-art approaches, demonstrating significant improvements in solution quality and computational efficiency. For the Set Covering problem (SC), the LLM agent's 's final heuristic achieves a superior balance between minimizing the number of selected sets and satisfying the constraints. By dynamically adjusting penalties and incorporating random exploration, the agent efficiently navigates the solution space, outperforming traditional methods in both the objective score and constraint satisfaction. In the Maximum Independent Set (MIS) problem, the LLM agent leverages simulated annealing principles combined with adaptive scoring of decision variables. This approach not only ensures thorough exploration but also accelcrates convergence towards high-que nigh-quality solutions. The agent's ability to balance objective contributions with constraint violations leads to a considerable reduction in the total error, as reflected in the final objective score. Lastly, for the Mixed Integer Knapsack Set (MIKS) problem, the LLM agent adopts hybrid strategy that integrates genetic algorithms and simulated annealing. This allows for more diversified search process, strategically selecting decision variables based on their contributions to the objective function and constraint interactions. The agent's 's solution demonstrates a significant improvement over existing methods, particularly in how it dynamically adapts to varying problem constraints while maintaining computational efficiency.
Evolutionary Result of the Dual-Layer Self-Evolution LLM Agent:
In summary, the proposed Dual-layer Self- celltvvolutionary LLM Agent effectively generates and refines heuristic strategies for diverse combinatorial optimization problems. Leveraging the complementary roles of its inner and outer layers, it balances exploration and exploitation to discover high-quality, context-aware strategies. Its adaptability in evolving both problem-solving heuristics and guiding prompts ensures superior solution quality and computational efficiency. From online
27

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
bin packing large-scale MILP problems, the agent consistently outperforms traditional and state-of-the-att methods, demonstrating robustness, scalability, and evolutionary refinement.
D.2. Inner and Outer Layer Prompt Initialization and Evolution
Prompt for Generating Initial Heuristic Strategies Given initial feusible solution and ables' lower hound, upper hound and coefficient in objective function. We want to improve the current solution using Large Neighborhood Scarch (LNS).
solution Mixed Integer Linear Programming (MILP) problem, with vari-
The can be solved step step by stariing from current solution and iteratively selecting subset of decision variables to relax and re-opiimize. In each step, most decision variables are fixed to their values in the current solution, and only small subsel allowed to change, You need to score all the decision variables based an the information I give you, and will chouse the decision variables with high soores neighhorhood selection. To avoid getring stuck in local optima, the choice of the subset can incorporate a degree of randomness.
First, describe your new algoratim and main sieps in one senience. The description must be inside brace. Next, imple- ment Python function named neighhooggb....oo... This function should accept input(s): initial 'cur- rent solution, 'louer.hound', 'upper_hound', "objective_oeefccieen.. _coefffciennt... The function should retur I ourput(s): neighbor_score "imitial solution', : 'current solution', 'lower. bound', "upper hound' and "abjective cuefficient are numpy arrays. "neighbor scure' is also numpy arryy that you need create manually. The i-th element the armyss corresponds the i-th decision variable. All are Numpy arrays. I don't give you 'ncighbor score' so that you noed to create it manually. The longth of the 'noigh- bor score" aray same as the length other arryss.
not give additional explanations.
(Cross) Initial Prompt for Heuristic Strategies Evolution Given initial feusible solution and current solution to a Mixed Integer Linear Programming (MIL.P) problem, with variables' lower boundd upper bound and coefficient in objestive function. We want to improve the current solution using Large Neighbochood Search (LNS).
(Cross) Initial Prompt Strategies Please help create new algurithm that has totally different form from the given ones.
Please help me create new algorithm that has totally different form from the given ones but can be motivated from them.
The uskk can be solved step-by-step by starting from the current so- lution and stenatively selecting subset decision variahles to relax and re-optimize. In each step, most decision variahles are fixed to their values in the current solution, and only small subset al- lowed change. You need to score all the decision variables based on the information I give you, and I will choose the decision vari- ables with high scores as neighborhood selection. To avoid getting stuck in local optima, the choice of the subset can incorporate a de- gree of randomness.
(Cross) Prompt for Prompt Strategies Evolu-
We are working on solving minimization problem. Our objective is leverage the capa- bilities of the Language Model (LLM) gen- erate heuristic algorithms that can elliciently tackle this problem. We have already devel- oped set of initial prompts and observed the corresponding outputs. However, improve the effectiveness of these algorithms, we need your assistance carefolly analyzing the ex- isting prompts and their results. Based on this analysis, we ask you to generate new prompts that will help achieve better outcomes in solving the minimization problem.
have existing algorithm's thought. objective function value with their codes follows: No.1 algorithm's thought, objective function value, and the corresponding code are:
No.2 algorithm's is thought, objective function value, core- sponding code are:
No.5 algorithm's 's thought, objective function value, and the corr- sponding code are:
Please help me create a new algorithm that has a totally different form from the given ones.
I have 5 existing prompts with objective func- tion value as follows:
First, describe your new algorithm and main steps in one sen- tence. The description must be inside a brace. Next, implement it in Python as lunction named seight.nggh This func- tion should accept input(si: 'initial solution,, current_xolution fower_bound" 'upper_hound', schjettiv__oefffiient _coefficennt." The func- tion should return ourput(s): "neighbor score'. 'initial solution. "current solution', "lower bound', 'upper bound' and 'objec-
No.1 prompt's lasks assigned LLM, and objective function value are: No.2 prompt's tasks assigned LLM, and objective function value are:
No.5 prompt's tasks assigned to LLM, and objective function value are:
poe_coofficeeet are numpy arrays. "ncighbor_scoo array that you need to create manually. The i-th element of the ar- rays corresonns to the i-th decision variable. All are Numpy aray.. don't give you neighhor_saove ually. The length of the neiggbor,scooe"' army is the same as the length other arays.
also a numpy
Plense help me create new prompt that has a totally different form from the given ones but can be motivated from them.
that you need create it man-
Please describe your prompt and main steps in one sentence. Do not give additional explanations.
Do not give additional explanations.
28

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
D.3. Heuristic Improvement Through Dual-layer Self-evolutionary LLM Agent
(Ot) Score:
(Ob) (883))577)
Rank decision variabies based on their penaliy contribttion and the differ mne from warren soluton, incorporsing randomness sevring.
Rank decision variables based on their objective contribttion and impuct current solution devinsion, with randonnes included in the scoring
inport:
select_ gaborh3os n, eite, value, constreint, initial solstion,
import nampy aр
def select neighhornood n. K, site, value, const int initial al utionn
current_ uaaluttionn sejective_com cowfficieettteee neighhor_pcors ap.zcros
solttion, objective_ [ojettiv__cootcicion] resgnber_ score np.serrs:n)
varinble_ditten
(F)
zoz rançztm):
varisble_sonttzaatttoo op.22r05
1hs cun [un current solutiono
for in zange
sice (11l penaicy maxi0, for J in zonge (k.111
1
Ivaivvaln (e(i]]]) curcent solutioni
(onstroinz(11)
[]1] for sango (x(A))
deviation ihs constraint [1]
ver index = sitelill31
for 1 rangerklál):
differenze sereott_colutiool
var_indox sito[1](1]
vac_indexi inttial__oluurionn
value[3]]
var_indox]
+ penalcy
cursont_co.uticc_pee (oLLttica(ver_indes
sittereace
neigabor_ (ve__indee
neighhos__core cofecrir__ooffcccott np. randen. in) return reighbor_soces
roigaber_scoee abgettvvr.occtiiioo ap.
rardon. rand
Heuristic (Olj Scores 5384,95417)
Score:
variables and difference from initial values, while also weighing their frequency of use in the constriints.
objective
This modified algecitlus ranks decision variables based on their cantri- bution to the toaal current solution's s objective function value and their satisfaction.
import numpy op got.ooooood in, site, value, const nt, init uttenn,
import humpy as def wtc.tt._noibabaaooooooooooo n, k, sita, value, consessint, solttto_.olation, solution, objective objecsiv__cottticienn costticientt aeiohhos_scors ap.zeros
curreal sttll lon, objject poe.oo/ score np.zerosin:
Freguency mp. for in zongo
zor (angaim)>
1ha sun(value [-] cuErent__olutiinn
The = sum 19aa (ule(e) current solutioni xite(s] [11 For 3 in (e)))
sitcli]
rangeik(L]])
for sange if ths constraint
deviation
constraint(i]]
tor 3 in range (k(3))
beichber_score (2t_)))))
var_inder site(i)(j)
osfective csfective_coettiiliio
www.:pceettcitttccm sitell
centribution. v5l ap.abst
11:11
constraine(11)
initial wo.uuteoooeeee
clse:
sursent sersent_solution Do.utica[var_indoo.
neighbor Baciio___coccee www.ecoooeicc. (aLe(()))))))
score [ad_ir + contrisution Frequency index]
wh.eetiveccoatticceeoo site
1M1 (conscsoint(1 1hs)
noigaber_scoge coettiiiin rp zondon, rand (ni
(Erequency ic-5)
neighhor_sooo 2oore to randon, rand(a) 0.1
wb.eattive_coettteoom recurn neighoor_ score
roturn nei geiphbar_sccre
Prompt Designed by L.M
Develop an algorithi that combines the strengths existing hearisties while introdiiig nandom peruriations to enhance exploration mini- objective function affectively.
Heuristic (Obj Score: 5374.19865)
variables
objective incorporate
adding degree of cundomnes to the scores.
Import numpy 25
select nei.sbbrhhoost., k, eite, value, constraint, initial_polutionn, currsne_sclution. neighbor_ccore (p.22ro)
cun(veise[1]11)
for 1 ia zarge [k[4]]:
var_index [4]
differense hrsp_/vvvoonlllll (constsoinE(s)) 1h6) difference
(ww.raas_oootioottaraaaaeaee pustisl_polution/yaaa
acightor_coors www.soorraaaa..oooooooooo....eee
neighbor Score += beetiiooooaficcinn ap.randonnrraddaal
return noigaber_score
29

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
D.4. Heuristic Strategies for Bin Packing Online: EoH Dual-Layer Self-Evolution LLM Agent
Heuristic Designed by EoH
Deseription
The heuristic incorporates a weighted average of the utilization ratio, dynamic adjustment, and an exponentially decaying factor, with different parameter settings to minimize the number of used bins.
Code
import numpy as np
def heuristic(item, bins):
diff bins-item remaining capacity exp ap. exp (diff) $ exponent term square root term ulti 1-diff/bins $ utilization term
sqrt = ap sqrt
comb ulti * sqrt & combination of utilization and square root
adjust np. wppreheeedd (di ff (item 3), comb + 0.8, comb + 0.3)
# hybrid adjustment term to penalize Large bins hybrid_exx exp = bins ( ((exp + 0.7) *exp)
# bybrid score based exponent tern
scores hybrid_exp
adjust
A sum of hybrid score and adjustment
return scores
Heuristic Designed by Dual-layer Self-evolution LLM Agent
Description
The new algorithm employs hybrid optimization strategy that combines nonlinear penalties for histori- cal usage, adaptive capacity scaling, and relative size assessment, facilitating a balance between local and global search for optimal hin assignment.
Code
import numpy np
def score (iten, bins]:
feasible_bins bins [bins > item]
scores = np. zeros_lkke (bins)
if (ef(sssibbl__bnnn) == 0:
return scores
$ Nonlinear capacity scaling that enhances the desire for larger spaces romaining_cappacity = feasible_bins iten
capacity_scaling mp. loglo (remaining cacllni___ppaiy remaining_capaciite ap.max weemmininnncappccllei
Relative size assessment: quadratic term comparing item size with bin capacities
rel relative_size_effer (item ** 2 feas ble_bins) 50 # Scale to
moderate impact
$ Nonlinear penalty based on historical usage counts to deter overutilization
histerical_coum np.arange (len (feasible_bins)) + | Simulating
historical usage
penalty_factor np-power (1.5, historicailcount)
Exponential
penalty for higher usage
$ Combining scores: enhanced capacity scaling, moderated size
assessment, and historical panalties
scores [bins item] capacity_scaling penaity_facte return scores
wtwpliieeeiieeeeeee
30

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
D.5. Heuristic Strategies for Traveling Salesman Problem: EoH vs. Dual-Layer Self-Evolution LLM Agent
Heuristic Designed by EoH
Description
This algorithm uses randomized approach to update the edge distance matrix by randomly selecting proportion of edges to increase their distances while uniformly rewarding smaller proportion of unused edges to encourage exploration.
Code
import mumpy as np
def update_edge eege_dietandeeeeeeeeeeeeeeeeeeee _lattedddateee,, local_opt_toarr edge_n_uaed)
N edge_distance. shapee()
upéatee__edge_éistanee Pacameters for zandonization
edga_disttnceecopy/
iacrease_facter
decrease_foctor 0.9
random_so iiron_selede seroo__seeecttoo_rttttee
0.3 percentage of edges to randomly adjust
Identicy all edges used in the local optimal tour
used_edges set
for in
start = [cccal_pp__tour(]]
local__ostt coeal__ppt_coor((E
len(Lecal_opt_tong
vaed_edgos.add (imin end), max(start, end)
Randonly select proportion of edgea to increase distance
sll_edges [(i, 31 for in zange for range (N) if 1
np. wwsnddo..aufflllllllee....
num_edgen_to_inette for edge in all_edges
int (Jen
random_celection__ret
start, [i__edppe(snn__edee____ooo inncreset_i
adge
Tf the edge is used in the local optimal cour, apply a higher increase
(start, end), naxistari, end) in used_edges:
disttacittteeeeee (start, end]
sacrease_factte
apdatted_egee_ddatteee (end, start] == increase_factor
@edated__dge_disteee distance (start, end) == dacrease_facee updated edge_ddeeee stacee (end, start) decrease_factor return updated_edop bec_e_ddeee____ee_eeeee
Heuristic Designed by Dual-layer Self-evolution LLM Agent
Description
The new algorithm refines the edge distance adjustment mechanism by incorporating acceptance heuristic dynamically explores alternative routes while gradually resetting excessively amplified distances, thus promoting diversification and improved convergence towards a global optimum.
Code
import numpy as np def serllat__ege_diieee
seige_distence jocal_opt_toure edge_a_uzed)
Creaze copy of the edge distance matrix for updases
ledee_ddosatnnoo sistance rp. (adge_distance)
Extract the number of nodea
num_nodes edge_dises surr_ddstanneehhe Caloulate the inverse frequency factor
(0]
edge
Deverse_frequency.rr
= max (edge___eded__usseee
edge_nn _uge_____edd
local optimal tour for in range (locs) _pt__torr)
Updaze edge distance based
Get the current and next node the local optimal tour curvent_nede locsl_opt_touz] next, noxe_rode Lacal_apt_taurll + 11 & Janiloca" [oocal_opppttt Lopt_ton")
Loooal_opt_teee the edge weight
Apply the inverse Irequency
sadated_edge_ddsttaeee (ww.eenteeerrreeeeeeccce next__ode;; k= Liveree__rruueecy_aacttot
curreat_rode, next_node]
updated_engee sird_edge_dise wtwpeeeeeddsstcclllloeeeee maxx__ndde ourrent_node] as corerra_frouueoy__too factor
next_node, ouzrens_node]
return updates_edge_diittan
31

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
D.6. Evolutionary Path of the Dual-Layer Self-Evolution LLM Agent
Heuristic (Ohj Score: 5400.81176
Prosspts (Cross) Pletse help me create new algorichm that has a Intally different form from the given
The algorahm ranks decasoo variables based on their impast on the objective function and how they relate to the violated construins, incorporating degree of randommess.
(Cross) Plense help me create new algorichm fatilly different
Lmport numpy a5 up de select coaet__siehhochhade
the given ones motivated from
k, size, valce, constraint, instial_ecietion cutrons_polution, casectiv__cofficcionni neigabor__caree viotated_conatzalnnc
(n)00
(Vasiation)
creating
algorithm that has a different form but can be modified version of the algorihmm provided.
for 1 in range
ihs cun/value [5]
corron__ooourionnssttttill
rance (k[4])]
if ihs csactraint(E]] [1]:
(Vatation) Please idestify the main algorithm paramesers and mosist me in creating new algorithm different pammeter settings score function provided.
violated sallatdd_consssatee con.tsranttt 1
for ceiohbos_ccorojottttle
(k(4)):
ob jeee:vo_oossfiiiinn (s [11
IE violated_constzalnnz 0:
neighhos_sse secors /- tooosccdooosstoooe
candomess np.randon.candle neighber scare -= randennass paare returr. nsighhor_scoze
0.1
Current Prumpis
(Cross) Devetop modidid heurstic algorithm that utilizes a hybrid approach, combuning elements of simulated annealing and genetie algorithms, optimize the given minimization problem.
Heuristic (Ohj Score: 1374519865)
Kank variables based contribation objective function and incorporate absolute difference from initial sohnion while adding degree of randomeess the secces.
(Cros) Design modiffeed heuristic algorithm for the misimization problem by incorperating elements of simulated annealing with unique cooling scholule.
Code
(Vatiation) Please idestify the main algorithm paramesers and
Lepost numpy ap
creating
dez seisct_nsichbechood n, &, site, valce, constrsint, in ion macren._uulutinn iun, cajjetive neighber_pcaet
purmmeter settigss
of the score function provided.
fox 1 in range (m)
(Varlation) Develop an algocitim that the strengths of existing houristies while introducing random perurbations cslionce exploration minimize the objective function more effectively.
1ha = wun [vallvalllle ual [1:T] [J] y patemmm
for
1 in rance (k[11))
for :
vas_index sitw[i][j]
differanca ap.abs (ooreent_ooouriootaarraa
initial_ woll:innnvee: index])
nwighbor_scoee
(sonstraint
differonce
neighber mcore wwwjectivew.c...o..o... www.tiio_ooeffiiieee.. app.randon rand (n)
zeturn. ne neighbos_scoss
Final Prompts
(Cris) Develop hybrid hetristic algorithes the minimization problesa that couthines gesetic algoritims with tabu seazch to enhance local capabilities while maintaining diversity the solution populatioos
Houristic (Ohj Score: 5373,34904)
Develop co-evolurinnary heuristic appenoch integmats genetic algorithms Incal search techniques eahance convergaace speed and minimize objective function spacified problem.
(Cruss) Develop evollluutoouryy heurisic appreach that integrates genetic algorilhms with local search toche tocheiques sques cnhince convergoee speed and minimize the objective function for the specilied problem.
Code
Lapost aunpy np
de sulect_ hww..o.hhihhhhhhhooooooooooo (n, is, k, wilny value, consticaint aoorint_ cafseciveecoatticiinnt gighho...oorrrrrr (prozeos
optimization strategy integrates genetic algoricmms dynamic programming principles to eahance the seurch for optimal solations, focusing adaptive mutation effectively minimize the objestive function value.
(Varlatoo)) Design
i in range (n))
tha e sun (valuvva U1I w cozrens_poturionsstttttit
for
(k (k11))
for zange [k]]);
var_indox aite[4][1]
(Variation) Design
optimization
di difference np-abs (ourrent sor innfver_indes)
fraewwor integrates particle swarm oprimisation with genetic algorithns, focnsing on adaptive mutation sinttgiis to cohance convengence speed minimize objective function value.
(constraint::)) tha) sandor justment ip..aadon. sard
adept tvv iotatioon rate np.eliging. Inp. iobjective soeff soeffigient 0.1, 1.0)
neighterr_coee ddaptive_nnd iww_utaaiiooaaaee randon_ad jddittddnnnnnn justimett return neighbor score
32

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
D.7. Evolutionary Result of the Dual-Layer Self-Evolution LLM Agent
D.7.1. EVOLUTIONARY RESULT SET COVERING PROBLEM
Heurtstic Score: 3339.9339)
This algorifhm computes scxess the penalty incurred by variable deviating from the cuncnt solinion evaluntes the impact constraint sutisfaction.
Code
nanpy up
&, site, valce, conatraint, initial cucrent_Rollttonr jact (oeciinn)))) neigaber_pcare ap.zeros (G)
Eus in range (n)
ala_value [1]]]
ourren__oolcionssstetllll for (k(41))
1 sangeik[[]]]:
vatiable index wit=[i][]]
ie ihs_valus constraint
penalty
constraint[s]
conisilution penally valuelill [i]]]]
seoothoss_corr_jaee [vartable_naad +- contribation
elaet
contribution val
neighbor__core [variable_
contribation
costs "g.aba (ourrent ponurrett_pollt solut ion prisiel_xolutionn x jobject iee_coofflcceen
with warrssaallldd ignore", Lnvalide ignor=");
neighbos_szoss
np.divide (asighbos_score,
kheramcosta
neighber score op-nin tniggherr_sssst neighber_seore /- upenax meighber_store) if apunes (ow (osnaxxtwigioorscooo 1- 0 wlaw rard factor rp.rendon, randit)) 0,1 neighber jusre Factrr cutuen neighhos_acore
Final Prompts
(Cross) Please help me create new algocithm that has totally differeut foom from the given ones.
(Crees) Please help me creale new alporithm that has totally different form from the given ones but can be motivated frum them.
(Variation) Please assist me in creaking new algorithm that different form but can be a modified version the algorithm provide..
(Variation) Plense identify the algoriffum paramoters
creating new algorithm that different pammeter seftings function provided.
D.7.2. EVOLUTIONARY RESULT OF MAXIMUM INDEPENDENT SET PROBLEM
Heuristic (Ohj Score: -(634,663))
This new heuristic apprucch combines the principles of simulated anmealing with the adspiiee scoring of decision variables based their contributions violated constraints while explonation
rating randomess
space.
Code
nungy op
select_neighhon tet._nneghbocchoddm R, site, value, constreint, instial_es.utien, current_poiittin,, sejecrive_ccetticientti
neig geir score xe-zeros
purrent_abjaativee
ap.dot lcurrort_colution, oejecsive_costticcinnt)
variable_ cow.etttttrtteeeeeec....
range(m):
curcon_ooducconnsstttlll.. for in (k])) it value constraint
ihs_value cun(vaisc[3]131
sange(x(1))
var_index eits|s]]!]
varias.e contribations Var index] (v ieurrent_ oclutiin carr_airrddr 11)
for index in zange in]:
[index] htwaable_corrribttccniiisss neighbor indexi improvement ceerrent_ccluttonii 0.5)
temperature ap. rendon, uniform(C.., 1.01
cardomess rp..ranon..unioorr (-termarattro temperature, sizemn!
neiqaber_scare
ncighbos_scoze
Final Prompls
(Cross) Develop novel bybrid algorithm that combines local seurch and simulased annealing techniques to explore the solution space and minimize the objective finction more effectively.
(Cress) Desige novel optimization algoeitum inspired by the existing methods, focusing oa adaptive partmeter taiing enhance convergence toward better solutioos.
(Variation) Design novel hessistic appmoch inspired by the principles of simulated anncaling to optimize the following problem pommeters.
(Nariation) Please identify the main algocithm parameters and assist me in creating new algorithm that bas different panmetter settings of the score funccion provided.
33

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
D.7.3. EVOLUTIONARY RESULT OF MIXED INTEGER KNAPSACK SET PROBLEM
Heurlsdic Score: 261129999)
This algorithm onhances diversity solution search process statogically selecting decision variables based on their objective contributions coustraint interactions, while incorporating a degres of random exploration.
Code
Lmport nanpy as ap
dec select wecocct_nnhhhheeeeee www.ghhhhhhheeeoooooooooooooooee (n, n, & site, value, constreiat, instiol_rolutien, cuerent_solutior, sejstire_ocatticcont) neighber accre ap.zeros (a)
contriiuutio__sooee
cootiva_coetticient cursent_scictioon
neighters_asee
conte aoreausres
for in (n)
its_value e sun[value[4113]
cercon__oolccion/citttllll for in rango
if Hha_value con)traini(t):
for var_index sits[A]]!]]
(x[4))
penalty (llis_value constraint[[]] / (1, op.sun (2]]
aciathors_ccra [va__iree]__ penaity value]i] np.xandon, co.ramion..uiforro (D. 1.2)
local pwappaccccctttrree nei neigiber score - (snittai__olstton ousreit_polatton)
Fac.oe
candomeess (o.raadonnsaad(a) 0.1
neighber jusre ap.eax www.igheor__cooooooo
neighbor scoze / ap.naxttaecchoor_cooo
zwburn ne wwwighhor_aasur
Final Prompts
(Cross) Design hyhrl beuristic algorithm that combines clements generic algorithms amncaling to explore solation space efficiently
(Cress) Develop multi-phase heuristic optimization strategy integrates particle optimization with scarch dysamically adapt parsmeters and enhance convergence rates.
(Variation) Develop an algurithm that incorpraates novel optimizztion strategy, diverging from previous approaches, enhance objective function's outcume by exploring pormeeter tuning tochniques.
(Varation) Please idomity the main algoiitum parameters and ieui me creating new algorithm that differest pammeter settings score function provided.
E. Convergence Analysis of LLM-LNS
E.1. Evolutionary Progress in Combinatorial Optimisation Problem
Across both two combinatorial optimization problems Online Bin Packing and Traveling Salesman Problem, LLM-LNS consistently shows superior convergence and final solution quality compared to EOH.
In the Online Bin Packing problem shown in Figure 5, LLM-LNS shows better convergence behavior from the early stages. As the generations progress, LLM-LNS steadily improves and consistently outperforms EOH. The reduced variance in later generations highlights the stability of the LLM-LNS approach, which efficiently balances exploration and exploitation. Its dual-layer structure allows it to thoroughly explore the solution space, avoiding premature convergence and reaching a higher overall objective score. In contrast, EOH exhibits larger fluctuations and fails to achieve the same level of performance, indicating its limitations in maintaining robust progress during the evolutionary process.
In the Traveling Salesman Problem shown in Figure 6, although LLM-LNS starts with a less favorable initial population compared EOH, it quickly demonstrates its advantage. Initially, EOH performs better, but it stagnates after the first generations, showing little improvement afterward. Meanwhile, LLM-LNS continues to refine its solutions and steadily decreases the objective score. This indicates that the dual-layer structure of LLM-LNS effectively prevents it from getting trapped in local optima, maintaining high level of exploration even in later generations. By the end of the evolutionary process, LLM-LNS surpasses EOH, achieving better overall results.
In both problems, LLM-LNS's ability to maintain diversity early in the process, combined with its strong convergence in later stages, gives it a clear advantage over BOH. The dual-layer evolutionary strategy ensures that LLM-LNS avoids stagnation, allowing for continuous improvement and ultimately leading to superior performance in solving combinatorial optimization problems.
E.2. Convergence Analysis of Generations
In the Online Bin Packing Problem, we conducted 100 generations of iterative training using the proposed dual-layer strategy. Figure 7 shows the convergence trends for both the training and testing scores over these 100 generations. The results
34

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
0.955
316
Pertemarce (6.00dra)
Perfermnnee (66 adheel
934
990
0.955
2.0
7.3
10.0
12.5
15.0
175
2000
23
10
20.0
22.3
15.
17.
20.
Number goncrators
Numbero gancuiions
Figure 5. Evolutionary Progress of Hcuristic Strategies in Online Bin Packing
Figure Evolutionary Progress of Heuristic Strategies in Travel- ing Salesman Problem
0.990
Peffrmance lobjective)
0.900
0.975
0.965
0.960
Train Test score
20
40
60
100
Number generations
Figure 7. Convergence of Training and Testing Scores in 100-Generation of Online Bin Packing Prohlem.
provide interesting insights into the behavior of our model during the evolutionary process, particularly in terms of how the training and testing losses evolve differently.
The training loss demonstrates clear and consistent downward trend throughout the generations. Initially, the training score starts relatively high, but quickly drops within the first few generations. This rapid initial improvement indicates that evolutionary algorithm is highly effective at optimizing the objective function within the training set. As the generations progress, the training score continues decrease, eventually converging to very low value. This steady decline suggests that the model is successfully adapting to the problem, continually refining its population and reducing the training objective. The absence of significant fluctuations in later generations implies that the model has reached stable state, effectively minimizing the training loss with little variance.
On the other hand, the testing loss follows a somewhat different pattern. Initially, we observe sharp decline in the testing score, which mirrors the behavior of the training score. However, after this initial drop. the testing score does not continue to improve as steadily as the training score. Instead, stabilizes around a certain value and begins exhibit small fluctuations.
35

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Table Comparison of objective values large-scale MILP instances across different methods using SCTP as optimizer. For each instance, the best-pes perforrmig objective value is highlighted in bold. The symbol indicates that the method was unable to generate samples for any instance within 30,000 seconds, while * indicates that the GNN&GBDT framework could not solve MILP problem.
SC₁
SC2
MVC1
MVCg
MIS;
MISa
MIKS,
MIKSa
Randorn- LNS
161642
171655.6
27049.6
277255.3
22892.9
222076.8
691.7
6870.1
ACP
17743.4
192791.2
27432.9
281862.4
23058.0
216008.8
29879.2
7913.5
CL-LNS
31285.0
15000.0
Gurobi
17934.3
320240.4
28151.
283555.8
21789.0
216591.3
32960.
329642.4
SCIP
25191.2
385708.4
31275.4
491042.9
18649.9
9104.3
29974.7
168289.9
GNN&GBDT
16728.8
261174.0
27107.9
271777.2
22795.7
2
LighI-MLLPOPT
16147.2
166756.0
26956.8
269771.3
22963.6
230278.1
36125,5
3574K3.8
15950.2
161732.8
26763.4
268825.5
23137.19
230682.8
36147.7
350468.7
This behavior suggests that while the model is able to generalize to degree, it encounters more variability in the testing data compared to the training data. These fluctuations could be attributed to the inherent complexity or diversity of the unseen test instances, which the model has not been directly optimized for.
This phenomenon is reminiscent of the behavior observed during neural network training, where the training loss continues to decrease as the model becomes more specialized in fitting the training data, while the testing loss reaches plateau and may exhibit some fluctuations. In this case, the testing loss reflects the model's ability to generalize beyond the training set. The fact that the testing score does not continue to decrease beyond certain point suggests that the model may have reached its limit in terms of generalization, possibly due to overfitting to the training data. However, the steady fluctuations in the testing score indicate that the model remains adaptable and does not suffer from severe overfitting, as there is no significant increase in the testing loss.
Overall, the divergence between the training and testing scores in later generations highlights the trade-off between optimization and generalization. While the dual-layer evolutionary strategy is highly effective at optimizing the training set, it must also balance the need for generalization to unseen data. The oscillation of the testing score around stable value suggests that the model is reasonably robust but may benefit from additional techniques to further enhance its generalization performance, such as regularization or early stopping strategies in future iterations.
In summary, the convergence analysis of the 100-generation experiment reveals that while the training loss continues to decrease, the testing loss stabilizes with slight fluctuations. This behavior is indicative of a model that has successfully optimized for the training data while maintaining a reasonable level of generalization, akin patterns observed in neural network training processes.
F. Supplementary Experiments for LLM-LNS on Large-Scale MILP Problems
F.1. Performance of LLM-LNS Using SCIP as the Subsolver
In this supplementary set of experiments, we further evaluate the performance of LLM-LNS by incorporating SCIP as the subsolver for large-scale MILP problems. The results, summarized in Table 7, provide a comprehensive comparison across various methods using SCIP, offering deeper insights into the robustness and adaptability of LLM-LNS when faced with different solver strategies.
As seen in the results, LLM-LNS continues to demonstrate superior performance across most instances, consistently outperforming traditional LNS-based methods, learning baased frameworks such as GNN&GBDT, and even advanced solvers like Gurobi and SCIP. The highlighted bold values indicate that L.M-LNSS achieves the best objective values in the majority of cases, reinforcing its scalability and effectiveness in large-scale MILP problems.
However, an interesting observation arises in the MIKS instances, where Light-MILPopt outperforms LLM-LNS. This can be attributed to the unique challenges posed by MIKS in large-scale settings. Specifically, MIKS requires significantly more resources for neighborhood searches as the problem size increases, compared smaller-scale instances. SCIP, as an optimizer, employs a different strategy for solving MIKS, which likely influences the performance of LLM-LNS when scaling to larger instances. In smaller-scale problems, LLM-LNS may have learned more aggressive strategies that are effective in those scenarios, but these strategies may lead to timeout issues in larger instances due to the increased computational complexity and extended iteration times required for SCIP. As a result, the overall improvement in performance is limited in these larger MIKS problems.
36

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Table Comparison of standard deviation values on large-scale MIL. instances across different methods using Gurohi optimizer.
SC₁
SC₂
MVC,
MVC,
MIS,
MIS;
MIKS
MIKS,
Randon-LNS
37.5
258.1
68.4
243.0
72.1
243.0
98.2
584,0
ACP
38.4
1039.3
71.6
403.5
60.3
928.8
118.2
649.2
CL-LNS
617.7
277.5
Gumbhi
28.8
143.4
77.2
287.3
48.8
147.5
69.0
225.7
SCIP
13823.6
298211.7
107.3
262.0
57.5
85.8
73.2
242313.7
GNN&GRDT
360.1
3800.4
93.8
950.4
119.3
4738.8
Light DIgH-MILPOPTT
1.0
145.7
79.4
209.4
52.1
133.1
41.7
272.5
LLM-LNS(OURS)
17.7
144.2
79.7
198.1
55.2
147.6
70.2
170.4
Table Comparison of standard deviation values large-scale MILP instances across different methods using SCIP optimizer.
SC1
SC2
MVC₁
MVC₂
MIS;
MiS₂
MIKS,
MIKS;
Random-LNN LNS
18.8
250.3
79.0
234.8
72.1
401.7
18.1
36.2
ACP
30.8
6338,3
77.2
217.6
60.3
946.4
1829.7
943.8
CL-LNS
617.7
277.5
Gurobi
28.8
143.4
77.2
287.3
48.8
147.5
69.0
225.7
SCIP
13823.6
298211.7
107.3
262.0
57.5
242313.7
GNN UNN&GBDT
51.4
5587.6
91.4
474.0
80.0
660.4
Light MOPP
37.7
693.4
77.3
216.9
$1.6
151.7
80.0
1045.8
LLM-LNS(OUS)
20.4
T69.5
82.6
188.7
75.9
1197.3
Despite these challenges, LLM-LNS still exhibits competitive performance in MIKS, managing to outperform many other methods, including Gurobi and traditional LNS strategies. The occasional time-out or reduced efficiency in MIKS does not overshadow the fact that LLM-LNS remains robust and scalable solution across a wide range of large-scale MILP problems.
In conclusion, these supplementary experiments highlight the adaptability and robustness of LLM-LNS when using different subsolvers, including SCIP. Although challenges remain in specific problem instances like MIKS, LLM-LNS consistently delivers superior performance across most problem types, demonstrating its ability to generalize across solvers and problem scales. The results reinforce the notion that LLM-LNS effectively bridges the gap between traditional solvers and learning- based methods, offering a scalable solution for large-scale combinatorial optimization problems.
F.2. Comparison of Standard Deviation Values
The comparison of standard deviation (SD) values across different methods using both Gurobi and SCIP as sub-optimizers reveals several key insights into the stability of various approaches when solving large-scale MILP problems. Standard deviation reflects the consistency of the solutions; lower values indicate that the method is more stable and produces less variation in different runs.
As shown in Table 8, for the experiments using Gurobi, LLM-LNS consistently demonstrates low standard deviation values across most instances, indicating that it not only achieves superior objective values but does so with high stability. For example, in SC₁, MVC2, and MIKS,, LLM-LNS has SD values of 17.7, 198.1, and 170.4, respectively, which are comparable to or lower than other methods. Light-MILPopt also shows excellent stability in SC₁ and MIKS,, with SD values of 1.0 and 41.7, respectively, although its performance fluctuates more in other instances. In contrast, Random-LNs and ACP exhibit higher variability, especially in SC₂ and MIKS,, where ACP's SD reaches as high as 1039.3 and 649.2, respectively, suggesting lack of robustness in these instances. Gurobi itself also shows moderate consistency, while methods like CL-LNS fail to generate results for certain instances, indicating poor scalability for large problems.
As shown in Table 9, when SCIP is used as the optimizer, the trends remain somewhat similar. LLM-LNS continues to show stable performance, particularly in SC₁ and MVC2, with SD values of 20.4 and 188.7, respectively. However, SCIP itself exhibits extremely high variability in some instances, particularly in SC₂ and MIKS with SD values exceeding 298,000 and 242,000, respectively, which suggests that SCIP struggles with certain large-scale MILPs. This instability in SCIP could be due its aggressive strategies or solver configurations being less suited to these specific problem instances. Light-MILPon again demonstrates relatively stable performance in most instances, although its SD increases significantly in some cases, such as MIKS,, GNN&GBIT and ACP also show considerable fluctuations, with ACP having an SD of 6338.3 3 in SC2, further highlighting its instability in large-scale settings.
In summary, LLM-LNS not only consistently outperforms other methods in terms of objective values but also maintains strong stability across a wide range of instances, particularly when compared to methods like Random-LNS, ACP, and SCIP.
37

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Table 10. Comparison of error bar on large-scale MILP instances across different methods using Gurobi optimizer.
SC₁
SC₂
MVC,
MVC,
MIS;
MIKS|
MIKS,
Randon-LNS
65.4
318.3
142.1
350.8
104.4
333,6
158.9
808.8
ACP
56.8
1787.2
120.6
$74.8
83.6
1233.0
173.7
742.7
CL-LNS
892.6
406.3
Gumbhi
39.7
252.7
119.6
349.0
64.7
183.1
103.8
319.7
SCIP
25238.2
533457.2
165.2
402.1
96.9
103.6
94.6
433463.8
GNN&GRDT
511.3
5504.8
148.7
1522.6
160.1
7887.9
Light- DIgh-M
1.4
206.4
121.6
289.8
78.8
216.6
63.3
420.1
LLM-LNS(OURS)
27.9
1879
1254
289.8
82.2
199.3
111.7
259.2
Table 11. Comparison of error bar on large-scale MILP instances across different methods using SCIP as optimizer.
SC₁
SCa
MVC,
MVC₂
MIS;
MIS;
MIKS;
MIKS:
Random-LNS 33.2
362.1
123.3
368.2
104.4
531.3
26.1
51.5
ACP
46.1
10845.3
106.0
324.1
83.6
1371.4
3253.2
1055.6
CL-LNS
892.6
406.3
Gurohi
39.7
119.6
349.0
64.7
103.8
SCTP
25238.2
533457.2
165.2
402.1
96.9
103.6
94.6
433463.8
GNN&GBDT
72.6
7349.2
147.2
678.8
100.4
1076.6
Light- POPT
66.6
1223,3
118.5
305.6
79.1
239.4
124.2
1473.9
LLM-LNSS (NN((
31.7
251.2
131.9
266.7
68.9
94.7
105.9
1868.3
This robustness makes LLLM-LNS a strong candidate for solving large-scale MILP problems effectively and consistently.
F33 Comparison of Error Bar
The eтror bar comparison across different methods using Gurobi and SCIP as optimizers provides insights into the variability and confidence in solutions across large-scale MILP instances. Error bars quantify the uncertainty or inconsistency in the results, with smaller values indicating more reliable and consistent performance.
As shown in Table 10, for methods using Gurobi, LLM-LNS again demonstrates strong reliability with relatively small error bars across most instances. For example, in SC1, MVC2, and MIKS,, LLMM-NSS has error bars of 27.9, 289.8, and 259.2, respectively. These values are noticeably smaller than those for methods like Random-LNS and ACP, which exhibit much larger error bars, reflecting greater instability. Light-MILPopt also shows excellent performance with particularly low error bars in SC₁ (1.4) and MIKS| (63.3), but its error increases significantly in some other instances. Notably, SCIP exhibits extremely large error bars in several instances, such as SC₂ and MIKS2, where the error bars exceed 533,000 and 433,000, respectively, indicating significant inconsistency its performance on these large-scale problems. GNN&GBDT also shows high error bars, suggesting that its performance is less reliable across different runs.
As shown in Table 11, when using SCIP the optimizer, LLM-LNS continues demonstrate relatively low error bars, particularly in SC1, MVC,, and MIKS,, where the values are 31.7, 266.7, and 105.9, respectively. These results are significantly more stable compared to methods like ACP and GNN&GBDT, which show very high error bars in instances like SC₂ (error bar of 10845.3 for ACP) and MIKS2. SCIP itself again shows extremely high error bars for instances such as SC₂ and MIKS further highlighting its instability in handling large-scale problems. Light-MILPopt performs well in some instances but also shows considerable variation in others, with error bars as high as 1473.9 in MIKS2.
Overall, LLM-LNS consistently demonstrates lower error bars across both optimizers, Gurobi and SCIP, indicating that it provides more reliable and consistent solutions for large-scale MILP problems. This makes it strong candidate for scenarios where both solution quality and stability are critical.
E.4. Convergence Analysis
In this section, we analyze the convergence performance of our proposed approach, our proposed LLM-LNS, in comparison to several baseline methods for solving large-scale MILP problems, including Random-LNS, ACP, Gurobi, GNN&GBDT, and PILPT The experimental results are shown in Figures 8 through 11, which include instances of four different problem types: Set Covering (SC), Maximum Vertex Covering (MVC), Independent Set (IS), and Mixed Integer Knapsack Set (MIKS). We evaluate both medium- scale and large-scale instances using two solvers as sub-optimizer, Gurobi and SCIP.
The analysis of the convergence curves reveals several important observations:
38

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Fauenii Ar
Time
Time
Figure 8. Time-objective value graphs of medium-scale problems using Gurobi: SC1, MVC1, 18, and MIKS
Goed
Figure 9. Time-objective value graphs of large-scale problems using Gurobi: SC2, MVC2, 18,, and MIKS
Ruton
Time
Figure 10. objectvee value graphs of medium-scaat problems using SCIP: SC,, MVC,, 18,, and MIKS
linc
Figure 11. Time-objes obje-obeeetive value graphs large-scale problems using SCIP: SC2, MVC2, 18,, and MIKS
For nearly all problem instances, the LLM-LNS approach demonstrates a significantly faster initial convergence compared to the baseline methods. The objective value drops sharply within the first few time steps, indicating that our method can quickly identify high-quality solutions. In contrast, methods like Random-I.NS and ACP exhibit slower initial convergence, requiring more time achieve similar reductions in the objective value.
Faster Initial Convergence:
Superior Final Objective Value: Across both medium- and large-scale problem instances, our proposed LLM-LNS consistently achieves lower final objective values compared to the other methods. This is particularly evident in the large-scale instances (e.g., SC2, MVC2, 18,, and MIKS2), where the superiority of our method becomes more pronounced. While methods such as Random-LNS and ACP plateau early, often with suboptimal solutions, our proposed LLM-LNS continues to improve the solution even after other methods have stagnated.
Stable Convergence Behavior:
The convergence curves of our proposed LLM-LNS exhibit smooth and gradual decreases the objective value, indicating stable optimization behavior. In contrast, some the baseline methods,
39

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Table 12. Performance comparison of L.M--NNS with additional LNS methods MIL. tasks. Results are reported as objective values
(lower is better).
Method
SC1
SC2
MVC1
MVC2
MIS
MIS;
MIKS:
MIKS;
Kandom-LNS
16140.6
169417.5
27031.4
276467.3
22892.9
223748.6
36011.0
351964.2
ACP
17672.1
18235944
26877.2
274013.3
23058.0
226498.2
34190.8
332235.6
Leust Integral
22825.3
228188.0
29818.0
306567.1
20106.9
195782.2
27196.9
241663.4
Mitt--nttggal
50818.2
519685.5
35340.5
327742.4
14584.4
157686.5
31235.3
314621.6
RINS
26116.2
261176.3
26851.3
306215.6
23069.7
201178.1
30049.1
299953.4
(Ours)
15802.7
138878.9
26725.3
268033.7
23169.3
231636.9
36479.8
3637499.5
especially Random-LNS and GNN&GBDT, show more erratic convergence patterns, characterized by large and sudden jumps in the objective value. This suggests that our method is more robust and avoids the instability that can arise in heuristic-based search strategies.
Scalability; The performance gap between our proposed LLM-LNS and the baseline methods becomes even more pronounced in lcrge-scale problem instances. For example, in the large-scale MIKS² and SC₂ instances, our proposed LLM-LNS outperforms all other methods by a significant margin, converging to a much lower objective value within a shorter time frame. This demonstrates the scalability of our method, as remains effective even as the problem size increases, whereas the performance of other methods, such as Light-MILPOPT and ACP, degrades considerably.
When compared to the exact solver Gurobi, our proposed LLM-LNS shows comparable even superior performance, partieularly in terms of convergence speed. While Gurobi tends to find solutions that improve gradually over time, our proposed LLM-LNS reaches competitive solutions much faster, which is crucial in time-constrained scenarios. This highlights the practical advantage of our method in scenarios where computational resources or time are limited.
Comparison with Exact Solvers:
In summary, the experimental results demonstrate that LLM-LNS has clear advantages in terms of convergence speed, final solution quality, and robustness compared to both heuristic-basee and exact optimization methods. Our approach particularly well-suited for large-scale MILP problems, where it consistently outperforms the baseline methods by a significant margin.
F.5. Baseline Comparisons with Additional LNS Methods
To evaluate the effectiveness of the proposed LLM-LLSS framework, we conducted comprehensive comparisons with several LNS methods that utilize different heuristic scoring functions. Specifically, we incorporated Least-Integral (Nair et al., 2020), Most-Integral (Berthold, 2006), and RINS (Danna et al., 2005), which are classical scoring functions commonly used in LNS frameworks, alongside the ttate-of-the-art methods ACP (Ye et al., 2023a) and classic method Random-LNS (Song et al., 2020).
The results, summarized in Table 12, demonstrate that our proposed LLM-LNS consistently outperforms all baseline methods across a variety of MILP tasks, including Set Covering (SC), Maximum Vertex Cover (MVC), Maximum Independent Set (MIS), and Mixed Integer Knapsack Set (MIKS). This advantage highlights the superior ability of LLM-LNS balance exploration diversity and solution convergence.
From the results in Table 12, several key observations can be made. Among the classical LNS methods, RINS generally achieves better results compared to Least-Integral and Most-Integral. as it leverages neighborhood- improvements combined with partial solutions. However, these methods still fall significantly behind ACP, Random-LNS, and our proposed LLM-LNS, particularly on larger problem instances such as SC₂, MVC2, and MIKS,. For example, on the SC₂ problem, RINS achieves an objective value of 261176.3, compared to 158878.9 for LLM-LNS, highlighting the limitations of traditional scoring functions in handling large-scale MILP problems.
ACP and Random-LNS perform much better than the classical scoring- based methods due their adaptiveness and ability to leverage heuristic diversity. However, even these state-of-the-art baselines are consistently outperformed by LLM-LNS across all tasks. For instance:
On the SC₁ problem, LLM-LNS achieves an objective value of 15802.7, compared to 16140.6 for Random-LL -LNS and 17672.1 for ACP.
40

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
On the 2 problem, LLM-LNS achieves 231636.9, compared to 223748.6 for Random-LNS and 226498.2 for ACP.
The clear performance advantage of L.LM--NS can be attributed to its dual-layer architecture, which combines prompt evolution and heuristic strategy optimization to balance search diversity and convergence. The outer layer generates diverse prompts that broaden the search space, avoiding premature convergence to suboptimal solutions. Meanwhile, the inner layer refines heuristic strategies and accelerates convergence by leveraging the evolved prompts. This interaction ensures that LLM-LNS adapts effectively to different problem scales and complexities.
Moreover, the results highlight the scalability of LLM-LNS, While ACP and Random-LNS demonstrate reasonable performance smaller tasks, their effectiveness diminishes the problem size increases. In contrast, LLM-LNS maintains its performance advantage across both small-scale (e.g., SC1) and large-scale (e.g., SC2) tasks, showcasing its robustness and adaptability. This scalability is directly enabled by the dynamic feedback loop between the two layers, ensuring continuous refinement of both the search space (via prompt evolution) and the solution strategies (via heuristic evolution).
In summary, the experimental results validate the effectiveness of LLM-LNS over both classical and state-of-the-art LNS baselines. Its dual- dual-layer mechanism provides superior generalization and adaptability, making a powerful framework for solving diverse and large-scale MILP problems.
G. Ablation Study of the Dual-Layer Self-evolutionary LLM Agent
This section presents the results of the ablation study conducted to analyze the contributions the dual-layer framework components: Prompt Evolution (outer layer) and Directional Evolution (inner layer). The study evaluates the effects of removing isolating each component on the overall performance of the framework. Specifically, we compare the following variations:
Base (EOH): The baseline Evolution of Heuristic (EOH) method without any modifications.
Base + Dual Layer: The EOH method with the dual-layer structure (Prompt Evolution in the outer layer).
Base + Differential: The EOH method with the Directional Evolution mechanism (inner layer).
Ours:
The complete dual-layer framework incorporating both Prompt Evolution and Directional Evolution.
We evaluate these variations on datasets of different scales to observe their impact on both small-scale and large-scale prob- lems. The datasets include 1k C100, 5k C100, 10k C100, 1k C500, 5k C500, and 10k C500, representing combinatorial optimization instances varying sizes. The results are summarized in Table 13.
Key Observations:
Impact of Prompt Evolution: Adding the dual-layer structure (Base Dual Layer) significantly improves performance large-scale problems, the outer layer enhances the diversity of the search process through prompt optimization. This is particularly evident in the 10k-C500 dataset, where the eπror rate decreases from 0.97% % (Base) to 0.39% %.
Impact of Directional Evolution: Incorporating the differential evolution mechanism (Base Differential) improves performance on small-scale problems by accelerating convergence through more effective crossover and mutation strategies. For example, on the 1k C100 dataset, the eтror rate decreases from 4.48 % (Base) to 2.64%.
The complete dual-layer framework (Ours) achieves the most balanced improvements across datasets, particularly for larger-scale problems. However, on small-scale datasets like 1k C100, the additional exploration introduced by Prompt Evolution can slightly increase the error rate compared to Base + Differential (from 2.64 % to 3.58%)
Synergy of Both Components:
These results validate the complementary roles Prompt Evolution and Directional Evolution enhancing both diversity and convergence, demonstrating the effectiveness of the dual-layer framework for solving combinatorial optimization problems of varying scales.

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
Table 13. Ablation study results on various datasets. The table compares the baseline (FOH), the addition of the dual-layer structure
(Prompt Evolution, outer layer), the addition of the differential evolution mechanism (Directional Evolution, inner layer), and the complete method (Ours). The best results for each dataset are highlighted in bold.
1k_C100
5k_C100
10k_C100
[k,C500
5k,C500
10k_C500
Base (EOII)
4.48%
0.88%
0.83%
4.32%
1,06%
0.97%
Base + Dual Layer
3.78%
0.93%
0.40%
3.91%
0.92%
0.39%
Base Differential
0.69%
2.54%
0.4%%
Ours
3.58%
0.85%
0.41%
3.67%
0.82%
0.42%
Table 14. Stability evaluation of multiple
Bin Packing tasks. Results reported as error rates (%)
Method
1R,C100
5K,C100
10L_C100
TK_C500
5k,C500
10K_C500
Avg
EOH Kun
4,48%
0.88%
0.83%
4.32%
1.06%
0.97%
2.09%
EOH Run 2
7.56%
3,33%
2.62%
7.22%
3.19%
2.50%
4.07%
BOH Run
4.18%
3.24%
3.35%
3.79%
3.12%
3.21%
3.48%
BOH Ave
5.41%
2.48%
2,27%
5.11%
2.46%
2.23%
3.33%
Ours Run
3.58%
0A1%%
3.675
0.82%
0.42%
I.63%
Ours Run 2
2.69%
0.86%
0.54%
2.54%
0.87%
0.52%
1.34%
Ours Run 3
2.64%
0.94%
0.6918
2,54%
0.94%
0.70%
1.41%
Ours Avg
2.97%
0.88%
0.58%
2.92%
0.88%1
0.55%
1.46%1
Table 15. Impact of population size on Bin Packing tasks,
Results are reported as error rates (%).
Method
Ik C100
5k C100
Iök C100
Ik C500
5k C500
10k
C500
Avg
EOH (20)
4.48%
0.88%
0.83%
4.32%
1.06%
2.09%
Ours (4)
3.23%
0.80%
0.43%
3.96%
1.27%
0.89%
1.76%1
Ours (20)
3.58%
0.41%
3.67%
0.82%
0.42%
1.63%
H. Additional Validation Experiments
H.1. Stability Evaluation of Multiple Runs
To evaluate the stability and consistency of our proposed method, we conducted repeated experiments on the Bin Packing task. Specifically, we ran three independent trials for both EoH and our method, and the results are summarized in Table 14.
In our proposed method, the seed heuristic strategies are not hand-crafted. Instead, they are automatically generated by the large language model, which introduces some degree of randomness between runs. Despite this randomness, our method consistently outperforms EoH in both effectiveness and stability. For example, the 1k_C100, 10k. C100, and 10k_C500 test sets, the variance in our results is small, and the average performance is consistently better than FoH.
These results demonstrate that our dual-layer framework, combined with the differential evolution mechanism, effectively enhances both consistency and generalization. Moreover, the smaller variance in our method's results highlights its robustness against the randomness introduced by the seed generation process.
H.2. Impact of Population Size on Experimental Outcomes
To further analyze the impact of population size on experimental outcomes, we conducted additional experiments on the Bin Packing task, testing our method with a reduced population size of 4. The results are summarized in Table 15.
As shown in the table, although the average performance slightly decreases with smaller population size, our method still outperforms EoH (population size 20). For example, the average error of our method with population size of 4 is 1.76 % which is better than EoH's 2.09%. This demonstrates that our dual-layer framework and differential evolution mechanism exhibit significant robustness and effectiveness, maintaining superior performance even with smaller populations.
H.3. Performance Comparison with EoH on LNS Tasks
In this subsection, we present a comparison between the proposed LLM-LNS framework and existing method EoH, on large-scale combinatorial optimization tasks. While EoH focus discovering strategies for combinatorial optimization problems, our LLM-LNS framework is specifically designed to address the challenges of large-scale MILP problems through its dual-layer self evolutiooo mechanism.
We evaluated the methods on the Set Covering (SC) problem, a minimization task, using two large-scale datasets:
42

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Table 16. Performance comparison the SC₁ dataset (200,000 variahles and constraints). Results reported objective values (lower
is better).
Method
Instance;
Instance:
Instances
Instances
Avg
EOH-LKS
16114.27
16073.72
16046.83
10074.26
16070.15
LLM-LNS (Ours)
15830.611
15801191
15800.171
15800.171
15802.68T
Table 17. Performance comparison the SC2 dataset (2,000,000 variables and constraints). (lower better).
Results are reported ohjective values
Instance,
Instance,
Instancey
Instance
Avg
BOH-LNS LLM-LNS (Ours)
175358.39
174339.78
174182
174026.33 158759.901
174978.20
158901.77
158953,571
158712.647
158831421
S Instances with 200,000 decision variables and constraints.
SC2: Instances with 2,000,000 decision variables and constraints.
EOH-LNS was selected as the primary baseline for comparison because it generally outperforms FunSearch on combinatorial optimization tasks, as reported in prior literature. This ensures fair and representative evaluation of our framework. The experimental results are summarized Tables 16 and 17, where LLM-LNS consistently outperforms EOH-LNS across all test instances. Specifically:
On the SC, dataset (200,000 variables and constraints), LLM-LNS achieves an average improvement of 1.67 over EOH-LNS.
On the SC₂ dataset (2,000,000 variables and constraints), the improvement is more pronounced, reaching 9.20% on average.
These results demonstrate the superior capability of LLM-LNS solving large-scale optimization tasks, particularly in terms of solution quality. The improvements can be attributed to the dual-layer architecture, which effectively balances search diversity and solution convergence.
The results demonstrate that LLM-LNS consistently outperforms EOH-LNS, particularly on large-scale instances. This improvement is enabled by the dual-layer self-evolutionary mechanism, which dynamically balances exploration and exploitation:
The outer layer generates diverse prompts to broaden search space coverage, preventing premature convergence to suboptimal solutions.
The inner layer refines heuristic strategies and accelerates convergence by leveraging the evolved prompts, ensuring high-quality solutions.
This collaborative interaction between the two layers forms a dynamic feedback loop, enabling continuous learning and adaptation. While EOH-LNS demonstrates strong performance on small-scale combinatorial optimization tasks, its inability balance exploration and convergence limits its scalability larger and more complex problems, as evidenced by the significant performance gap SC2.
H.4. Comprehensive Evaluation TSPLib Instances
We evaluated our method on all 87 instances from the TSPLib benchmark to comprehensively assess its performance. As shown in Table 18, method achieves better results than the EOH baseline on 43 instances, matches EOH on 39 instances, and performs slightly worse on only instances. This demonstrates that our method is not only robust but also generalizes effectively across diverse TSP instances of varying sizes and complexities. On average, the gap from the best-known solutions is reduced from 6.93% for EOH to 6.25% for our method, representing an overall improvement of approximately 10%. These results highlight the superiority of our approach in minimizing the gap to optimality across a wide range of benchmark instances.
43

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Table 18. Performance comparison between EOH and our method on TSPLib instances. Results are reported as the gap from the best-known solutions (%). Bold values indicate the better performance, with red for EOH and blue for ours. Green indicates identical
performance.
Instance
Gap
Ours Gap
Instance
FOH Gap
Ours Gap
Instance
Gap
Ours Gap
pe4.9
2.80%
1.97%
pla7397
4.28%
4,28%
gr96
0.00%
0,00%
rd100
0.01%
0.01% %
r15934
4,25%
4.25 %
pch442
1.15%
0.96%
u2319
2.34%
2.34%
gil262
0.48%
pch3038
4.13%
4.13%
10n
0.03%
0.03%
A417
0.80%
0.77%
1sp225
1.39%
0.00%
B1400)
7.66%
2.28%
new 1379
3.82%
2.99%
d2103
188%%
1,88%
kroA150
0.00%
0.00%
pob1
5.07%
2.91%
d198
0.40%
0.29%
11157
5.03%
5.03%
gr666
2.17%
0.00%
ch130
0.01%
0.70%
kroB100
0.00%
0.00%
u1060
4.04%
1.54%
berlin52
0.03%
0.03%
eilS
0.67%
0.67%
11304
6.52%
2.40%
u2152
4.60%
4.60%
16ysses16
0.00%
0.00%
2.85%
1.13%
kxoD100
0.00%
0.00%
1inhp318
3,22%
2.77%
299
0.61%
0.11%
rd400
2.23%
0.82%
gr202
0.54%
0.00%
vm 1084
3.64%
1.74%
rat575
3.11%
1.88% %
d1655
5,79%
5.79%
ch150
0.37%
0.04%
pr107
0.00%
0
krol3200
0.23%
0.44%
=280
2.06%
0.34%
d1291
6.53%
2.54%
gr229
1.15%
0.00%
2x264
0.00%
0.00%
pr76
0.00%
0
d493
2.82%
1.27%
dsj1000
4.28%
1.06%
pr136
0.09%
0.00%
ra199
0.99%
1.37%
an153
220.07%
215.43%
kroA
0.02%
ali535
0.67%
0.00%
ulysses22
0.00%
0.00%
kroBI 150
0.08%
0.01%
bier127
0.26%
0.01% %
kzoC100
0.01%
0.01%
ci176
1.53%
1.18%
p=124
0.00%
0.00%
d1323
4.35%
1.93%
p654
0.75%
0.05%
gr431
1.93%
0.00%
r11889
4.08%
4.08%
d657
2.85%
1.0%%
eil101
2.59%
2.08%
fn14461
4.63%
4.63%
pv2392
4.19%
4.19%
rat783
4,48%
2.18%
ts255
0.00%
0.00%
ul432
4,84%
3.02%
u1817
4.62%
4.62%
lin318
1.65%
1.09%
r15915
3,96%
3.96%
atr48
215.43%
215,43%
st70
0,31
0.31%
ra199
0.68%
0.68%
113995
4.38%
4,38%
burmal4
0.00%
0.00%
u159
0.00%
0.00%
kruA200
0.25% %
0.62%
u574
2.85%
1.38%
1=1022
3.27%
1.16%
pr152
0.00%%
0.19%
gr137
0.11%
0.00%
pr226
0.10%
0.06%
vml748
4.33%
4.33%
pr144
0.00%
0.00%
knoE100
0.00%
0
The improvements are particularly evident on larger and more challenging instances. For example, on fl1400, our method reduces the gap from 7.66% (EOH) 2.28%, showcasing its scalability and effectiveness in handling complex optimization problems. Similarly, on the pcbl 173 instance, the gap decreases from 5.07% (EOH) to 2.91% %, validating the ability of our method outperform EOH on instances with higher complexity. Even medium-sized instances such as pr439, our method demonstrates significant improvements, reducing the gap from 2.80
In addition to these improvements, we also observe instances where both methods achieve comparable performance. For example, on smaller problems such as eil51, ulysses 66, and kroD100, both EOH and our method report identical gaps, demonstrating that our method maintains competitive performance even on instances where EOH performs optimally, Furthermore, the results highlight the consistency of our approach across various instance scales, from small to large.
There are only few exceptions where EOH slightly outperforms method. For example, on ch130, EOH achieves gap of 0.01%, %. whereas our method reports 0.70%. However, these cases are rare, occurring in only 5 instances out of 87, and do not substantially impact the overall trend of improvement demonstrated by our method.
Overall, our method exhibits strong generalization across the TSPLib benchmark and consistently achieves lower average gaps compared to EOH. The significant improvements on larger and more complex instances further underscore the scalability and effectiveness of our dual-layer architecture. By balancing exploration and exploitation, our method demonstrates its capability to address the challenges posed by diverse and large-scale optimization problems, making it reliable alternative to state-of-the-ee methods such EOH.
H.S. Impact of the Backbone Algorithm on Performance
This section addresses whether the proposed method is sensitive to the choice of the backbone algorithm. Our study focuses on solving large-scale MILP problems, where heuristic methods play a critical role due to the complexity of the problem space. Among these methods, LNS has demonstrated significant advantages in scalability and efficiency, especially for large-scale problems. In this context, we selected ALNS (Adaptive Large Neighborhood Search) as the backbone of our framework. ALNS, as a variant of LNS, dynamically adjusts neighborhood sizes to balance exploration and exploitation, making it more effective than non-adaptive LNS methods, which often struggle with local optima in large-scale problems.
To validate this choice, we conducted experiments replacing ALNS with non-adaptive LNS in our framework. The results,
44

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Table 19. Comparison of ALNS (adantive) and non-adantive LNS as the backbone algorithm in our framework. Results are reported objective values (lower is better).
Method
SC₁
SCa
MVC:
MVCa
MIS:
MIS;
MIKS:
MIKS;
Withous Adaptiive
15957.0
160510.8
26850.3
269701.8
23073.2
230497.4
36330.8
362496.3
T.MMIT NS (Ours)
15802.7
158878.9
26725.3
268033.7
23169.3
231636.9
364798
363749.5
Table 20. Performance comparison of L.L.--.NS using different M.MSs on the 10k, C500 dataset. Results are reported the gap from the best-known solutions (%). Lower values indicate better performance.
L.M Model
Run
Runz
Runs
Avg.
gpl do mini
0.42%
0.52%
0.70%
0.55%
spt-4a
0.33%
0.58%
0.39%
0.43%
deepseek
0.83%
0.52%
0.38%
0.58%
semini-1_S-poo
0.63%
0.53%
102%
Ilama-3.1 1.1ea.3.--700
2.87%
3.98%
0.88%
2,58%
summarized in Table 19, show that ALNS consistently outperforms non-adaptive LNS across all tested MILP instances. For example, on the SC₁ problem, the objective value achieved by ALNS is 15802.7, compared 15957.0 for non-adaptive LNS. Similarly, on the MVC₂ problem, ALNS achieves an objective value of 268033.7, whereas non-adaptive LNS reports 269701.8. These results highlight the critical role of adaptive mechanisms in ALNS for leveraging the full potential of our framework.
H.6. Robustness of LLM-LNS with Different LLMs
We conducted experiments evaluate the robustness of the LLM-LNS framework across various large language models, including GPT-4o, GPT-4o-mini, DeepSeek, Gemini-1.55 1.5-Pro, and Llama-3.1-70B. These experiments were performed on the O5kC dataset, and the results are summarized in Table 20.
The results demonstrate that the dual-layer structure of LLM-LNS adapts effectively to different LLMs, achieving reasonable performance across all tested models. GPT-4o consistently achieved the best results, showing the lowest average gap of 1,, followed by GPT-4o-mini (0.55% and DeepSeek (0.58%). Semini-1.5-Pro and Llama-3.1-700 exhibited relatively weaker performance, with average gaps of 1.02% and 2.58 % respectively. These variations are likely due to differences in model architecture and pretraining quality. Nonetheless, the framework demonstrated strong general robustness, with all models performing adequately within the LLM-LNS structure.
These findings underscore the necessity of combining LLMs with a structured optimization framework to fully leverage their potential.
H.7. Comparison with ReEvo
We conducted additional experiments to compare our proposed method with ReEvo (Ye et al., 2024), a contemporary hyper-heuristic framework that combines reflection mechanisms and evolutionary search. Both methods were evaluated on the Bin Packing problem using the lightweight language model GPT-4o-mini, with the number of iterations fixed at and the population size set to 20.
In the experiments, ReEvo exhibited poor stability when using GPT-4o-mini. Out of 138 attempts, only 3 runs successfully completed all 20 iterations, while the remaining runs were prematurely terminated due to invalid offspring generated during certain generations. Upon analysis, we identified severe hallucination issues in ReEvo. Although its reflection mechanism was effective in capturing evolutionary directions through pairwise comparisons of parent strategies stored in short-term memory, any errors in reflection led to a rapid decline in the quality of subsequent offspring. For example, ReEvo frequently attempted to call nonexistent libraries or use invalid function parameters, resulting invalid heuristic algorithms and the termination of the evolutionary process.
In contrast, method adopts differential memory mechanism that generalizes beyond pairwise comparisons. Rather than relying on two parent strategies, our approach analyzes differences across multiple parent solutions and their corresponding objective values. This richer context enables the language model to conduct contrastive learning, allowing it to internalize more robust and directional evolutionary signals. addition, differential memory is embedded within a dual-layer agent architecture, where the upper-layer agent optimizes prompt structures while the lower-layer agent generates new strategies. This coordinated design facilitates deeper interaction between memory-guided learning and heuristic generation, significantly
45

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
improving both performance and stability.
To ensure fair comparison, we selected the 3 successful ReEvo runs and compared their performance with our method. Under the default setting, ReEvo utilized an expert seed algorithm to initialize its population. However, after 20 iterations, the best best-performing algorithm in ReEvo remained its initial expert seed algorithm, failing to generate superior heuristic strategies. Furthermore, when the expert seed algorithm was removed, ReEvo's solution quality deteriorated further, with its average performance on the Bin Packing problem falling significantly behind our method.
The experimental results are shown in Table 21. Our method demonstrates substantial advantages under the same settings. In terms of solution quality, our approach consistently outperformed ReEvo across all test instances of the Bin Packing problem, with even greater advantages in scenarios without expert seed algorithms. Additionally, our method exhibited significant stability advantages, consistently completing 20 iterations and generating high-quality heuristic strategies without being affected by the hallucination issues observed in ReEvo. The collaborative optimization between the agents in our dual-layer architecture effectively balances search diversity and efficiency, delivering superior performance and higher robustness.
Table 21. Performance comparison between ReEvo and our proposed method on the Bin Packing problem. Average percentages represent the error rates.
Ik.C100
Sk,C100
10k,C100
15,0
5k_C500
10k_C500
Avg
ReEvo Runl
3.78%
0.80%
0.33%
6.75%
1.47%
0.74%
2.31%
ReEiaa Run2
3.78%
0.80%
0.33%
6.75%
1.47%
0.74%
2.31%
ReEvva
3.78%
6.75%
1.47%
0.74%
2.31%.
ReEvo Avg
3.78%
0.80%
0.33%
6,75%
1.47%
0.74%
2.31%
ReEvaa no expert Run
4.87%
4.08%
4.09%
4.50%
3.91%
3.95%
4.23%
ReFxvo-n-eexpe Run
4.87%
4.08%
4.11%
4.50%
3.90%
3.97%
4.24%
RcEvo-no-cxpert Ruo 3
4.87%
4.08%
4.09%
4.50%
3.91%
3,95%
4,23%
ReExo-no-expert Avg
4.87%
4.08%
4.10%
4.50%
3.91%
3,96%
4.24%
Ours Runl
3.58%
0.85%
0.41%
3.67%
0.82%
0.42%
1.63%
Ours Run?
2.69%
0.86%
0.54%
2.54%
0.87%
0.52%
1.34%
Ours Run3
2.64%
0.94%
0.69%
2.54%
0.94%
0.70%
1.41%
Ours Avg
2.97 %
0.88%1 1
0.55%
2.92%
0.88%
0.55 7
1.46%
In conclusion, our method not only outperforms ReEvo in terms of experimental results but also demonstrates significant advantages in stability and robustness. By integrating differential memory into dual-agent framework, our approach goes beyond short-term comparisons and enables deeper, contrastive learning across diverse search trajectories. This innovation opens up new avenue for applying LNS to large-scale optimization problems, surpassing existing state-of-the-ar solutions in both quality and reliability.
H.8. Performance Comparison with EoH Using Different LLMs
To evaluate the adaptability and effectiveness of our proposed method across different language models, we conducted experiments comparing our framework with FoH on the 10k C500 dataset using three L.Mss: GPT--4-mini, GPT-44o, and DeepSeek. EoH was chosen as the baseline based on existing literature, which suggests it generally outperforms FunSearch on combinatorial optimization tasks.
The results of the experiments summarized in Table 22. Our method consistently outperformed EoH across all tested LLMs. Notably, our approach demonstrated significant advantages when using GPT-4o-mini and DeepSeek. For instance, with GPT-40-mini, our framework achieved an average performance of 0.55% %, which is approximately four times better than EoH's 2.23%. Similarly, under DeepSeek, our method achieved an average performance of 0.58%. significantly outperforming EoH's 1.77%
One particularly interesting observation is the poor convergence of EoH under DeepSeek. In both Rung and Rung- EoH's fitness function values during evolution were much lower than those achieved by our framework. This highlights the limitations of EoH's framework in adapting certain LLMs, where errors in evolution can significantly impact its performance. In contrast, our dual-layer architecture, combined with differential evolution, demonstrates robust and stable performance across all tested L.LMs.
These findings underscore the superiority of our approach in leveraging the capabilities of different LLMs for combinatorial optimization tasks. The dual-layer structure not only enhances adaptability but also ensures consistent performance, addressing the convergence and stability issues observed in EoH. We believe these results further validate the effectiveness
46

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Table 22. Performance comparison between EoH and our proposed method on the 10k_C300 dataset using different LLMs, Average percentages represent the error rates.
10k_C50
Run
Ron:
Runa
Avg.
apt-4o-mini (ROH)
0.97%
2.50%
3.21%
2.23%
gpt-4o-mini (Ours)
0.42%
0.52%
0.70%
0.55 8,55%1 1
gpt-4o
0.41%
0.50%
gpi-4o (Oun)
0.33%
0.58%
0.39%
0.43 % T
deepseek (BOH)
1.77%
deepscek (Ours)
0.83%
0.52%
0.38%
0.58
Table 23. Performance comparison between standalone LLMs and our proposed framework the Bin Packing problem. Average percentages represent the error rates.
1k_0100
5k,C100
1Ok_C100
Ik_C500
5k_C500
10k_C500
Avg
Sample Runl
5.32%
4.40%
4.44%
4,97%
4.27%
4.28%
4.61%
Sample Run2
7.51%
2.30%.
9,47%
3.99%
4.93%
Sumple Run3
5.32%
4.40%
4.44%
4.97%
4.27%
4.28%
4.61%
Sample Avg
6.05%
3.70%
3,54%
6.47%
4.37%
4.18%
4.72%
Ours Runl
3.58%
0.83%
0.41%
3.67%
0.82%
0.42%
1.63%
Ours Run2
2.69%
0.86%
0.54%
2,54%
0.87%
0.52%
1.34%
Run?
2.64%
0.94%,
0.70%
Ours Avg
2.97%
0.88 1
0.55%
2.92%
0.88 %-1
0.58%
1.46%
and scalability of our method across diverse settings.
H.9. Comparison with Standalone LLMs
To further validate the effectiveness of our framework, we conducted a comparative experiment against standalone L.LMs. Specifically, we replaced all crossover and mutation operations in our framework with instances where the problem information was directly input into standalone GPT-4o-mini model, which independently generated new strategies and evaluated them. Both approaches were tested on the Bin Packing problem across 20 iterations, with the same total number of strategies generated in each case.
The results, summarized in Table 23, demonstrate that our framework significantly outperforms the standalone LLM approach across all test instances. On average, our framework achieves an eπrоr rate of 1.46 %, which is approximately 69% lower than the standalone LLM's average error rate of 4.72 %.. This improvement is primarily due to the dynamic interaction between the outer and inner layers in our framework, which balances exploration and exploitation, ensuring the generation of diverse and high-quality strategies. In contrast, the standalone LLM approach frequently generated redundant or identical strategies, thereby limiting its ability to effectively explore the solution space.
Additionally, we observed that the standalone LLM approach struggled to maintain diversity as the number of iterations increased, resulting in many duplicate strategies and subsequent decline in optimization performance. In contrast, our framework, through evolutionary operations such as crossover and mutation, maintains diversity within the population, enabling it to achieve superior optimization outcomes with the same number of generated strategies.
These findings confirm that our framework not only improves decision-variable ranking and optimization compared standalone LLMs but also addresses key limitations such as diversity and redundancy. By integrating evolutionary mechanisms into the LLM-based framework, our approach ensures more efficient of computational resources and delivers superior performance across various problem instances.
H.10. Efficiency Comparison of Evolution Time
To complement our performance evaluation, conducted detailed comparison of the evolution time between our method and representative baseline, EOH. Both methods were run over 20 generations on the Bin Packing and Traveling Salesman Problem (TSP) tasks. Evolution time is measured as the total wall-clock time spent on generating and evaluating new prompt strategies during each generation. As our method operates in learning-based paradigm, all evolutionary computations occur in the training stage and do not affect inference- efficiency.
The results are summarized in Tables 24 and 25. Overall, our method achieves comparable or lower evolution time than EOH
47

---

Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Table 24, Evolution time (in minutes) comparison on the Bin Packing task over 20 generations.
Method
Ours BOI1
9.9
10.5
11.1
11.7
12.3
12.9
49.3
51.1
51.7
53.8
17.9
38.5
46.8
47.4
69.5
78.2
88.1
88.7
108.7
109.3
Method
11
12
13
14
15
16
17
56.4
57.1
59.5
61.5
136.9
FOH
110.0
110.5
111.3
111.9
117.2
117.8
118.4
137.4
138.
138.7
Table 25. Evolution time (in minutes) comparison on the TSP task over 20 generations.
Method
1
2
3
6
7
8
10
Ours
3,8
9.3
11.6
14.2
16.6
23.1
35.5
37.2
38.9
40.6
EOH
6.0
12.3
16.0
20.9
23.5
26.0
28.4
Mathod
11
12
17
Ours
42.2
44.2
46.0
47.8
49.6
51.6
53.3
58.5
65.5
67.3
33.1
35.4
39.1
45.6
48.1
50.4
59.6
Table 26. Comparison of objective values on real-world datasets from MIPL.B 2017 under 3000s time limit. Lower is better. indicates no feasible solution was found. "*" indicates the method failed due to architectural incompatibiliyy.
Instance
Random-LNS
ACP
CL-LNS
Gurobi
GNN&GEDT
Light-MLLPpp LLM-LNS (Ours)
dws (min.)
189028.6 14261.3
186625,3
146411.0
147417.7
143630,5
(min.)
27488.0
3575.9
across most generations. Notably, in the Bin Packing task, our approach achieves faster evolution in the earlier generations and maintains efficiency in later ones, while EOH exhibits significant runtime increases as generations progress.
We observe that EOH tends exhibit higher evolution time in many generations, particularly in the Bin Packing task. This is largely due to the nature of the algorithms it evolves: EOH often produces solutions with On²)) computational complexity, such as pairwise comparison-based packing or route construction procedures. These strategies, while potentially effective, impose significant overhead during evaluation. In contrast, our framework encourages the emergence of simpler, efficient strategies with linear (n) complexity. By guiding evolution through gerformance-base feedback and maintaining diversity through controlled variation, our method reduces redundant exploration of expensive algorithms and ensures faster convergence. This advantage becomes especially clear in later generations, where EOH's runtime escalates, while our approach remains computationally manageable.
These findings confirm that our method not only outperforms in solution quality, but also sustains competitive superior efficiency in the evolutionary process, making it practical and scalable choice for large-scale combinatorial optimization.
H.11 Evaluation on Realistic Industrial Benchmarks
To assess the practical value of our proposed LLM-LNS framework, we extend our evaluation beyond academic benchmarks to include two real-world problem classes from the MIPLIB 2017 dataset: dws and ivu. These classes are representative of large-scale industrial applications, each consisting of multiple instances with consistent structure and domain semantics.
Unlike many other MIPLIB instances that are either too heterogeneous or too small for learning- based heuristics to generalize meaningfully, the dws and i vvu classes provide favorable setting for systematic experimentation. We use the largest instance in each class as the test case, while the remaining instances are used for training when applicable. All methods are evaluated with time budget of 3000 seconds.
The results are summarized in Table 26. LLM-LNS consistently achieves superior performance, producing better solutions than classical LNS variants, strong commercial solvers such as Gurobi, and recent learning-based approaches. Notably, it is the only method that finds high-quality solutions for both benchmarks, including the challenging vv instance where Gurobi and other baselines fall short. These results highlight the ability of LLM-LNS to generalize to realistic and large-scale MILP problems.
48

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
Table 27. Comparison objective values on large-scale MILP instances across different methods. For each instance. the best- performing objective value is highlighted in bold. The "_" symbol indicates that the method was unable to generate samples for any instance within 30,000 seconds, while "*" indicates that the framework could not solve the MILP problem.
Method
SC₁
SC₂
MVC,
MVC2
MIS,
MIS;
MIKS,
MIKS,
Random-LNS
16140.6
169417.5
27031 4
276467.5
22892.9
221748.6
360110
351964.2 332235.6
ACP
17672.1
4
26877.2
274013.3
23058 0
226498.2
34190.8
CL-LNS
31285.0
15000.0
CP-SAT (LNS only)
16053.5
177566.1
26765
268773.4
23159.1
231091.3
Gurobi
17934.5
320240.4
28151.3
283555.8
21789.0
216591.3
32960.0
329642.4 4
SCIP
25191.2
385706.4
31275
491042.9
18649.9 9
9104.3
29974.7
168289.9
CP-SAT (Full Solver)
16036.8
177413.5
26771.8
269741.6
23152.4
230711.3
GNN&GBDT
16728.8
252797.2
27107.9
271777.2
22795.7
227006.4
Light-MILPOpt
16108.1
160015.5
26950.7
269571.5
22966.5
230432.9
36125.5
362265.1
LLM-LNS (Ours)
15802.7
158878.9
26725.3
268033,7
23169.3
231636.9
36479.8
363749,5
H.12. Comparison with Advanced LNS in CP-SAT
To strengthen the comprehensiveness of our baseline comparisons, we additionally include the LNS capabilities of CA-SAT, a well-known solver developed by Google OR-Tools CP-SAT contains highly engineered portfolio of neighborhood search strategies, including random, sequential, and adaptive mechanisms, and has been recognized as strong non-learning-base LNS system. This makes it a relevant point of reference for evaluating the effectiveness of LLM-LNS.
We evaluate two configurations of CP-SAT: the default full solver and version with use_lns sesseenssoonll oonly True, both executed with 16 threads to activate its full range of neighborhood heuristics. These settings allow us to assess CP-SAT both as a general MILP solver and as a dedicated LNS system. Results are presented in Table 27, using the same time limit as other baselines.
CP-SAT demonstrates competitive performance on easier problems such as Maximum Independent Set (MIS) and Minimum Vertex Cover (MVC), achieving results that are comparable to or better than traditional heuristics. However, on structurally complex and large-scale MILP tasks like Set Covering (SC), its performance noticeably lags behind learning-basse approaches. Additionally, due to architectural constraints, CP-SAT does not support general mixed-integer problems, and thus fails to provide results for the MIKS task.
Despite the strong engineering behind CP-SAT, our proposed LLM-LNS consistently outperforms all baselines across problem types. These findings reinforce the effectiveness and generalization ability of LLM-guided local search, particularly when facing high- disenseinnii combinatorial structures and diverse constraints.
I. Limitations and Future Directions
While the proposed dual-layer self-evolutionary framework has demonstrated strong performance in solving large-scale MILP problems, we acknowledge several limitations that warrant further exploration and improvement. Below, we discuss these limitations in detail and outline potential future directions.
First, although the framework exhibits good generalization ability on MILP and certain combinatorial optimization problems, it is currently tailored to specific optimization scenarios. The design primarily focuses MILP and does not directly extend to other types of optimization tasks, such as nonlinear optimization or dynamic optimization problems. Developing more general agent structure that can adapt to a wider range of optimization algorithms and tasks remains an open challenge. Future work could explore more modular and flexible designs to enhance the adaptability of the framework for solving diverse and complex optimization problems.
Second, the current method leverages the generative capabilities of large language models (LLMs) and evolutionary mechanisms for heuristic strategy design. However, it does not fully incorporate domain knowledge or classical optimization expertise into the framework. In practical optimization tasks, domain-specific knowledge and traditional optimization techniques (c.g., heuristic rules or mathematical programming methods) often play a critical role. A key direction for future research is to explore how to effectively integrate the generalization capabilities of LLMs with optimization domain knowledge to create more efficient and robust algorithms. Such integration could not only improve computational efficiency but also reduce the resource overhead for solving ultra-large-scae problems.
49

---

Large Language Model-driven Large Neighborhood Search for Large-Scalc MILP Problems
Third, the fitness function currently employed for evaluating heuristic strategies relies simple unnormalized averaging of objective values. While this approach has proven effective for the random instances studied in this paper, where objective values likely possess similar orders of magnitude, it may introduce bias when dealing with more heterogeneous sets of problems. In such scenarios, instances with larger objective values could disproportionately influence the evolutionary process, potentially causing the heuristic to overfit to them. pertinent direction for future work involves exploring more sophisticated fitness evaluation mechanisms. This could include the development of multi-metric fitness functions, incorporating measures such as the gap estimation integral or k-step improvement rates, to ensure a more balanced and comprehensive assessment of heuristic performance across diverse instance characteristics.
Finally, computational resource constraints remain practical challenge for solving large-scale problems. While the proposed framework demonstrates good scalability, solving ultra-large-scale instances still requires significant computational time and hardware resources, which may limit its upplicability in resource-constraing environments. Future research could focus on optimizing the computational complexity of the algorithm or designing more efficient resource allocation strategies to address these challenges.
50


Reviews:
[{"review_id": "2WENABYXDJ", "reviewer": "Reviewer_G8Pp", "summary": "This paper proposes LLM-LNS, a Large Language Model-driven Large Neighborhood Search framework for solving large-scale MILP problems. The method introduces a dual-layer self-evolutionary LLM agent: an inner layer evolves heuristic strategies to ensure convergence, while an outer layer optimizes evolutionary prompts to maintain diversity and avoid local optima. Experiments demonstrate that LLM-LNS outperforms state-of-the-art solvers like Gurobi, ML-based LNS methods, and heuristic evolution frameworks such as FunSearch and EOH. The approach shows strong generalization from small-scale training instances to large-scale MILP problems, achieving superior performance in combinatorial optimization tasks like bin packing and the Traveling Salesman Problem.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer G8Pp for the thorough review and positive evaluation of our work.  Your encouraging comments and constructive suggestions are highly appreciated and have helped us further improve the clarity and completeness of the paper.\n\nIn the following, we address your concerns and questions point by point.\n\n**Strengths And Weaknesses:**\n\n**A1:** Thank you for this valuable comment. We would like to clarify that the instances used in our experiments are not arbitrarily selected, but are generated based on standard formulations of canonical MILP problems, as described in Appendix C.5. For each problem class and size range, instances are randomly sampled from the same distribution. Training and testing sets are formed via random partitioning, which ensures fair evaluation and avoids selection bias. We will make this clearer in the main text and explicitly refer readers to Appendix C.5, where we have also added pseudocode for the instance generation process.\n\n**A2:**  Thank you very much for your suggestion! We agree that ReEvo [1] is an important baseline. As detailed in Appendix H.7, we conducted a comparative experiment on the Bin Packing problem under the same settings. When using lightweight models such as GPT-4o-mini, our method exhibited significantly better stability and achieved superior performance across all test instances. We plan to add a summary of this comparison in the main text and include a pointer to Appendix H.7 for clarity. \n\n**A3:**  Thank you for your insightful comment. While our differential memory mechanism shares conceptual similarities with the reflection-based evolution in ReEvo, there are key differences in both design and learning strategy. ReEvo employs a pairwise comparison of parent strategies based on short-term memory. In contrast, our approach learns from differences across multiple parents, enabling the discovery of more directional and effective evolutionary strategies. By leveraging the objective values of these strategies, the large language model performs contrastive learning to internalize beneficial search directions. Furthermore, differential memory is integrated into a dual-layer agent architecture, allowing deeper interaction between prompt optimization and strategy generation. We will clarify these differences in Appendix H.7. \n\n**Questions For Authors:**\n\n**A1:** Thank you for the question. Our method adopts a dual-layer self-evolutionary agent, where the outer layer evolves prompt strategies and the inner layer evolves heuristic strategies. In the outer layer, prompt strategies guide the LLM to generate new heuristics through fixed crossover and mutation templates. While these operators are fixed, the prompt strategies themselves evolve dynamically: they are evaluated based on the performance of the heuristics they produce, and low-performing prompts are pruned over time. This design enables adaptive exploration while maintaining diversity and preventing premature convergence.\n\n**A2:**  Thank you for the question. Our method follows a learning-based optimization paradigm, where evolution takes place during the training stage, not inference. Therefore, it does not affect solving efficiency.\n\nAlthough we introduce an additional layer for prompt strategy evolution, the overall evolution time remains comparable to EOH. The slight overhead mainly comes from evaluating new prompt strategies through testing, which is necessary to compute their fitness.\n\nTo provide a concrete comparison, the total evolution time on the 20th generation is:\n- BinPacking: Ours – 144.7 minutes, EOH – 138.7 minutes\n- TSP: Ours – 67.3 minutes, EOH – 59.6 minutes\n\nWe believe this small difference is acceptable given the improved performance, and again, it occurs only during training, not during actual problem solving.We will include these results in the appendix to provide a more detailed comparison. Thank you again for the helpful suggestion.\n\nThank you again to Reviewer G8Pp for the valuable suggestions — they will undoubtedly help us improve the paper.", "claims_and_evidence": "see the section Strengths And Weaknesses", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Reasonable experimental designs and analyses", "relation_to_broader_scientific_literature": "This paper situates itself within the broader scientific literature by addressing key challenges in solving large-scale Mixed Integer Linear Programming (MILP) problems, a critical area in optimization research.", "essential_references_not_discussed": "Essential References are well-discussed", "other_strengths_and_weaknesses": "### **Strengths**\n\n1. The paper is well-organized and easy to follow, with a clear structure that enhances readability.\n2. Unlike many current works that primarily follow the pipeline of EoH, this paper introduces significant contributions to the LLM-based heuristic evolution pipeline. It proposes an outer layer to evolve prompting strategies, which is novel, and introduces directional evolution based on differential memory. Ablation studies confirm the effectiveness of these innovations.\n3. The paper includes comprehensive experiments for the ablation study, thoroughly evaluating each component of the pipeline.\n\n### **Weaknesses**\n\nI believe this is a generally good paper. I really like the idea of prompt evolution. I have the following concerns about this paper, which if well-addressed will lead to an even better paper.\n\n1. Although various problem classes are considered, the experiments are conducted on selected instances rather than using a standard instance distribution, as is typical in the learning-for-optimization community.\n2. A key baseline, ReEvo [1], is omitted, which is essential given the state-of-the-art context of this work.\n3. The reflection procedure appears similar to the directional evolution based on differential memory. Clarification of their differences is needed.\n\n[1] ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution", "other_comments_or_suggestions": "See the questions part.", "questions_for_authors": "Besides the questions in the Strengths And Weaknesses section, I also have the following questions:\n\n1. How are the prompting strategies evolved? Are fixed strategies employed in the evolution process?\n2. What is the “evolution time” for this pipeline, and how does it compare with previous works?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ThOYJYMpsR", "reviewer": "Reviewer_fpWD", "summary": "The authors propose a Large Language Model (LLM)-driven LNS framework for large-scale MILP problems. Their approach introduces a dual-layer self-evolutionary LLM agent to automate neighborhood selection, discovering effective strategies with scant small-scale training data that generalize well to large-scale MILPs. The inner layer evolves heuristic strategies to ensure convergence, while the outer layer evolves evolutionary prompt strategies to maintain diversity. Experimental results demonstrate that the proposed dual-layer agent outperforms state-of-the-art agents such as FunSearch and EOH. It also achieves superior performance compared to advanced ML-based MILP optimization frameworks like GNN & GBDT and Light-MILPopt.\n\n## update after rebuttal：I'd like to keep the score unchanged.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer fpWD for the positive and encouraging feedback. We are glad that you found our method interesting and the experimental design sound. Your recognition of the contributions and the clarity of our work is truly appreciated and motivates us to further refine and extend our research.", "claims_and_evidence": "Claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The evaluation criteria make sense.", "theoretical_claims": "No theoretical results.", "experimental_designs_or_analyses": "Experiments are sound.", "relation_to_broader_scientific_literature": "The method is interesting and extends LLM reasoning to MILP.", "essential_references_not_discussed": "References are complete.", "other_strengths_and_weaknesses": "The paper was well written with extensive experiments and supporting material.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YDAcUlr336", "reviewer": "Reviewer_r212", "summary": "This paper describes an evolutionary LLM-based framework to produce heuristics represented as code. It extends previously-proposed evolutionary methods for heuristic search with two additional techniques: prompt evolution and directional evolution. Prompt evolution focuses on finding good LLM prompts to produce heuristic strategies, and directional evolution uses meta-prompts to provide strategy fitness values to LLMs as feedback to improve strategies. This is applied for both typical combinatorial heuristics, evaluated on online bin packing and the traveling salesman problem, and for variable selection heuristics in Large Neighborhood Search in MILP, evaluated in four typical MILP problem classes. Computational results are encouraging when compared with previous non-ML, ML, and LLM-based approaches.\n\n## Update after rebuttal\n\nI maintain my review after the rebuttal.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer r212 for the detailed, thoughtful, and constructive feedback. We greatly appreciate your recognition of the contributions and your suggestions for improving the clarity, robustness, and completeness of the work.\n\n**Methods And Evaluation Criteria:**\n\n**A1:**  We agree that fully evaluating high-level LLM behavior is challenging. As suggested, we will include the full evolution traces of both strategies and prompts in the appendix to improve interpretability. Regarding instance realism, as noted in our response to Reviewer 4X7L, we have added experiments on two large-scale MIPLIB problem classes to further validate the robustness of our method.\n\n**A2:** CL-LNS was designed for small-scale MILPs and struggles to scale to our large instances with hundreds of thousands of variables. Training takes over 8 hours per instance, and inference is 30× slower than our method, making it impractical. Following your suggestion, we added CP-SAT (16 threads, both original and use_lns_only) as a new baseline. As shown in Table 1 at the supplementary link, CP-SAT supports only integer programs and performs well on easier problems like MIS and MVC. However, on more complex large-scale tasks such as SC${}_{2}$, its performance lags behind several other baselines. **Our method still outperforms all baselines across tasks.** Due to time constraints, further analysis of CP-SAT—including using it as a subsolver to enhance LLM-LNS—will be included in future work.\n\n**Experimental Designs Or Analyses:**\n\n**A1:** We agree your suggestions help better highlight our method’s strengths. We will revise the paper to include Figure 8 in the main text if space permits. Following your advice, we also report the primal integral in Supplementary Table 2, which further confirms the effectiveness of LLM-LNS. We appreciate your point on the deployment advantage of LLM-based methods and will add a note on this practical benefit in the revision.\n\n**A2:**  Our method evolves prompt strategies during training, not inference, so it does not affect solving efficiency. Although we add a prompt evolution layer, its total time remains comparable to EOH, with minor overhead from fitness evaluation via testing. Evolution times (in minutes) for BinPacking and TSP over 20 generations are reported in Rebuttal to Reviewer G8Pp, and will be added to the appendix.\n\n**A3:** You're absolutely right—setting a time limit per subproblem is important for robustness. In our implementation, we do impose a maximum time per LNS iteration: 100 seconds for problems with ~100K variables, and 200 seconds for ~1M variables. We will clarify this in the experimental setup section of the paper.\n\n**A4:** We agree that unnormalized averaging may be biased on heterogeneous datasets. In ongoing work, we explore multi-metric fitness (e.g., gap estimation integral, k-step improvement rate). We will briefly discuss this in the Appendix as a direction for future work.\n\n**A5:** The terms site, value, and constraint describe the constraint matrix: involved variables, coefficients, and RHS. We'll clarify this in the paper. In ongoing work, we observe that giving full constraint details may lead to strategies with high time complexity. We're exploring feature extraction to simplify inputs, and will discuss this in the Appendix.\n\n**Other Comments Or Suggestions:**\n\n**A1&A3:** We have updated the plots to report the best-so-far solution at each time step. The corrected results are shown in Appendix Figures 1–4. The primal integral results (based on the best-so-far solutions) have been added in Appendix Table 2.\n\n**A2:** We have added the minimization or maximization indicator for each problem in Appendix Table 1. If helpful, we can further include a primal gap comparison in the Appendix to make the results clearer.\n\n**A4&5&8&9:** We agree this will make the paper clearer, and will revise the corresponding sections.\n\n**A6:** We confirm that, following the same setup as EOH and FunSearch, we use five TSPLib instances (d198, eil76, rat99, rl1889, and u1060) as the training set for evolving our policies. None of the other TSPLib instances used in evaluation are seen during training.  We will update Table 17 to clearly mark this.\n\n**A7:** We have explained the difference between set 1 and set 2 in Appendix Table 5 (Sec. C.5). We'll also add a sentence in the main text to clarify this and point to the appendix.\n\n**A10:** We will revise Appendix C.5 to include a clear description of the instance generation process.\n\n**A11:** We will include the final heuristics in the code and highlight key algorithmic directions in the appendix to aid interpretability and better understand LLM behavior.\n\nDue to the rebuttal length limit, supplementary figures and tables are provided at https://anonymous.4open.science/r/Supplementary-Figures-and-Tables-8DBB/. If any part of our response is unclear or insufficient, we would be very happy to further clarify and continue the discussion.", "claims_and_evidence": "There are two main methodological contributions: 1, the strategy-search addition to the stack of evolutionary LLM layers for searching for heuristics to solve a combinatorial optimization problem, which enable the LLM to diversify and control its own search strategies, and 2, the use of LLM-based heuristic search in the context of Large Neighborhood Search. Their effectiveness is well-supported by a comprehensive set of experiments in various forms: only the LLM framework without the LNS for online bin packing and TSP in Sec. 4.1, ablation studies on each LLM strategy in Appendix G, and the full framework with LNS in Sec. 4.2. The appendix also contains other supporting experiments, such as variations in population size, variations in LLMs, and stability.\n\nExperiments on online bin packing and TSP show that this stack of evolutionary methods can improve upon previous similar approaches by a reasonable margin, and the ablation studies confirm that both prompt evolution and directional evolution make a significant difference. These improvements may not always be consistent in the sense that turning off one or the other could be better, but they appear to be consistently better than not using either approach. The computational results on LNS are also very positive and encouraging. In general, the computational evidence is comprehensive and covers a good number of different scenarios.", "methods_and_evaluation_criteria": "The LLM strategy search makes sense: the heuristic search itself might require some guidance of which directions to explore. The example in Figure 3 is useful to understand what it is doing, and it is very interesting to see how the prompt strategy can guide the heuristic strategy towards certain known algorithmic directions. While it is always tricky to truly evaluate LLM behavior with high-level methods like these, the ablation tests suggest meaningful improvements. I suspect that this could also lead to more interpretable heuristics since the heuristic search is directed by broad algorithmic strategies, but this study is not present in the paper (it would be very interesting to see, but I do not expect it for this rebuttal).\n\nThe LNS research direction is also promising. Based on my own experience as an OR practitioner, I have had the prior belief that if there is any entry point to combine LLM-based function search with OR solvers, LNS is probably one of the most suitable ones. Variable selection strategies in LNS are flexible enough so that improvements in functions can produce significant impact, simple in scope enough to let LLMs work without a lot of complexity, and leverage the full generality of OR solvers. It is encouraging to see this in action and working well.\n\nAs far as I know, both of these approaches are novel, though I am more familiar with the LNS literature than the LLM one.\n\nThe computational evaluation appears to be careful and generally comprehensive. The experiments cover a good variety of both problems and baselines. For the MILP instances, I tried to get a sense of how realistic these instances are, but unfortunately I could not find how these instances were generated. Based on the number of variables and constraints, they seem rather sparse (e.g. 3x constraints on independent set or vertex cover means that the average degree of the graph is 6). That said, while ideally it would be better to have more realistic applications, it is not a significant concern.\n\nI do have some concerns related to the LNS baselines:\n\n1. I am surprised that your CL-LNS baseline is performing so poorly, which is not what you would see in (Huang et al., 2023b). Do you know why? I do notice that you are solving much larger instances than in that paper, but it is still a little surprising and I wonder what exactly is the issue.\n\n2. If the behavior of CL-LNS is indeed correct, then I would argue that this paper is missing something closer to state-of-the-art LNS. If random LNS is your best LNS baseline, then I do not think you have SOTA LNS in your experiments. What I suggest is adding CP-SAT as a baseline to the paper. While CP-SAT does a lot more than LNS, it contains a competitive LNS implementation and it does not require you to have to implement yet another LNS algorithm. You have two options here, use it as a full blown solver (which would belong in the Gurobi/SCIP category), or if you want only its LNS capabilities for purposes of comparison, you can turn on the use_lns_only parameter. Make sure to increase the number of workers from the default as the various types of LNS are only active with a certain number of workers (I suggest 16, or 32 if you want; this may depend on how many threads other baselines are using for a fair comparison). It is of course not an ML-based approach, so it may not perform better than other ML-based approaches, but I expect it to be a better baseline than random LNS, since it implements random LNS and other LNS techniques.", "theoretical_claims": "The paper has no theoretical claims.", "experimental_designs_or_analyses": "The experimental setup appears sound. As mentioned above, I consider these experimental results to be very positive, but I have a few comments and suggestions for improvement.\n\n1. Looking at the results from Table 4, I first thought that you might be slightly overstating the contributions: my read of Table 4 is that LLM-LNS is a clear advantage over Gurobi and SCIP, but it is only a slight advantage to Light-MILPOPT. However, I believe your results are actually stronger than it may first appear from reading the main text. \n\n    * This is more visible in Fig. 8: even if the results are fairly close at the time limit, LLM-LNS can obtain very good solutions early on, which is valuable in practice. I would like to make three recommendations to emphasize the strength of your own results: 1, show Figure 8 in the main text if you can find some space, 2, report the primal integral as well, and 3, include a sentence on this in the main text. The primal integral is a common way in the OR/MILP literature to quantify heuristic performance over time (I left another comment on this below).\n\n    * Furthermore, I would actually consider simply being competitive with the ML-based approaches a success: in certain use cases, the result of LLM-based approaches can be preferable over typical neural network approaches because they are significantly easier to deploy and maintain. From a software engineering / systems perspective, it is easier to copy-and-paste and maintain a short snippet of a code rather than needing to store and maintain neural network data for an algorithm. Of course, they have different obstacles in the \"training\" step, so this opinion might not be prevalent or suitable for every use case, but this is definitely a relevant advantage for those interested in practical deployment. Perhaps this is something you might want to note in the paper.\n\nNext, I discuss some areas that could have been better covered:\n\n2. I was looking for results on the amount of time and compute needed to produce these heuristics, and I could not find them. I am not sure if I missed them, but I believe these are important to include (even if you only have estimates). Please include them if they are not in the paper, or let me know where they are if they already are.\n\n3. If I understand correctly, I do not see a per-subproblem time limit in LNS. This is a little surprising for a number of reasons: 1, practical LNS implementations typically have some time limit in subproblem solves so it does not blow up, especially when they accidentally set the neighborhood size too high; 2, although the fitness function would filter these out, you may be wasting time running slow code proposed by LLMs; 3, as noted in Section F.1, this is risky if you are trying to generalize to larger instances. I believe a subproblem time limit can help make the approach more robust. That said, it is encouraging to hear that this method works well even without a per-subproblem time limit. I understand that this is not something that you can do at rebuttal, but it feels omitted and a brief discussion about this somewhere in the paper would be useful to at least highlight that this is something that can be done.\n\n4. Another topic that I felt could be better covered in the paper is the fitness function. The paper proposes simple unnormalized averaging. This works well for the random instances studied in this paper because all objective values likely have about the same order of magnitude, but this is not always true for more heterogeneous sets of problems. In those cases, instances with larger orders of magnitude in objective value may be much more emphasized than those with smaller ones, and thus the heuristic may overfit to them. While simple averaging is fine for this work, I feel it is appropriate to include a short discussion about this in the fitness function section in the Appendix.\n\n5. There is little discussion on the input parameters to the variable scoring heuristic, which I feel is an important topic. Looking at the examples, I see names like \"site\", \"value\", \"constraint\", but I cannot figure out what exactly they are. Even those that are self-explanatory, it would be nice to know how they are represented. Could you please describe what they are in the paper? In particular, why did you choose these parameters and not others? Could you have done better if you have chosen others, or even omitted some (as this affects how the LLM behaves)? Please add a discussion of this topic to the paper.", "relation_to_broader_scientific_literature": "I believe the paper does a decent job at relating to previous work.", "essential_references_not_discussed": "I do not have further references to add.", "other_strengths_and_weaknesses": "The paper is generally comprehensive and well-written. Overall, I believe this paper is a solid step towards effectively leveraging LLMs in practical OR applications.", "other_comments_or_suggestions": "Here are other minor comments, mostly on presentation:\n\n1. In Figs 7-10, Light-MILPOPT seems to sometimes become worse. I am guessing you are taking the current solution, but this is not the right way to present the result, since you can always keep the best solution. Please correct these plots to report the best solution value found so far in each time step, rather than the current one.\n\n2. Table 4 is difficult to read since improvements on each column depend on whether it is a minimization or maximization problem. An option here is to use primal gap instead, which is traditional in MILP. See, for example, Table 2 in the CL-LNS paper (Huang et al., 2023b in your paper). If you do not want to use it, at least add some indicator on whether you are minimizing or maximizing in each column.\n\n3. As previously discussed, primal integral would be great to see as well (see Berthold, \"Measuring the impact of primal heuristics\"). You seem to have the data to compute that based on Figs. 7-10. Please note comment 1: use the data for the best solution found so far to compute the primal integrals, not the current value like Light-MILPOPT is showing in the submitted version.\n\n4. The ablation study is important to understand the impact of the prompt evolution and the directional evolution. Space permitting, consider adding a sentence in the main text summarizing the results, and point to the appendix.\n\n5. Could you see if you could fit into the start of Sec. 4.1 a couple of sentences explaining the heuristic framework for online bin packing and TSP, i.e. a very brief summary of what you have in Appendix C.4? In my readthrough, I got confused as I thought you were using LNS for these problems, but you are not using LNS here. I believe this misunderstanding is easy to make, so I would even encourage to explicitly add in Sec. 4 or 4.1 that this is not using LNS for these problems.\n\n6. Could you mark in Table 17 which TSPLib instances were used for training? This should be easy enough to add and it would be helpful to get some more information on generalization.\n\n7. In Table 4, please add to the caption the difference between set 1 and 2.\n\n8. Sec. 4.1.2: I presume that you are using the routing solver in Google OR-Tools and not CP-SAT. Please include for clarity, since there are multiple solvers in OR-Tools.\n\n9. Section C.2: Could you please add here that $T$ is for the entire LNS solve (i.e. not for each subproblem), and that you solve each subproblem to optimality? I believe this is the case.\n\n10. Section C.5 seems to be missing information on the instance generation process.\n\n11. Would you be willing to provide in the final version the optimal heuristics for all six problems? This can be included with the code. It would be interesting to see if there is anything interpretable in those heuristics. Furthermore and optionally, it might be insightful to highlight in the paper the algorithmic directions that appeared in prompts of the best heuristics for each problem class.", "questions_for_authors": "All my questions are throughout the above sections. While I am recommending acceptance, there are a few gaps in the paper and I am assuming the authors can provide a reasonable rebuttal. Please go through them carefully and address them, as I believe it can strengthen the paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XMHysNkXbD", "reviewer": "Reviewer_4X7L", "summary": "This paper proposes LLM-LNS, a framework leveraging Large Language Models (LLMs) to drive Large Neighborhood Search (LNS) for solving large-scale Mixed Integer Linear Programming (MILP) problems including Online Bin Packing, Traveling Salesman Problems, SC, MVC, MIS, and MIKS. The main novelty lies in a dual-layer self-evolutionary LLM agent that generates and refines heuristic strategies for neighborhood selection. Experiments validate superior performance over state-of-the-art methods like FunSearch, EOH, and Gurobi.\n\n## Update after rebuttal\nI maintain my review after the rebuttal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer 4X7L for the thoughtful and constructive feedback. We are glad that you find the proposed LLM-LNS framework innovative and recognize its performance improvements over existing methods. We appreciate your suggestions regarding dataset realism, solver settings, and related work, and we address each of these points in detail below.\n\n**Claims And Evidence and Weakness:**\n\n\n**A1:** Thank you very much for the helpful suggestion. We fully agree that evaluating on realistic datasets is important. While MIPLIB 2017 is a valuable benchmark, many of its instances are either heterogeneous or not large enough to meaningfully evaluate LLM-driven heuristics. Therefore, we carefully selected two problem classes from MIPLIB — dws and ivu — which both contain multiple large-scale instances of the same type, allowing for a meaningful train/test split and consistent evaluation.\n\nSpecifically, we used the largest instances from each class as the test set, and the remaining instances for training. All methods were evaluated under a 3000s time limit. The results below demonstrate that LLM-LNS generalizes well to realistic, large-scale industrial problems. We will include these experiments in the appendix and plan to evaluate broader MIPLIB categories in future work.\n\n|               | Random-LNS |ACP| CL-LNS |  Gurobi  | GNN&GBDT | Light-MILPOpt | LLM-LNS(Ours) |\n| :-----------: | :--------: | :------: | :----: | :------: | :------: | :-----------: | :-----------: |\n| dws(Minimize) |  189028.6  | 186625.3 |   -    | 146411.0 |    *     |   147417.7    | **143630.5**  |\n| ivu(Minimize) |  14261.3   |  9998.6  |   -    |  27488   |    *     |       -       |  **3575.9**   |\n\n\n**Experimental Designs Or Analyses:**\n\n**A1:** Thank you for the question. We used the default settings for both Gurobi and SCIP. To ensure a fair comparison, all baselines were run under the same computational constraint: 16 cores and 32 threads within a fixed time limit. We will include a description of these settings in the Experimental Setup section of the revised manuscript.\n\n**Supplementary Material:**\n\n**A1:** Thank you very much for the suggestion! We agree that moving Algorithm 1 into the main text would help clarify the overall workflow of our method. We will include it in the main paper if space permits during the revision.\n\n**Essential References Not Discussed:**\n\n**A1:** Thank you very much for pointing this out. BTBS-LNS is a recently accepted paper at ICLR 2025, which proposes a reinforcement learning-based LNS framework with a binarized-tightening and branching mechanism for solving MIP problems. While the approach is related in spirit, the code is not publicly available at this time. Moreover, the experiments in BTBS-LNS are mainly conducted on relatively small-scale problems (typically with tens of thousands of decision variables), and our previous experience suggests that reinforcement learning struggles to scale effectively in much larger problem settings, which are the main focus of our work. We will add a discussion of BTBS-LNS in the Related Work section, and if the code is released in time, we will consider including a comparative experiment in the final version.\n\nWe sincerely appreciate Reviewer 4X7L’s insightful comments and constructive suggestions. They have helped us significantly improve the clarity and completeness of our paper. We have carefully addressed each point in our revision and will incorporate the proposed changes into the final version. Thank you again for your thoughtful review and valuable feedback.", "claims_and_evidence": "### Key Points\n1. The author claims that the proposed LLM-LNS framework surpasses traditional LNS methods, advanced solvers like Gurobi and SCIP, and modern ML-based frameworks. However, the dataset used in the comparison is four academic ones, so a more realistic dataset like MIPLIB 2017 should be used to validate its effectiveness.", "methods_and_evaluation_criteria": "The authors introduce a dual-layer LLM agent, which evolves heuristic strategies and evolutionary prompts. The framework adapts neighborhood size dynamically based on search progress, allowing for efficient exploration of large solution spaces.", "theoretical_claims": "None", "experimental_designs_or_analyses": "I would like to know the settings of Gurobi and SCIP because most of the solving time is spent on proving optimality.", "relation_to_broader_scientific_literature": "This paper aligns with recent advances in combining LLMs and optimization heuristics, following the trend of using machine learning to automate the design of optimization strategies.", "essential_references_not_discussed": "A few recent works like \"BTBS-LNS: Binarized-Tightening, Branch and Search on Learning LNS Policies for MIP\" are closely related but are not discussed in the paper.", "other_strengths_and_weaknesses": "**Strengths:**\n-  The proposed framework is highly innovative and demonstrates clear improvements over existing methods.\n\n**Weakness:**\n- more realistic large-scale datasets like MIPLIB 2017 should be tested.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposed a Large Language Model-driven Large Neighborhood Search (LNS) method for solving  Large-Scale MILP Problems. Reviewers acknowledged the non-trivial contribution and promising empirical results. They raised several concerns regarding more realistic testing instances, more baselines for comparison, and discussions w.r.t some existing works. Authors' responses successfully addressed most of these concerns. Based on the uniformly positive evaluations, I recommend acceptance.
Decision: Accept (spotlight poster)