PaperlayerView exact revision on arXiv

Source-linked AI summary

LLMs Can Design Near-Optimal OR Algorithms

Jackie Baek

arXiv:2608.27296v1cs.AIcs.LG

TL;DR

The paper asks whether general-purpose LLMs can design algorithms for hard, well-specified operations-research problems. It evaluates minimal-prompt LLM use across inventory, queueing, and assortment tasks at instance and problem-class levels, finding that gpt-5.6-sol matches or outperforms the best existing method on nearly all evaluated instances, including through reusable level-2 algorithms.

  • Problem

    The paper asks how well LLMs can design algorithms for hard, well-specified operations-research problems, isolating algorithm design as a distinct OR-pipeline step.

  • Method

    The study tests four LLMs on inventory control, queueing network control, and assortment optimization using one untuned prompt, with either instance-specific solutions or reusable class-level algorithms.

  • Results

    gpt-5.6-sol matches or outperforms the best existing method on nearly all evaluated instances, including when its level-2 algorithm is fixed before evaluation instances are seen.

  • Takeaways & Limitations

    For well-specified OR problems with rich algorithmic traditions, current LLMs can produce high-performing, interpretable algorithms from a minimal prompt.

  • Takeaways & Limitations

    Evidence is empirical and limited to three OR settings; robustness outside tested instance families and the effect of benchmark information in training remain unknown.

Abstract

from arXiv · show

We ask whether large language models (LLMs) can design effective algorithms for well-specified operations research (OR) problems. We study inventory control, queueing network control, and assortment optimization. We evaluate two levels of LLM use: at level 1, the model receives one problem instance and returns a solution for that instance; at level 2, it receives only the problem class description and broad parameter ranges, and returns an algorithm that maps instance parameters to solutions. Human input is minimal: we give one untuned prompt that describes the problem, and the model has access to a Python sandbox tool with a fixed compute budget. The strongest model we test, gpt-5.6-sol, matches or outperforms the best existing method on almost all evaluated instances. This holds even at level 2, where the returned algorithm is fixed before seeing the evaluation instances. Performance also improves sharply across models released less than eight months apart, suggesting that this capability is moving quickly. Thus, for the well-specified operations problems we study, a single untuned LLM query can already produce algorithms competitive with specialized methods. These results suggest that frontier LLMs can be a serious empirical baseline for algorithm design in well-specified OR problems.

1 Introduction

The paper experimentally tests whether general-purpose LLMs can design algorithms for hard, well-specified OR problems, using minimal prompting across three domains. The strongest model matches or outperforms existing methods on nearly all evaluated instances, including when producing reusable level-2 algorithms.

  • Motivation: The study asks whether LLMs can design effective algorithms for operations-research problems.It isolates the algorithm-design step from formulation, implementation, validation, and deployment.
  • Experimental design: The protocol uses one untuned prompt describing the problem and output format, without structural hints or prompt tuning.The model is also given a Python sandbox with a fixed compute budget.
  • Evaluation scope: The experiments cover inventory control, queueing network control, and assortment optimization across 3,440 benchmark instances.The benchmarks include 34 inventory, 13 queueing, and 3,393 assortment instances.
  • Experimental design: Level 1 returns a solution for one instance, whereas level 2 returns an algorithm mapping instance parameters to solutions.Level 2 receives a problem class and broad parameter ranges; level 1 receives numeric parameters for a single instance.
  • Main findings: gpt-5.6-sol is no worse than the best existing method in eight of ten classes at both levels and on every instance in six classes at each level.The comparison selects the strongest reported method instance by instance, including exact methods where available.
  • Main findings: Level-2 algorithms often perform nearly as well as level-1 solutions while producing reusable structure for entire problem classes.The strongest generated procedures use recognizable OR ideas, including projected inventory statistics, exact and local-search routines, and pressure-based scheduling.
  • Model comparison: Performance differs substantially among models released within eight months, especially at level 2.The deterministic inventory results show gpt-5.1 farther from benchmarks, while gpt-5.4 is closer but retains visible gaps.
  • Limitations: The evidence is empirical and limited to three OR settings, with unknown robustness outside tested instance families and no approximation guarantees.The authors also cannot rule out benchmark-specific information in model training, and level-2 performance can depend on how broadly the problem class is defined.

