Assortment Optimization Under the Paired Combinatorial Logit Model

Heng Zhang (), Paat Rusmevichientong () and Huseyin Topaloglu ()
Additional contact information
Heng Zhang: Marshall School of Business, University of Southern California, Los Angeles, California 90089
Paat Rusmevichientong: Marshall School of Business, University of Southern California, Los Angeles, California 90089
Huseyin Topaloglu: School of Operations Research and Information Engineering, Cornell Tech, New York, New York 10044

Operations Research, 2020, vol. 68, issue 3, 741-761

Abstract: 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.

Keywords: customer choice modeling; paired combinatorial logit model; assortment optimization (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1930 (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:68:y:2020:i:3:p:741-761

Access Statistics for this article

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