Technical Note—Capacitated Assortment Optimization: Hardness and Approximation

Antoine Désir (), Vineet Goyal () and Jiawei Zhang ()
Additional contact information
Antoine Désir: Technology and Operations Management, INSEAD, 77300 Fontainebleau, France
Vineet Goyal: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Jiawei Zhang: Leonard N. Stern School of Business, New York University, New York, New York 10012

Operations Research, 2022, vol. 70, issue 2, 893-904

Abstract: Assortment optimization is an important problem that arises in many practical applications such as retailing and online advertising. In this problem, the goal is to select a subset of items that maximizes the expected revenue in the presence of (1) the substitution behavior of consumers specified by a choice model , and (2) a potential capacity constraint bounding the total weight of items in the assortment. The latter is a natural constraint arising in many applications. We begin by showing how challenging these two aspects are from an optimization perspective. First, we show that adding a general capacity constraint makes the problem NP-hard even for the simplest choice model, namely the multinomial logit model. Second, we show that even the unconstrained assortment optimization for the mixture of multinomial logit model is hard to approximate within any reasonable factor when the number of mixtures is not constant. In view of these hardness results, we present near-optimal algorithms for the capacity constrained assortment optimization problem under a large class of parametric choice models including the mixture of multinomial logit, Markov chain, nested logit, and d -level nested logit choice models. In fact, we develop near-optimal algorithms for a general class of capacity constrained optimization problems whose objective function depends on a small number of linear functions. For the mixture of multinomial logit model (resp. Markov chain model), the running time of our algorithm depends exponentially on the number of segments (resp. rank of the transition matrix). Therefore, we get efficient algorithms only for the case of constant number of segments (resp. constant rank). However, in light of our hardness result, any near-optimal algorithm will have a super polynomial dependence on the number of mixtures for the mixture of multinomial logit choice model.

Keywords: Revenue Management and Market Analytics; assortment optimization; FPTAS; choice models (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2142 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:2:p:893-904

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().