2 Setup

The setup formalizes OR problem classes, instances, feasible solutions, and rewards, then defines where an LLM can enter the solution chain. Experiments compare instance-specific solutions with reusable algorithms under constrained, single-query prompting.

  • Problem classes and instances: A problem class C = (Θ, X, R) specifies parameters, feasible solutions, and deterministic rewards for each instance.Randomness, such as demand or customer choices, is folded into the reward through an expectation or long-run average.
  • Problem classes and instances: Solutions may be single choices, such as assortments, or sequential policies mapping states to actions.For sequential problems, the solution space is X(θ) = { π : S →A }.
  • Examples: Lost-sales inventory uses demand, lead time, costs, and order limits to define a policy over on-hand inventory and outstanding orders.Each period includes an arrival, a new order, demand realization, and lost unmet demand.
  • Examples: Assortment optimization under MMNL is single-shot: the solution is an assortment S with |S| ≤k, and reward is expected revenue.The model includes customer segments, segment weights, product utilities, prices, and a cardinality cap.
  • Levels of LLM invocation: Level 1 queries the LLM once per instance for a solution, whereas level 2 queries once per class for executable code mapping any instance to a solution.Level 2 is closer to standard algorithm design; level 0, which queries at every state, is not tested.
  • Experimental protocol: The experiments use one untuned, tool-using query with a fixed Python sandbox and compute budget, and returned code cannot call an LLM.Main results do not retry or select among repeated samples except for defective artifacts.

3 Inventory Experiments

The inventory experiments compare LLM-generated policies with tuned inventory heuristics across lost-sales, dual-sourcing, and multi-echelon settings. The strongest model performs near or above the best existing methods, including on exact and difficult long-lead-time cases, while level-2 algorithms reuse structure across instances.

  • Instances: The study uses lost-sales, dual-sourcing, and multi-echelon inventory settings from prior benchmark instances, focusing the main text on 26 lost-sales instances.The lost-sales cases include deterministic and stochastic lead times; dual-sourcing and multi-echelon results are deferred to the appendix.
  • Evaluation design: Level 1 queries one instance at a time, whereas level 2 uses one query per problem class to produce algorithms mapping instance parameters to ordering policies.Each query has a fixed Python sandbox budget, and level-2 algorithms are evaluated across their class rather than rewritten for each instance.
  • Benchmarks: Benchmark policies include base-stock, constant-order, capped base-stock, and mixed strategies, with free parameters tuned separately for each instance.The capped base-stock policy has a 2.33-approximation guarantee, while the mixed strategy randomizes between two adjacent integer order quantities.
  • Results: 23 of 26 instances were beaten by gpt-5.6-sol at level 1, while all 26 were within 0.5% of the best tuned benchmark.At level 2, two class-level algorithms beat the benchmark on 21 instances and remained within 0.5% on all 26.
  • Model comparison: Performance varies sharply across models: claude-fable-5 is strong but less reliable, gpt-5.4 is competitive mainly at level 1, and gpt-5.1 is worse at both levels.The models were released within less than eight months, providing a capability gradient across closely timed releases.
  • Efficiency: The level-2 deterministic algorithm takes 598 seconds for one class-level query, versus 2,248 seconds mean wall time for level-1 instance queries.After generation, the level-2 algorithm requires 3.0 seconds per instance on average, compared with 1.8 seconds of level-1 module-load time.
  • Results: The strongest models recover exact optima on short-lead-time cases and remain essentially optimal at level 2 when dynamic programming is feasible.The short-lead-time table uses the exact dynamic program as the comparator and treats matching within simulation noise as optimal.
  • Results: On the deterministic lead-time sweep, gpt-5.6-sol improves on the best tuned benchmark by 2.5% to 4.1% at every lead time.Its level-2 policy uses projected, risk-adjusted inventory based on recursively propagated mean and variance rather than raw inventory position.

4 Queueing Experiments

