Exact and heuristic algorithms for cardinality-constrained assortment optimization problem under the cross-nested logit model

Le Zhang, Shadi Sharif Azadeh and Hai Jiang

European Journal of Operational Research, 2025, vol. 324, issue 1, 183-199

Abstract: We study a class of assortment optimization problems where customers choose products according to the cross-nested logit (CNL) model and the number of products offered in the assortment cannot exceed a fixed number. Currently, no exact method exists for this NP-hard problem that can efficiently solve even small instances (e.g., 50 products with a cardinality limit of 10). In this paper, we propose an exact solution method that addresses this problem by finding the fixed point of a function through binary search. The parameterized problem at each iteration corresponds to a nonlinear binary integer programming problem, which we solve using a tailored Branch-and-Bound algorithm incorporating a novel variable-fixing mechanism, branching rule and upper bound generation strategy. Given that the computation time of the exact method can grow exponentially, we also introduce two polynomial-time heuristic algorithms with different solution strategies to handle larger instances. Numerical results demonstrate that our exact algorithm can optimally solve all test instances with up to 150 products and more than 90% of instances with up to 300 products within a one-hour time limit. Using the exact method as a benchmark, we find that the best-performing heuristic achieves optimal solutions for the majority of test instances, with an average optimality gap of 0.2%.

Keywords: Assortment optimization; Cross-nested logit; Revenue management; Branch-and-Bound; Cardinality constraint (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724009792
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:324:y:2025:i:1:p:183-199

DOI: 10.1016/j.ejor.2024.12.037

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().