PaperlayerView exact revision on arXiv

Source-linked AI summary

MAPLE: Memory-Augmented Planning with Language and Evolution

Kesheng Chen, Yamin Hu, Wenjian Luo

arXiv:2609.11636v1cs.AI

TL;DR

Dynamic operations require optimization systems to adapt natural-language revisions while preserving earlier decisions and useful search state. MAPLE maintains executable optimization state across such requests and evaluates it with the NLDO benchmark. It completes all trajectories, achieving online scalar quality of 0.951 and Pareto hypervolume ratio of 0.875.

  • Problem

    Existing optimization agents translate natural-language requirements into executable models, but dynamic operations require updates that preserve earlier decisions and reuse useful search results.

  • Method

    MAPLE maintains the optimization program, accepted plans, earlier updates, and candidate solutions while combining mathematical programming with evolutionary and Pareto search.

  • Results

    MAPLE completes all NLDO trajectories, achieving online scalar quality of 0.951 and Pareto hypervolume ratio of 0.875.

  • Takeaways & Limitations

    Controlled comparisons show that persistent executable state improves continuity and validity while allowing useful search information to survive substantial revisions.

  • Takeaways & Limitations

    MAPLE relies on a fixed catalog of decision types, solver routes, and restart actions, and new decision types or numerical operators require runtime extensions.

Abstract

from arXiv · show

Domain practitioners understand their business constraints but may lack operations-research expertise or dedicated support. LLM-based optimization agents translate natural-language requirements into models or solver programs that established optimization tools can execute. This progress makes optimization more accessible, but real-world operations are dynamic: changing demand, resources, and priorities require updates to data, constraints, and objectives. Methods centered on isolated requests offer limited support for rapid adaptation that preserves earlier decisions and reuses useful search results. We introduce MAPLE (Memory-Augmented Planning with Language and Evolution), an agent for maintaining optimization problems through successive natural-language requests. MAPLE combines language-based problem construction with mathematical programming and evolutionary search. It retains the optimization program, accepted plans, earlier updates, and candidate solutions for subsequent requests. We introduce NLDO, a benchmark of 15 trajectories and 180 updates spanning selection, scheduling, rostering, routing, and cloud-resource placement. In the main evaluation, MAPLE completes all trajectories and achieves online scalar quality of 0.951 and a Pareto hypervolume ratio of 0.875. Controlled comparisons further show that maintaining executable state improves update validity and can preserve useful search information across substantial revisions.

1 INTRODUCTION

MAPLE addresses live dynamic optimization by maintaining executable optimization state across successive natural-language revisions. On NLDO, it completes all trajectories while achieving strong scalar and Pareto quality, and controlled comparisons examine the value of persistent state.

  • MAPLE targets operations that require revising programs, recovering earlier assignments, and assessing whether previous candidates remain useful.These needs arise because demand, resources, and priorities change over time.
  • The paper formulates live dynamic optimization as cumulative natural-language revisions and introduces NLDO alongside MAPLE’s executable-state architecture.
  • The system maintains an executable optimization program, input data, accepted plans, update records, and candidate solutions for later requests.Its components support mathematical programming, evolutionary search, and Pareto search.
  • MAPLE completes all 15 NLDO trajectories, reaching online scalar quality of 0.951 and Pareto hypervolume ratio of 0.875.NLDO covers 180 updates across selection, scheduling, rostering, routing, and cloud-resource placement.
  • NLDO evaluates trajectory continuity separately from resulting-plan quality, while component and restart controls examine validity, historical grounding, and search reuse.

2 TASK AND BENCHMARK

NLDO models planning as a sequence of natural-language requests that progressively define feasible sets and objectives. It evaluates both continuity of accepted trajectories and the quality and feasibility of saved plans across 15 benchmark trajectories.

  • Task formulation: Each episode starts with an initial request and input tables, followed by revisions that define time-indexed feasible sets and objective vectors.Single-objective tasks seek one feasible plan, whereas multi-objective tasks seek mutually nondominated plans representing trade-offs.
  • State and history: MAPLE stores input tables, the optimization program, accepted output, candidate solutions, and earlier update records as evolving state.An accepted update extends event history, while a rejected revision leaves the committed state and history unchanged.
  • Evaluation: The benchmark separates protocol continuity from saved-plan quality, scoring trajectory prefixes, feasibility, normalized scalar quality, and Pareto hypervolume.The first recorded rejection ends the eligible prefix and gives remaining states zero continuity and quality scores.
  • NLDO coverage: NLDO contains 15 trajectories and 180 updates across five task families, with single- and multi-objective initial states and complete trajectories.The benchmark includes selection, scheduling, rostering, routing, and cloud-resource placement, with 195 total states.

