On the Structure of Cardinality-Constrained Assortment Optimization

We study the static assortment optimization problem with cardinality constraints, i.e., the problem of offering an assortment of items of constrained size that will maximize expected revenue. This is generally regarded as a challenging problem, with identified hardness results in the existing literature for a number of popular and/or well-studied choice models. Motivated by existing approaches in the unconstrained setting that find successful exploitation of identified structure to devise either exact or approximate solution methods, we introduce another structural property of possible interest for study in the cardinality constrained setting. Recently, the work of Jagabathula (2016) has identified the optimality of a local search method for the cardinality constrained static assortment problem under Multinomial Logit (MNL) Choice, making MNL a rare case study of tractability among cardinality constrained problems. So we first revisit the MNL constrained assortment problem under a new lens in search of structure that explains its “tractability.” Following this, we study the extent to which this property holds in other choice models. Indeed, we find that local search is optimal for some other choice models, and remains so even under more generalized cardinality constraints. Finally, we provide and test some algorithms (which require black-box access to the expected revenue function) that can be applied to the joint assortment and pricing problem under certain choice models, showing favorable performance small to moderate-sized problems against some current approaches.

Download paper here

Recommended citation: Louis Chen, David Simchi-Levi. (2017). “On the Structure of Cardinality-Constrained Assortment Optimization.” . .