A Re-solving Heuristic for Dynamic Assortment Optimization with Knapsack Constraints
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 highly 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. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Assortment OptimizationSimilar Papers 제목 키워드 기반
The Refined Assortment Optimization Problem
We introduce the refined assortment optimization problem where a firm may decide to make some of its products harder to get instead of making them unavailable as in the traditional assortment optimization problem. Airlin…
Assortment OptimizationDiscrete Choice ModelsEvaluating the impact of different types of crossover and selection methods on the convergence of 0/1 Knapsack using Genetic Algorithm
Genetic Algorithm is an evolutionary algorithm and a metaheuristic that was introduced to overcome the failure of gradient based method in solving the optimization and search problems. The purpose of this paper is to eva…
Dynamic Assortment Optimization with Changing Contextual Information
In this paper, we study the dynamic assortment optimization problem under a finite selling season of length $T$. At each time period, the seller offers an arriving customer an assortment of substitutable products under a…
Assortment OptimizationCombinatorial OptimizationFrom Small to Large: A Graph Convolutional Network Approach for Solving Assortment Optimization Problems
Assortment optimization seeks to select a subset of substitutable products, subject to constraints, to maximize expected revenue. The problem is NP-hard due to its combinatorial and nonlinear nature and arises frequently…
Differentiable Knapsack and Top-k Operators via Dynamic Programming
Knapsack and Top-k operators are useful for selecting discrete subsets of variables. However, their integration into neural networks is challenging as they are piecewise constant, yielding gradients that are zero almost …