An improved compact formulation for the assortment optimization problem with small consideration sets

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.