Structure-Aware Primal–Dual and Large-Neighborhood Search in an LLM-Configured Optimization Agent

We study large-scale promotion optimization across multiple markets on Alibaba's e-commerce platform, where high-quality feasible policies must be generated within a short operational time window. Subsidies affect demand exponentially, tiered coupon rules induce price discontinuities, and decisions are coupled through complex constraints involving budgets, subsidies, cross-market consistency, and priority orderings among merchandise groups. We develop a portfolio of two complementary structure-aware methods. A primal–dual (PD) method relaxes shared constraints, yielding independent multi-market subproblems for individual products, and recombines their solutions to recover a feasible policy. An adaptive large neighborhood search (LNS) method jointly updates products linked by tight budget or group-priority constraints, enabling coordinated moves across coupon thresholds that can be difficult to achieve through multiplier updates alone. We further embed the portfolio in an optimization-agent framework, where an LLM selects hyperparameters from finite predeclared sets based on a numerical summary of each instance, after which both PD and LNS are executed and the better feasible solution is returned. Theoretically, we establish exact product-wise separability of the primal–dual relaxation and develop a branch-and-bound algorithm that globally solves each product-level subproblem with an optimality certificate. On a 72-instance test suite spanning six structural families and problem sizes $N$ from 100 to $10^5$ products, our portfolio returns a feasible policy for every instance under a 900-second time budget per method, whereas Gurobi finds an incumbent for only 33 instances. On these 33 common-feasible instances, the portfolio's mean objective shortfall relative to Gurobi is only 0.0094%. The scalability advantage becomes more pronounced on larger instances: for the 36 instances with $N\ge 10^4$, the portfolio returns a feasible policy on all 36, whereas Gurobi finds an incumbent on only 6; for the 18 instances with $N\ge 5\times 10^4$, the corresponding counts are 18 and 1, respectively.