A Continuous-Knapsack-Based Framework for Constrained Static Assortment Optimization

Published Online:https://doi.org/10.1287/opre.2026.2633

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

INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.