.png){kind=icon}
.png){kind=icon}
Return
An improved compact formulation for the assortment optimization problem with small consideration sets
.png){kind=icon}
PRE
AI
DOI：10.1080/01605682.2025.2451738.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We investigate the assortment optimization problem with small consideration sets, where customers belong to classes and choose according to the k-product non-parametric ranking-based choice model - i.e., each customer's preference list contains at most k products, and customers purchase the most preferred product among the ones offered in the assortment. This problem is known to be NP-hard even when k is equal to 2. The best approximation method from the literature has a performance guarantee of 2(1-1k)k-1(1k) and can find, empirically, assortments that are 0.3-0.5% within optimality when k equals 4 and there are 100 products and 10 000 customer classes. By building upon a compact Mixed-Integer Linear Programming model proposed, in the literature, for the full non-parametric ranking-based choice model, we propose an improved compact model that features a very tight continuous relaxation and can be easily solved with a general-purpose solver. An extensive set of computational experiments shows that our improved formulation can find provably optimal assortments of instances with up to 200 products, 100 000 customers classes, and k equal to 5, in a few minutes of runtime.
Keywords:
Assortment optimization
choice models
mixed-integer linear programming
exact methods
Journal
IF:
2.7
Papers:
390
Citations:
9.2K