The queueing experiments evaluate LLM-generated policies on dynamic-programming-solvable networks and larger reentrant-line networks, using both instance-specific and class-level queries. Level-2 algorithms preserve most level-1 performance when the problem class is structurally specified, but a broad class description can produce weaker generic policies.

  • Instances: The benchmark contains criss-cross, N-model, and extended six-class reentrant-line queueing networks from prior work.The first two groups are small enough for dynamic programming; extended six-class networks are evaluated against PPO.
  • Experimental design: Level 1 uses one query per instance, whereas level 2 uses one query per structural class under fixed compute and execution budgets.A broad level-2 query instead describes the full multiclass-network class.
  • Evaluation: On seven DP-solvable instances, every returned policy is evaluated exactly; larger six-class networks are evaluated by steady-state simulation.The primary comparators are computed dynamic-programming optima for small instances and PPO for extended networks.
  • Level 1 results: At level 1, gpt-5.6-sol is essentially optimal on all seven DP-solvable instances and beats PPO on four of six extended networks.It ties one extended-network comparison and is 2.2% worse on the largest network, within PPO’s reported uncertainty.
  • Level 2 results: At level 2, structurally specified algorithms are essentially optimal on criss-cross and N-model networks, while one reentrant-line query beats PPO on five of six instances.Thus, class-level generation retains most level-1 performance for these structural classes.
  • Broad L2: A broad class-level query returns a competitive generic index-plus-pressure rule on extended networks but performs poorly on criss-cross and N-model instances.The results indicate that structurally specified classes let the model choose more appropriate topology-specific strategies.
  • Model comparison and algorithm structure: Across models, level-2 performance separates sharply: gpt-5.6-sol remains strong, whereas gpt-5.1 produces a static reentrant-line rule and unstable N-model policies.The returned algorithms use dynamic programming or approximate dynamic programming on small networks and pressure-type rules on larger ones.

5 Assortment Experiments

The assortment experiments test LLM solvers on hard MMNL, nested-logit, and constrained-MMNL benchmarks against established heuristics, learning methods, and optimization-based comparators. Strong level-2 solvers match the best existing methods on MMNL and constrained MMNL, while nested logit remains a difficult exception and MMNL results are limited by a two-type benchmark structure.

  • Benchmark classes: The experiments use three hard assortment classes: MMNL with a cardinality cap, nested logit, and MMNL with five general linear constraints.The benchmark includes 628 MMNL, 971 nested-logit, and 1,794 regenerated feasible constrained-MMNL instances for level 2.
  • Experimental design: The comparison includes revenue-ordered, alpha-phi, ADXOpt, NN + local search, Kunnumkal LP, and conic MIP methods according to the choice model.Each LLM is queried once per family and its solver is run on every instance in that family.
  • Results: On MMNL and constrained MMNL, the strongest LLM solvers essentially match the best existing method.The strong level-2 MMNL solvers are exact on the released benchmark, while gpt-5.6-sol matches the best existing method on every constrained-MMNL instance.
  • Nested logit: Nested logit is the exception: the strongest LLM solvers are within 0.1% of the best method on 87.4% of instances but lose on a hard tail.The comparator is already near-optimal, lying within 0.1% of an upper bound on 911 of 971 instances and within 0.5% on all instances.
  • Level comparison: For stronger models, level 1 and level 2 are essentially identical on the evaluated assortment subset.The main visible level-1 benefit is for gpt-5.1 on nested logit, where the within-0.1% share rises from 50.0% to 77.1%.
  • Two-type MMNL structure: All released MMNL instances have only two distinct product-utility vectors, making exact optimization easy when that structure is recognized.The LLM solvers exploit this structured benchmark, so the result does not establish performance on general MMNL.
  • Algorithm structure: The strongest generated assortment solvers combine exact branches, greedy and relaxation-based starts, local search, repairs, and occasional restricted exact subproblems.These portfolios use standard OR primitives rather than a single revenue-ordered or greedy rule.

6 Robustness and Sensitivity Checks

