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

Journal Article (2025)
Author(s)

Le Zhang (Tsinghua University)

Sh Sharif Azadeh (TU Delft - Transport, Mobility and Logistics)

Hai Jiang (Tsinghua University)

Research Group
Transport, Mobility and Logistics
DOI related publication
https://doi.org/10.1016/j.ejor.2024.12.037
More Info
expand_more
Publication Year
2025
Language
English
Research Group
Transport, Mobility and Logistics
Bibliographical Note
Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. @en
Issue number
1
Volume number
324
Pages (from-to)
183-199
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

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%.

Files

1-s2.0-S0377221724009792-main-... (pdf)
(pdf | 1.53 Mb)
- Embargo expired in 01-07-2025
License info not available