An improved compact formulation for the assortment optimization problem with small consideration sets
针对顾客偏好列表最多包含k个产品的小考虑集品类优化问题，提出一种改进的紧凑型混合整数线性规划公式，其连续松弛非常紧，可在几分钟内求解多达200个产品、10万个顾客类别且k=5的实例，并得到最优解。
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−1𝑘)𝑘−1(1𝑘) 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.