- | ||||
|
![]()
|
Constrained Assortment Optimization under the Paired Combinatorial Logit Model
Rohan Ghuge(rghuge 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |