Assortment Optimization under Multinomial Logit Choice Model with Tree Structured Consideration Sets

We study assortment optimization problems under multinomial logit choice model with two tree structured consideration set models, i.e., the subtree model and the induced paths model. In each model, there are multiple customer types and each customer type has a different consideration set. A customer of a particular type only purchases product within his consideration set. The tree structure means all products form a tree with each node representing one product and all consideration sets are induced from this tree. In the subtree model, each consideration set consists of products in a subtree and in the induced paths model, each consideration set consists of products on the path from one node to the root. All customers make purchase decisions following the same multinomial logit choice model except that different customer types have different consideration sets. The goal of the assortment optimization is to determine a set of products offered to customers such that the expected revenue is maximized. We consider both unconstrained problem and capacitated problem. We show that these problems are all NP-hard problems and propose a unified framework, which captures the tree structure in both models, to design fully polynomial time approximation schemes (FPTAS) for all these problems. Besides, we identify a special case under the induced paths model, showing that it can be solved in $O(n)$ operations