Robustness checks show that gpt-5.6-sol’s level-2 algorithms often remain strong without query-time computation, generalize to new instances, and are usually stable across repeated draws. The main exceptions are weaker zero-compute queueing results, difficult nested-logit tails, and occasional defective or non-evaluable artifacts.

  • 6.1 The role of query-time tools: Zero query-time compute leaves level-2 inventory and assortment performance largely intact, but harms level-1 inventory performance substantially.The zero-compute level-2 inventory algorithm beats the benchmark on all six lead-time instances, while five of six level-1 policies trail it by 3.5% to 13%.
  • 6.1 The role of query-time tools: Queueing is more mixed without query-time compute: the criss-cross artifact is essentially optimal, while the N-model is about 7% above optimum.On extended reentrant-line instances, zero compute remains usable but averages about 2.4% above the PPO comparator.
  • 6.1 The role of query-time tools: Adding unlimited web search does not change the tested level-2 results across deterministic lost sales, MMNL, nested logit, and constrained MMNL.The model used web search only briefly for literature checking or not at all.
  • 6.2 Generalization to new instances: gpt-5.6-sol beats the best tuned benchmark on every deterministic and stochastic inventory holdout instance.Older models are less robust: gpt-5.4 is modestly worse on most holdout cells, while gpt-5.1 fails badly on deterministic holdouts.
  • 6.2 Generalization to new instances: Assortment holdouts support generalization beyond published benchmark structure, with all frozen MMNL artifacts matching the comparator throughout the generated instances.Stronger models also match the multistart local-search comparator throughout the nested-logit holdout, whereas gpt-5.1 is weaker.
  • 6.3 Sensitivity to repeated draws: Repeated draws are usually stable, but five of 97 fail under evaluation, and multi-echelon inventory varies by 6.8 percentage points.Seven of nine additional N-model draws complete evaluation; five are within 2% of optimal and two exceed the evaluation hang guard.
  • 6.3 Sensitivity to repeated draws: Near-optimal repeated draws sometimes overrun the nominal 30-second design target by factors of 2 to 18, while hard-deadline draws sacrifice accuracy unnecessarily.The reported failure is attributed to treating a soft runtime target as a hard constraint, not to inability to design the right algorithm.

7 Conclusion

The paper concludes that a general-purpose LLM can produce high-performing algorithms for several hard, well-specified OR benchmarks, including transferable level-2 procedures. It also emphasizes that real operations work extends beyond algorithm design and that the generated methods may depend on recombining existing OR knowledge.

  • 7 Conclusion: Across inventory, queueing, and assortment benchmarks, the strongest model matches or outperforms the best existing method on nearly all evaluated instances.The level-2 result concerns procedures that transfer across many instances rather than solutions for only one instance.
  • 7 Conclusion: The generated algorithms often combine familiar OR ideas such as capped base-stock policies, small-state dynamic programs, pressure-based scheduling, and local search.The paper states that how much performance depends on exposure to existing OR literature remains unknown.
  • 7 Conclusion: The study isolates algorithm design, while formulation, measurement, validation, deployment, and objective trade-offs remain part of real operations problems.Its conclusion is limited to the well-specified benchmark problems studied.
  • 7 Conclusion: The experiments use four named models, fixed sandbox budgets, and a 30-second per-instance setup target for returned level-2 algorithms.All local computation and evaluation ran on one Apple M2 Pro laptop using Python 3.10, NumPy 1.24, and SciPy 1.10.
  • 7 Conclusion: Comparisons use the best existing method on each instance, with common-random-number simulation for inventory and exact or simulation-based evaluation for queueing.LLM solutions never enter the comparator.

B.1 Validation

The appendix validates simulators and benchmark implementations before reporting inventory results. Exact dynamic programs, source-paper reproduction, internal simulator checks, and separate tuning and scoring streams support the reported comparisons.

  • B.1 Validation: Inventory policies are validated before scoring, including simulator and benchmark implementation checks.The validation appendix covers additional inventory settings, full lost-sales results, and timing results.
  • B.1 Validation: Benchmark parameters are tuned by simulation, with candidate searches followed by refinement around the winner.Final scoring uses random-number streams separate from benchmark tuning streams.
  • B.1 Validation: Short-lead-time lost-sales simulation matches the dynamic program within simulation error, with cost differences of at most 0.009 on costs of order five.The stochastic lead-time simulator is additionally checked against the degenerate deterministic case, Little’s law, and realized lead-time distributions.
  • B.1 Validation: Tuned dual-sourcing benchmarks reproduce the source paper’s Figure 9 within a hundredth of a percentage point for all but two of 18 policy-instance pairs.The dual-sourcing results compare LLM policies with the exact optimum for six instances.
  • B.1 Validation: Multi-echelon validation uses an exact line-by-line transcription check and a limiting parameter regime because published numbers are unavailable for direct reproduction.The multi-echelon system has one warehouse supplying ten stores, with stochastic demand and special delivery.
  • B.1 Validation: Multi-echelon demand is rounded normal, truncated below at zero, and exact optimization is intractable in that system.The appendix retains the printed second-setting value µ = 0; truncation leaves a positive effective demand mean.

