Publication Type
Journal Article
Version
submittedVersion
Publication Date
10-2024
Abstract
We study the assortment optimization problem under general linear constraints, where the customer choice behavior is captured by the cross-nested logit model. In this problem, there is a set of products organized into multiple subsets (or nests), where each product can belong to more than one nest. The aim is to find an assortment to offer to customers so that the expected revenue is maximized. We show that, under the cross-nested logit model, the unconstrained assortment problem is NP-hard even when there are only two nests, and the problem is generally NP-hard to approximate to any constant factors. To tackle this challenging problem, we develop a new discretization mechanism to approximate the problem by a linear fractional program with a performance guarantee of (Formula presented.), for any accuracy level (Formula presented.). We then show that optimal solutions to the approximate problem can be obtained by solving mixed-integer linear programs. We further show that our discretization approach can also be applied to solve a joint assortment optimization and pricing problem, as well as an assortment problem under a mixture of cross-nested logit models to account for multiple classes of customers. Our empirical results on a large number of randomly generated test instances demonstrate that, under a performance guarantee of 90% (i.e., expected revenues are guaranteed to be at least 90% of the optimal revenue), the percentage gaps between the objective values obtained from our approximation methods and the optimal expected revenues are no larger than 1.2%.
Keywords
Constrained assortment optimization, cross-nested logit, discretization, mixed-integer linear programming
Discipline
Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms
Research Areas
Intelligent Systems and Optimization
Publication
Production and Operations Management
Volume
33
Issue
10
First Page
2073
Last Page
2090
ISSN
1059-1478
Identifier
10.1177/10591478241263857
Publisher
SAGE
Embargo Period
4-2-2025
Citation
LE, Cuong and MAI, Tien.
Constrained assortment optimization under the cross-nested logit model. (2024). Production and Operations Management. 33, (10), 2073-2090.
Available at: https://ink.library.smu.edu.sg/sis_research/10138
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Additional URL
https://doi.org/10.1177/10591478241263857
Included in
Artificial Intelligence and Robotics Commons, Operations Research, Systems Engineering and Industrial Engineering Commons, Theory and Algorithms Commons
