Assortment Optimization Under the Paired Combinatorial Logit Model

• 成果类型: Article
• 署名作者: Zhang, Heng; Rusmevichientong, Paat; Topaloglu, Huseyin
• 署名单位: University of Southern California
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1930
• 发表日期: 2020
• 页码: 741-761
• 关键词: customer choice modeling; paired combinatorial logit model; Assortment Optimization

摘要

We consider uncapacitated and capacitated assortment problems under the paired combinatorial logit model, where the goal is to find a set of products to offer to maximize the expected revenue obtained from a customer. In the uncapacitated setting, we can offer any set of products, whereas in the capacitated setting, there is an upper bound on the number of products that we can offer. We establish that even the uncapacitated assortment problem is strongly NP-hard. To develop an approximation framework for our assortment problems, we transform the assortment problem into an equivalent problem of finding the fixed point of a function, but computing the value of this function at any point requires solving a nonlinear integer program. Using a suitable linear programming relaxation of the nonlinear integer program and randomized rounding, we obtain a 0.6-approximation algorithm for the uncapacitated assortment problem. Using randomized rounding on a semidefinite programming relaxation, we obtain an improved 0.79-approximation algorithm, but the semidefinite programming relaxation can become difficult to solve in practice for large problem instances. Finally, using iterative rounding, we obtain a 0.25-approximation algorithm for the capacitated assortment problem. Our computational experiments on randomly generated problem instances demonstrate that our approximation algorithms, on average, yield expected revenues that are within 1.1% of an efficiently computable upper bound on the optimal expected revenue.