A Continuous-Knapsack-Based Framework for Constrained Static Assortment Optimization
Abstract
We consider the constrained static assortment optimization problem under the Multinomial Logit (MNL) model and its extensions, including the Customized Assortment Problem (CAP) and the joint assortment and pricing problem. Building on the knapsack formulation of MNL assortment planning, we introduce a novel concept, termed the modified reduced profit, defined as the maximum attainable value of the knapsack model for a given item set under a fixed no-purchase probability. We show that this modified reduced profit is a continuous-knapsack value function and is monotone and submodular. This structural property leads to a general approximation framework. In particular, if maximizing the continuous-knapsack value function over a downward-closed family L admits an α-approximation algorithm, then our MNL-THR algorithm achieves an α(1 − ϵ)-approximation through a geometric search over the no-purchase probability. As important special cases, cardinality, budget, and matroid constraints yield a (1 − 1/e)(1 − ϵ) guarantee. We further extend the framework to the CAP and the joint pricing and assortment problem, showing that the underlying submodularity structure is preserved. Finally, we develop faster approximation algorithms that avoid the geometric search and achieve a (1 − 1/e)/2 guarantee under the three commonly studied constraint families, providing a trade-off between computational efficiency and solution quality