B.4 Per-instance inventory results

The per-instance inventory appendix reports directly comparable level-1 and level-2 results against the same tuned benchmarks and simulation streams. Gaps are expressed relative to the best existing method, with negative values favoring the LLM.

  • B.4 Per-instance inventory results: Table 12 reports 20 remaining lost-sales instances across four models at level 1 and each model’s two level-2 algorithms.Policies within each row use identical demand and lead-time streams and the same tuned benchmark.
  • B.4 Per-instance inventory results: Percentage gaps are measured against the best existing method, with negative values indicating lower LLM cost.For short lead-time and dual-sourcing rows, the comparator is the exact dynamic program; for Table 12 and multi-echelon rows, it is the best tuned benchmark.

B.5 Compute and wall time

The appendix distinguishes wall time, sandbox compute, and evaluation-time setup, showing that level 1 often spends substantial compute tuning instance-specific policies while level 2 shifts work to per-instance design calls.

  • Timing measures: Three clocks separate prompt-to-answer wall time, metered sandbox execution, and evaluation-time setup for returned artifacts.At level 2, setup is design(θ) per instance; at level 1, it is module-load time.
  • Inventory compute: Level 1 uses 1,959–2,841 seconds on lost-sales and multi-echelon inventory classes, with several queries reaching the 3,600-second cap.These policies require simulation-based tuning, unlike the dual-sourcing class.
  • Inventory compute: Level 2 uses 18–237 seconds of sandbox compute and defers computation to design(θ), which takes 3–13 seconds per evaluation instance.The sandbox budget is 3,600 seconds.
  • Timing tables: The timing tables report one class-level level-2 query per inventory row and one level-1 query per instance, including output and setup measurements.The level-1 table summarizes distributions across instances, while the level-2 table reports class-level queries.

C.2 Simulation and comparator validation

Queueing validation combines exact relative-value-iteration evaluation on seven small instances with steady-state simulation on six larger networks, using PPO as the primary comparator for the latter.

  • Exact evaluation: Seven DP-solvable criss-cross and N-model instances receive exact optima and exact policy gaps through relative value iteration on truncated uniformized chains.Evaluating the optimal policy reproduces each optimum within 10^-10.
  • Simulation protocol: Six extended six-class networks use 20 independent simulation runs with 2 × 10^6 post-warm-up events after a 2 × 10^5-event warm-up.Common random numbers are used across policies.
  • Comparator validation: PPO is the primary comparator on extended networks, with reported costs of 14.13, 23.27, 32.17, 39.30, 51.47, and 55.12.The corresponding confidence intervals range from about 0.2 to 1.8; LBFS and cµ are secondary checks.
  • Robustness checks: The level-1 comparison agrees with the steady-state results under QGym’s finite-horizon protocol, which starts empty and averages 100 trajectories.Stability draws use a lighter simulation protocol and are reported as robustness checks.
  • Compute use: Queueing level-1 generation uses 45–1,558 sandbox seconds on criss-cross, 2,024 seconds on the N-model, and usually most of 3,600 seconds on extended networks.Level-2 artifacts use 841, 58, and 208 seconds for the three queueing groups, respectively.

D Additional assortment results

