Research map / Large language models / Agents, code and math
Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LLM-LNS, an LLM-driven large neighborhood search where a dual-layer self-evolutionary agent evolves variable-scoring heuristics and prompt strategies from small MILP instances and transfers them to large MILPs.
Problem
Choosing effective neighborhoods in large neighborhood search for large-scale MILP problems, where hand-crafted rules need expertise and ML-based neighborhood selection converges slowly or needs costly labeled data.
Approach
A two-level LLM evolutionary agent: the inner layer evolves heuristic thoughts and code for variable scoring, the outer layer evolves prompt strategies for crossover/variation, and differential memory feeds parent fitness values back to the LLM to direct evolution; the learned scorer drives adaptive neighborhood selection in LNS.
Key results
- On online bin packing, the agent averages 1.63% excess bins versus 2.09% for EOH and 2.31% for FunSearch.
- On TSPLib subset, the agent achieves 0.08% average gap to best-known solutions versus 0.16% for EOH.
- On large-scale MILPs, LLM-LNS reports the best objective on SC1 (15802.7 vs 16108.1 for Light-MILPopt) and the best primal integral on SC2 and MVC2 with over 20% improvement over the closest competitor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LLM-LNS instead of the strongest listed baseline | Large-scale MILP solving · SC1, SC2, MVC1, MVC2 | objective value: SC1: 16108.1 -> 15802.7; SC2: 160015.5 -> 158878.9; MVC1: 26877.2 -> 26725.3; MVC2: 269571.5 -> 268033.7 | Helped |
| Use LLM-LNS instead of the strongest listed baseline | Large-scale MILP solving · MIS1, MIS2, MIKS1, MIKS2 | objective value: MIS1: 23058.0 -> 23169.3; MIS2: 230432.9 -> 231636.9; MIKS1: 36125.5 -> 36479.8; MIKS2: 362265.1 -> 363749.5 | Helped |
| Use the dual-layer self-evolutionary agent instead of EOH | Online Bin Packing · Online Bin Packing, Avg | fraction of excess bins: 2.09% -> 1.63% | Helped |
| Use the dual-layer self-evolutionary agent instead of FunSearch | Online Bin Packing · Online Bin Packing, 5k C100 and 10k C100 | fraction of excess bins: 0.80% -> 0.85%; 0.33% -> 0.41% | Hurt |
| Use the dual-layer self-evolutionary agent instead of EOH | TSP heuristic generation · TSP TSPLib subset, Avg | relative distance to best-known solution: 0.16% -> 0.08% | Helped |
| Use the dual-layer self-evolutionary agent instead of EOH | TSP heuristic generation · TSP bier127 | relative distance to best-known solution: 0.42% -> 0.01% | Helped |
Surprising findings
- CL-LNS fails to produce results within the time limit on most large-scale instances.
Limitations
- Results depend on a single LLM (GPT-4o-mini) and a fixed number of evolution iterations (20).
- Some baselines fail or are unavailable on large instances (e.g., CL-LNS, GNN&GBDT on MIKS), limiting comparison completeness.
- Hardware and LLM cost are not reported.
Experimental setup
Datasets: Set Covering Minimum Vertex Cover Maximum Independent Set Mixed Integer Knapsack Set Weibull online bin packing instances TSPLib
Benchmarks: Set Covering Minimum Vertex Cover Maximum Independent Set Mixed Integer Knapsack Set Online Bin Packing (Weibull) TSPLib
Metrics: objective value primal integral fraction of excess bins relative gap to best-known solution
Baselines: FunSearch EOH First Fit Best Fit Nearest Insertion Farthest Insertion Google OR-Tools AM POMO LEHD Random-LNS ACP
Builds on: FunSearch EOH Adaptive Constraint Partitioning Random-LNS
Closest papers by meaning
- LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch (ICLR 2025 · similarity 0.87)
- Regularized Large Neighborhood Search (NeurIPS 2026 · similarity 0.87)
- Multi-Objective Evolution of Heuristic Using Large Language Model (AAAI 2025 · similarity 0.86)
- HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs (AAAI 2025 · similarity 0.86)
- Towards Foundation Models for Mixed Integer Linear Programming (ICLR 2025 · similarity 0.86)
- Autoformulation of Mathematical Optimization Models Using LLMs (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.