3 METHOD

MAPLE constructs an executable optimization state and revises it through localized edits, historical bindings, typed search, restart selection, and fixed validation gates. Its runtime commits valid revisions while rejecting failures and preserving the preceding state.

  • State revision: MAPLE revises executable state by locating edits, resolving accepted-history references, selecting warm or full restarts, and validating outputs before commitment.Valid revisions commit updated data, programs, plans, and search state; failures preserve the preceding state.
  • Initial construction: TSS binds model-declared decision types and evaluation functions to fixed initialization, variation, repair, solver, and search operations.Typed candidates can include binary, categorical, bounded integer or real, permutation, and assignment segments.
  • Initial construction: Figure 2 separates model-authored problem construction from fixed execution: the model builds W0 from D0, while TSS and NSGA-II produce P0 and A0.
  • Localized updates: LPD applies localized data or Workbench edits, while LSM retrieves accepted assignments and enforces resolved historical bindings during search.A price change may update tables alone, whereas a new constraint may require editing evaluation logic.
  • Validation and commitment: Figure 3 shows that compilation and public-test failures trigger bounded repair, invalid search outputs reject updates, and valid outputs commit state and history.
  • Restart selection: The restart selector verifies whether proposed reuse risks match supported structural causes and changed fields before choosing Full rather than Warm.Warm migrates and repairs part of the prior population, whereas Full initializes every candidate afresh.

4 EXPERIMENTS

MAPLE is evaluated on initial optimization, sequential revision, executable-state scaffolding, historical grounding, and search reuse. It completes every trajectory and substantially outperforms Persistent ReAct on strict-prefix scalar and Pareto quality, while controlled tests isolate benefits from TSS and reuse.

  • 4.1 Q1: CAN THE AGENT SOLVE THE INITIAL REQUEST?: MAPLE’s initial states achieve scalar quality of 1.000 and Pareto HV of 0.832, with execution rates of 59.3% on NLP4LP-hard and 80.0% on BWOR20.The initial-request evaluation reports both program execution and reference-objective agreement.
  • 4.2 Q2: CAN THE AGENT FOLLOW A SEQUENCE OF REVISIONS?: MAPLE completes every trajectory, reaching strict-prefix online quality of 0.951 on scalar tasks and 0.875 HV on Pareto tasks, versus 0.501 and 0.042 for Persistent ReAct.Persistent ReAct’s scores rise to 0.763 and 0.185 when mathematically feasible plans are accepted despite auxiliary-field failures, while MAPLE remains unchanged.
  • 4.3 Q3: WHAT HELPS THE AGENT HANDLE REVISIONS CORRECTLY?: TSS raises Pareto-update feasibility from 80.6% to 100.0% and mean HV from 0.665 to 0.879 over six NLDO-DM episodes.Without TSS, 140 of 720 update–seed outputs are invalid, including missing routing and GPU-compatibility checks.
  • 4.3 Q3: WHAT HELPS THE AGENT HANDLE REVISIONS CORRECTLY?: LSM resolves all 18 assignment requests only when it combines earlier update records with accepted plans; either partial source alone resolves only its six directly answerable requests.The requests include preserving a customer’s vehicle assignment identified through a prior congestion note.
  • 4.4 Q4: WHEN SHOULD SEARCH REUSE PREVIOUS SOLUTIONS?: MAPLE and Always Warm both score 0.915 on the first ten updates, while after disruptive replacements MAPLE scores 0.696 versus 0.636 for Always Warm.The gains are concentrated in routing, and MAPLE selects Full after the substantial late changes.
  • 4.4 Q4: WHEN SHOULD SEARCH REUSE PREVIOUS SOLUTIONS?: Across six sequences, MAPLE’s paired gain over Always Warm is 0.010, with five positive episode differences and a bootstrap interval of [0.001, 0.021].The exact sign test gives p = 0.219, and the gain is concentrated in routing.