Additional assortment analyses document instance coverage and use a stratified level-1 set because that setting requires one query per evaluated instance.

  • Instance selection: All 628 MMNL and 971 nested-logit instances are scored for every method, while constrained MMNL uses a 1,800-instance grid after removing six degenerate cases.A small number of individual entries are also excluded when solver revenues exceed verified exact optima.
  • Level-1 set: The level-1 assortment set contains 72 MMNL, 48 nested-logit, and 36 constrained-MMNL instances selected from the lowest seeds.The selection uses one lowest-seed instance per released MMNL and nested-logit configuration and two lowest seeds per constrained-MMNL configuration.
  • Level-1 results: Figure 9 presents level-1 assortment results on the stratified instance set using the comparator, axes, and conventions of Figure 6.It is the one-query-per-instance counterpart to Figure 6.

D.1 Compute and wall time

Assortment timing is reported through query wall time, sandbox execution, and returned-solver runtime, with level 2 generally shifting work into fast evaluation calls.

  • Timing measures: Three clocks measure assortment query wall time, sandbox Python time, and level-2 returned-solver runtime per evaluation instance.The level-2 table also reports mean and maximum solver runtime by family.
  • Level-2 compute: Level-2 assortment queries use about 100–120 seconds of the 3,600-second sandbox budget, while returned solvers usually run in well under one second per instance.Zero-compute queries take about four minutes of reasoning and produce solvers of similar speed.
  • Level-1 compute: Level-1 assortment queries are usually about a minute, with a few MMNL and nested-logit queries using most of the 900-second sandbox budget.The level-1 timing table reports distributions across the stratified instance set.

E Holdout generalization results

The holdout evaluation tests frozen level-2 algorithms on newly constructed inventory and assortment instances, including parameter regimes beyond the main benchmarks.

  • Holdout design: The holdout evaluates frozen level-2 artifacts on new inventory and assortment instances without querying the model again.The inventory holdout includes deterministic and stochastic lost-sales instances; assortment holdouts use MMNL and nested-logit regimes.
  • Inventory holdout: The lost-sales holdout spans 30 deterministic and 12 stochastic instances with varied lead times, demand means, and penalty costs.
  • Assortment holdout: MMNL holdouts vary product counts, classes, assortment caps, utility regimes, and random seeds across exact and large subsets.
  • Assortment holdout: Nested-logit holdouts vary products per nest, numbers of nests, per-nest caps, dissimilarities, utilities, prices, and cross-nest regimes.

F Adding a web-search tool

Adding web search leaves the reported algorithmic results essentially unchanged, although this check is limited and substantially increases generation time.

  • Setup: The four level-2 reruns used the same prompt and 3600-second Python budget, with web search added as the only tool change.
  • Tool usage: All web searches occurred at the start of sessions, before code was written, and the model used the tool sparingly.
  • Results: Deterministic lost sales achieved a mean gap of −1.26% with web search versus −1.27% for the main artifact.
  • Results: MMNL remained optimal on all 628 instances, constrained MMNL matched the best existing method on all 1,794, and nested logit matched the main artifact.
  • Caveat: The check used one model and one artifact per class, while web search substantially increased wall-clock generation time.

G How the model reasons

The model’s process combines literature-informed formalization, candidate-family comparison, computation budgeting, testbed construction, and explicit guardrails before finalizing the required interface.

  • Overall pattern: Across transcripts, the recurring pattern is structure identification, algorithm-family comparison, computation budgeting, testbed construction, guardrails, and contract-compliant code.
  • Formalize the problem and recall what is known: The model typically begins by formalizing the problem and recalling a relevant structural result or known algorithmic idea.
  • Enumerate candidate method families and weigh exactness against cost: It compares exact methods, simple policies, and hybrids while weighing solution quality against computational cost.
  • Budget the computation: It budgets computation against the stated 30-second per-instance target and sandbox capabilities.
  • Build a testbed and benchmark against ground truth: The model builds simulators, brute-force checkers, dynamic programs, or internal testbeds and uses exact small cases as yardsticks.In dual sourcing, the returned algorithm retains the exact dynamic program when the state space is small enough, attaining the exact optimum on all six instances.
  • Hunt for failure modes and add guardrails: Later checks add explicit branches for edge cases, overflow, feasibility repair, and degenerate inputs.
  • Finalize to the contract: The final returned code must define the required function signature, return feasible integer orders, and avoid expensive optimization inside each simulated-period call.
Loading 2608.27296v1…