# A Re-solving Heuristic for Dynamic Assortment Optimization with Knapsack Constraints

arXiv: https://arxiv.org/abs/2407.05564 · HTML: https://mlsanity.com/paper/2407.05564/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 65 references that are in the map.
- First posted on arXiv 8 Jul 2024.

## Builds on (most cited first, 13 of 13)

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits](https://mlsanity.com/paper/1504.06937/) (2015)
- [Dynamic Assortment Optimization with Changing Contextual Information](https://mlsanity.com/paper/1810.13069/) (2018)
- [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [Online Allocation and Pricing: Constant Regret via Bellman Inequalities](https://mlsanity.com/paper/1906.06361/) (2019)
- [A Note on a Tight Lower Bound for MNL-Bandit Assortment Selection Models](https://mlsanity.com/paper/1709.06109/) (2017)
- [Multi-stage and Multi-customer Assortment Optimization with Inventory Constraints](https://mlsanity.com/paper/1908.09808/) (2019)
- [Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources](https://mlsanity.com/paper/2002.02430/) (2020)
- [An Optimal Policy for Dynamic Assortment Planning Under Uncapacitated Multinomial Logit Models](https://mlsanity.com/paper/1805.04785/) (2018)
- [Dynamic Assortment Selection under the Nested Logit Models](https://mlsanity.com/paper/1806.10410/) (2018)

## Built on by (most cited first, 1 of 1)

- [Learning an Optimal Assortment Policy under Observational Data](https://mlsanity.com/paper/2502.06777/) (2025)

## Abstract (arXiv)

In this paper, we consider a multi-stage dynamic assortment optimization problem with multi-nomial choice modeling (MNL) 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 (LP) 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 resolving policy and the optimal objective of the fluid approximation) scales logarithmically with the length of time horizon and resource capacities.