Treffer: Constrained Assortment Optimization Under the Paired Combinatorial Logit Model.

Assortment optimization involves selecting a subset of products to offer to customers in order to maximize revenue. Often, the selected subset must also satisfy some constraints, such as capacity or space usage. Two key aspects in assortment optimization are (1) modeling customer behavior and (2) computing optimal or near-optimal assortments efficiently. The paired combinatorial logit (PCL) model is a generic customer choice model that allows for arbitrary correlations in the utilities of different products. The PCL model has greater modeling power than other choice models, such as multinomial-logit and nested-logit. In "Constrained Assortment Optimization Under the Paired Combinatorial Logit Model," Ghuge, Kwon, Nagarajan, and and Sharma provide efficient algorithms that find provably near-optimal solutions for PCL assortment optimization under several types of constraints. These include the basic unconstrained problem (which is already intractable to solve exactly), multidimensional space constraints, and partition constraints. The authors also demonstrate via extensive experiments that their algorithms typically achieve over 95% of the optimal revenues. We study the assortment optimization problem when customer choices are governed by the paired combinatorial logit model. We study unconstrained, cardinality-constrained, 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 for the unconstrained version and performance guarantees of 50% and ≈ 50 % for the cardinality-constrained 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 is 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. We compared our algorithms against an upper bound obtained using a linear program. Our average performance bounds for the unconstrained, cardinality-constrained, knapsack-constrained, and partition-constrained versions are over 99%, 99%, 96%, and 99%, respectively. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)