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 uncapacitated, capacitated and space 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, a fundamental and well-studied optimization problem. We obtain performance guarantees of 87.4%, 50% and ~50% for the uncapacitated, capacitated and space constrained versions respectively. These bounds improve significantly over prior work. We also study the assortment problem under more general constraints (such as multiple space constraints and partition constraints), for which we obtain a performance guarantee of 38.5%. To the best of our knowledge, these constraints have not been investigated previously. In addition, we implemented our algorithms and tested them on random instances available in the 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: 01/05/2019

Modify/Update this entry