Constrained Assortment Optimization under the Paired Combinatorial Logit Model

Rohan Ghuge (rghugeumich.edu)
Joseph Kwon (jyjkwonumich.edu)
Viswanath Nagarajan (viswaumich.edu)
Adetee Sharma (adeteesumich.edu)

Abstract: We study the assortment optimization problem when customer choices are governed by the paired combinatorial logit model. We study unconstrained, capacitated and knapsack constrained versions of this problem, which are all known to be NP-hard. We design efficient algorithms that compute approximately optimal solutions, using a novel relation to the maximum directed cut problem and suitable linear-program rounding algorithms. We obtain a randomized polynomial time approximation scheme (PTAS) for the unconstrained version and performance guarantees of 50% and ~50% for the capacitated and knapsack constrained versions respectively. These bounds improve significantly over prior work. We also obtain a performance guarantee of 38.5% for the assortment problem under more general constraints such as multidimensional knapsack (where products have multiple attributes and there is a knapsack constraint on each attribute) and partition constraints (where products are partitioned into groups and there a limit on the number of products selected from each group). In addition, we implemented our algorithms and tested them on random instances available in prior literature. Our computational results are very good, demonstrating much better empirical performance than the above-mentioned worst-case bounds.

Keywords: assortment optimization, submodularity, linear and semidefinite programming

Category 1: Applications -- OR and Management Sciences

Citation:

Download: [PDF]

Entry Submitted: 01/05/2019
Entry Accepted: 01/07/2019
Entry Last Modified: 06/10/2020

Modify/Update this entry