MAPLE: Memory-Augmented Planning with Language and Evolution

Operational plans often need to be revised as requirements change over time. Responding to these changes requires updating the underlying optimization problem, preserving decisions that users wish to keep, and deciding whether to reuse previous solutions as starting points or search from scratch. We introduce MAPLE (Memory-Augmented Planning with Language and Evolution), an agent for optimization under changing requirements expressed in natural language. MAPLE constructs the initial optimization problem through a typed program interface and solves it with numerical solvers. For each subsequent request, it revises and solves the current problem, uses records of prior requests and a saved plan to identify and preserve decisions that users ask to keep, and selectively reuses previous solutions to initialize the new search. To evaluate agents under changing requirements, we introduce NLDO, a benchmark of 15 planning tasks, each followed by 12 natural-language updates, spanning five task types: resource selection and allocation, production scheduling, staff scheduling, delivery route planning, and computing task allocation to servers. In the main evaluation, MAPLE completes all 15 task sequences, achieving mean online single-objective quality of 0.951 and a mean Pareto hypervolume ratio of 0.875 across initial and updated task states.