5 RELATED WORK

Related work spans natural-language optimization, interactive language agents, and dynamic numerical optimization. MAPLE combines these directions by retaining executable optimization state while revising problems through language, and NLDO evaluates continuity alongside solution quality.

  • Natural-language optimization for domain practitioners: Natural-language optimization methods translate language into programs or solver workflows, while MAPLE extends them to continued revision as operations change.The related methods include NL4Opt, execution-feedback optimization agents, MIRROR, and ORPilot.
  • Interactive and dynamic language agents: Interactive agents retain dialogue, experience, or prior information, whereas MAPLE retains executable optimization state and NLDO evaluates continuity and solution quality across revisions.The comparison includes multi-turn planning and asynchronous environment-change benchmarks.
  • Multi-objective and dynamic numerical optimization: Dynamic optimization studies repair, transfer, and restart under changing objectives or constraints; MAPLE revises executable problems through language before applying established solvers such as NSGA-II.This connects language-mediated problem revision with established multi-objective search procedures.

6 CONCLUSION

MAPLE maintains executable optimization state across natural-language revisions and completes all NLDO trajectories. The evaluation uses synthetic data, with reproducibility materials provided in the supplement.

  • MAPLE completes all 15 NLDO trajectories, achieving online scalar quality of 0.951 and Pareto HV of 0.875.
  • Persistent executable state supports update continuity, while controls show that TSS reduces invalid outputs and historical requests may require both update records and accepted plans.
  • NLDO uses synthetic data, with tasks, prompts, settings, seed-level evidence, and offline scoring references supplied separately from agent inputs.

A APPENDIX

The appendix organizes definitions, execution details, supplementary experiments, and reproducibility materials. It also provides an appendix-content map for locating evidence.

  • The appendix first defines mechanisms, metrics, and execution setup before presenting supplementary experiments.
  • The Harness walkthrough follows the results, while prompt interfaces and recorded benchmark requests appear last.
  • Table 5 maps appendix contents to their corresponding evidence locations.

A.1 MAPLE INITIALIZATION AND UPDATE PROCEDURE

MAPLE initializes an executable Workbench and updates only the data or functions affected by later requests. It combines typed scaffolding, conditional language-model edits, fixed optimization, and executable-state reuse.

  • LPD identifies whether revised input data or Workbench functions must change, while TSS checks the editable functions before optimization proceeds.
  • The saved state includes data, the Workbench, accepted plans, and candidate populations or archives, with the LP/MILP path not using a population.
  • Language-model calls are conditional on requested data translation, function editing, or repair, and restart assessment uses update history and the change digest before population construction.

A.2 CHECKS FOR RESTART RECOMMENDATIONS

MAPLE’s restart procedure combines model recommendations with fixed structural checks before choosing reuse or a fresh start. The update pipeline preserves unaffected Workbench functions and validates candidate edits before execution.

  • Fixed checks determine whether a response satisfies the conditions for a fresh start after the model proposes candidate reuse.
  • Parsing normalizes risk strings, removes unrecognized mechanisms and duplicate paths, and retains cited paths only when they belong to the changed-field set.
  • Initialization compiles and tests the candidate Workbench, permits at most B repair attempts after public errors, and commits no state if checks still fail.
  • Updates copy the accepted Workbench and edit build_problem() for decision or data changes and evaluate() for evaluation, constraint, decoding, or reporting changes.
  • The restart gate requires high risk, a Full vote, and at least one cited changed path in addition to structural support.
  • Ordinary parsing or provider errors return Warm, while detected quota-limit errors are passed back to the caller.

A.3 TSS WORKBENCH AND AVAILABLE CHOICES

