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 (Formula presented.) and can find, empirically, assortments that are 0.3-0.5% within optimality when k equals 4 and there are 100 products and (Formula presented.) 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 comput...