Assortment optimization under the paired combinatorial logit model

Heng Zhang, Paat Rusmevichientong, Huseyin Topaloglu

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)741-761
Number of pages21
JournalOperations Research
Issue number3
StatePublished - May 2020
Externally publishedYes


  • Assortment optimization
  • Customer choice modeling
  • Paired combinatorial logit model

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Assortment optimization under the paired combinatorial logit model'. Together they form a unique fingerprint.

Cite this