The TSS Workbench is a reusable optimization program whose fixed runtime exposes typed decision and solver choices while the model edits problem and evaluation functions. Warm repairs and reuses historical candidates, whereas Full search can restart with fresh candidates.

  • TSS Workbench and available choices: The model’s decision-definition function reads public tables, declares typed decisions, chooses the solver, and names outputs; its evaluation function checks candidates against constraints and objectives.
  • TSS Workbench and available choices: TSS rejects unsupported decision spaces, preserves objective mode, and Warm migrates, repairs, re-evaluates, deduplicates, and supplements historical candidates before search.For multi-objective tasks, seed ordering includes objective extremes, knee candidates, and nondominated selection with crowding.
  • TSS Workbench and available choices: Workbench revisions can change public data or route evaluation, while the runtime’s evolutionary loop evaluates repaired seeds before filling remaining population slots with fresh candidates.Historical candidate reuse adds evaluation work before the shared evolutionary loop.
  • TSS Workbench and available choices: The Workbench-building model selects decision types and a solver route, while fixed runtime code supplies checks, operators, and restart actions.The model writes the decision-definition and evaluation functions within this boundary.

A.4 LIMITATIONS AND ETHICS

MAPLE’s scope is constrained by its fixed runtime catalog, model-dependent interpretation and feasibility checks, finite search budgets, and deployment-safety requirements. The authors position it for batch or human-supervised re-optimization rather than unrestricted autonomous operation.

  • Limitations and ethics: Tasks requiring a new decision type or numerical operator need a runtime extension because MAPLE relies on a fixed catalog of supported choices.
  • Limitations and ethics: Historical grounding and semantic restart decisions depend on the model interpreting references, unspecified constraints, and update meaning correctly.Clarification is needed when a request could refer to several earlier entities or leaves a constraint unspecified.
  • Limitations and ethics: Evolutionary routes operate within finite budgets, and repairing retained candidates adds latency before search, affecting the choice between reuse and fresh initialization.
  • Limitations and ethics: Generated Python currently runs in the application process, so operational deployment requires stronger isolation and high-impact decisions should support inspection, approval, and rollback.The intended use is batch or human-supervised re-optimization.

A.5 METRIC DEFINITIONS

NLDO scores scalar and Pareto outputs using feasibility-aware, normalized measures over sequential states. The evaluation separates mathematical validity from protocol eligibility and uses withheld reference archives for multi-objective comparison.

  • Metric definitions: Scalar quality is normalized against an exact or best-known reference: infeasible outputs receive zero, reference-matching outputs receive one, and values lie in bounded 0–1 tables.Online quality averages state quality, with infeasible and unsolved states contributing zero.
  • Metric definitions: Dynamic evaluation separates solve rate from online quality, with rejected or ineligible states ending the accepted prefix and unattempted states remaining in the denominator.MAPLE averages quality across ten search seeds at each state and then across states.
  • Metric definitions: Pareto evaluation compares each submitted archive with a withheld feasible reference archive, using fixed ideal and reference points shared by all methods at that state.Reference archives pool ten independent runs, each with population 500 and 500 generations, before nondominated filtering.
  • Metric definitions: Hypervolume ratio is computed after removing infeasible candidates and normalizing within a unit box; IGD and ideal gap provide additional Pareto measures, with smaller ideal gap preferred.Dominated or duplicate points add no hypervolume, and an archive without a feasible candidate receives zero HV ratio.

A.6 BENCHMARK AND EVALUATION DETAILS

NLDO organizes dynamic optimization evaluation across multiple problem families, domains, and static or dynamic views. The benchmark combines public scoring formulas with annotations for updates, retained information, and trajectory continuity.

  • Benchmark coverage: NLDO covers five problem families across selection, scheduling, rostering, routing, and cloud-resource placement, with compact, larger, and Pareto task profiles.Compact scalar tasks use exact references, larger scalar tasks use best-known solutions, and Pareto tasks use held-out archives.
  • Benchmark views: The benchmark provides four views spanning static and dynamic single- and multi-objective settings, with dynamic views including initialization.Update-only analyses exclude the initial state and are labeled separately.
  • Update design: Thirty of 180 updates require information from earlier requests, while rostering, routing, and cloud placement each contribute six disruptive t11–t12 states.All table changes retain the initial columns and listed decision entities.
  • Evaluation protocol: Evaluation distinguishes optimization objectives, hard constraints, and auxiliary diagnostics while supplying cumulative updates, validation feedback, and retained method state.The framework defines feasible plans and, for multi-objective tasks, mutually nondominated plan sets representing trade-offs.
  • Scoring: Saved routes and assignments are rescored with public formulas, replacing hidden evaluator behavior that introduced route multipliers, undeclared emissions, or order-dependent cloud energy.The public cloud formula makes energy invariant to key order, whereas the original hidden rule produced 26 or 30 instead of 17 before global scaling in the stated example.

