A Re-Solving Heuristic for Dynamic Assortment Optimization With Knapsack Constraints

• 成果类型: Article
• 署名作者: Chen, Xi; Liu, Mo; Wang, Yining; Zhou, Yuan
• 署名单位: New York University; University of North Carolina; University of North Carolina Chapel Hill; University of Texas System; University of Texas Dallas; Tsinghua University
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• DOI: 10.1177/10591478251399005
• 发表日期: 2026
• 关键词: Network Revenue Management; choice model; inventory; algorithm; POLICY

摘要

In this article, we consider a multi-stage assortment optimization problem with multinomial logit (MNL) choice modeling under resource knapsack constraints. Given the current resource inventory levels, the retailer makes an assortment decision at each period, and the goal of the retailer is to maximize the total profit from purchases. With the exact optimal dynamic assortment solution being computationally intractable, a practical strategy is to adopt the re-solving technique that periodically re-optimizes deterministic linear programs (LPs) arising from fluid approximation. However, the fractional structure of MNL makes the fluid approximation in assortment optimization non-linear, which brings new technical challenges. To address this challenge, we propose a new epoch-based re-solving algorithm that effectively transforms the denominator of the objective into the constraint, so that the re-solving technique is applied to a linear program with additional slack variables amenable to practical computations and theoretical analysis. Theoretically, we prove that the regret (i.e., the gap between the re-solving policy and the optimal objective of the fluid approximation) scales logarithmically with the length of time horizon and resource capacities.