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.
Article