Premium
Bounding Optimal Expected Revenues for Assortment Optimization under Mixtures of Multinomial Logits
Author(s) -
Feldman Jacob,
Topaloglu Huseyin
Publication year - 2015
Publication title -
production and operations management
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.279
H-Index - 110
eISSN - 1937-5956
pISSN - 1059-1478
DOI - 10.1111/poms.12365
Subject(s) - heuristics , mathematical optimization , bounding overwatch , computer science , upper and lower bounds , multinomial logistic regression , heuristic , revenue , set (abstract data type) , transshipment (information security) , mathematics , economics , artificial intelligence , machine learning , mathematical analysis , accounting , computer security , programming language
We consider assortment problems under a mixture of multinomial logit models. There is a fixed revenue associated with each product. There are multiple customer types. Customers of different types choose according to different multinomial logit models whose parameters depend on the type of the customer. The goal is to find a set of products to offer so as to maximize the expected revenue obtained over all customer types. This assortment problem under the multinomial logit model with multiple customer types is NP‐complete. Although there are heuristics to find good assortments, it is difficult to verify the optimality gap of the heuristics. In this study, motivated by the difficulty of finding optimal solutions and verifying the optimality gap of heuristics, we develop an approach to construct an upper bound on the optimal expected revenue. Our approach can quickly provide upper bounds and these upper bounds can be quite tight. In our computational experiments, over a large set of randomly generated problem instances, the upper bounds provided by our approach deviate from the optimal expected revenues by 0.15% on average and by less than one percent in the worst case. By using our upper bounds, we are able to verify the optimality gaps of a greedy heuristic accurately, even when optimal solutions are not available.