A.7 STATIC SOLVING SETUP

The static supplement measures one-shot language-to-optimization performance on NLP4LP-hard and BWOR20. It evaluates executable programs using execution, reference-objective agreement, and joint diagnostic checks.

  • Static setup: The static benchmark contains no updates, memory, restart choice, or predecessor population, isolating ordinary one-shot optimization from language.Each case provides problem text and public parameters, and methods produce executable Python solver code.
  • Primary metrics: Execution rate and Objective agreement measure whether programs run and whether returned objectives match references within benchmark-specific tolerances.Objective agreement accepts alternative optimal decision vectors and uses 10^-6 absolute and relative tolerances for NLP4LP-hard, while BWOR20 uses 0.1 absolute and zero relative tolerance.
  • Diagnostics: Joint Match combines compilation, execution, and reference-objective or status-only agreement, with every benchmark case included in its denominator.The tables retain separate compilation, execution, objective, and workflow-specific checks, which may overlap.
  • Case selection: NLP4LP-hard contributes 59 retained instances with nonempty reference solutions from a 361-instance snapshot, while BWOR20 is a fixed released-dataset subset.The retained NLP4LP-hard references use objectives from the supplied solution records.

A.8 BASELINE INTERFACES AND EXECUTION

Persistent ReAct carries solver code, accepted answers, and cumulative history across updates, then revises and executes the program in response to new requests. Runtime feedback supports up to three code-output repairs after compilation, runtime, or formatting failures.

  • Baseline interface: Persistent ReAct retains preceding solver code and accepted answers, editing the program for each subsequent request as a stateful ReAct control.At initialization it writes a complete Python solver using public parameters and solver libraries.
  • Update execution: Each update supplies the initial tables, cumulative dialogue, and carried workspace, after which the revised program is executed and its printed solution is read.The workspace also contains a separate history field with the preceding plan and cumulative updates.
  • Execution and repair: Compilation, runtime, or solution-format failures trigger error feedback and at most three code-output repairs, while reasoning and tool-plan fields remain auxiliary.Nothing is carried at initialization, and the cross-stage workspace retains code and answers without a separate population or Pareto archive.

A.9 NUMERICAL SETTINGS AND RELEASED MATERIALS

MAPLE’s numerical studies compare adaptive restart and search-state reuse against fixed policies and controls, showing gains concentrated in disruptive routing updates while archive-size effects are small on average.

  • Aggregate results: 0.875 overall HV versus 0.866 for own-history Warm and 0.825 for own-history Full.Adaptive reuse helps routing, while Full is slightly stronger in cloud placement.
  • Historical grounding: 100% of benchmark updates are resolved when earlier requests and accepted plans are available for reference.LSM resolves all 30 entity references, including six requiring three historical links; neither source alone resolves requests requiring both.
  • TSS controls: 0.669 routing and 0.728 cloud online quality with TSS versus 0.336 and 0.513 without TSS.All three typed routing runs remain valid, while two additional typed cloud runs fail held-out checks at t11–t12.
  • Restart comparisons: 0.013 normalized HV improvement over Matched Warm on P010–P015, with all six episode means favoring MAPLE.The gain is concentrated at t11–t12, and MAPLE uses 162.8 generations versus 199.0 for Matched Full.
  • Domain breakdown: 0.122–0.168 HV gains over Matched Warm occur across routing episodes P010–P012, compared with 0.002–0.011 in cloud episodes.These results localize the benefit of fresh initialization to disruptive routing updates.
  • Archive sensitivity: 0.775, 0.776, and 0.774 mean HV ratios result from archive limits of 100, 200, and 500, respectively.The mean changes by at most 0.0016, although smaller archives alter individual fronts and require more generations.
Loading 2609.11636v1…