Multi-Purchase Assortment Optimization with Heterogeneous Baskets: Overcoming the Curse of Dimensionality

We study multi-purchase assortment optimization with heterogeneous basket capacities and general utility-shock distributions. In the multi-purchase random utility model (MP-RUM), a customer with random capacity $B$ selects up to $B$ offered products with the highest realized utilities, provided they are preferred to an outside option. Assortment optimization under MP-RUM is computationally challenging because computing purchase probabilities requires joint ranking of offered products, while capacity heterogeneity introduces a curse of dimensionality. We develop a two-step approximation framework to address these challenges. First, we replace the random rank threshold with a deterministic counterpart for each capacity level and assortment, defining a surrogate choice model and its associated surrogate assortment problem (SP). Under regularity conditions on utilities and shock tails, optimizing SP incurs an additive $O(1)$ revenue loss under MP-RUM, independent of catalog size and the basket-capacity distribution. Without these conditions, we establish a distribution-free bound of square-root order in mean capacity and show that this order is tight. Second, to address the curse of dimensionality, we compress the capacity distribution into a small set of representative values and bound the loss in surrogate revenue by the mean absolute compression error. This reduction yields a polynomial-time approximation scheme for SP under mild conditions on capacity variability and inner-problem tractability. We also identify conditions under which replacing the distribution by its mean incurs a controlled loss in surrogate revenue. Our numerical experiments show near-optimal revenues across utility-shock distributions. Moreover, linear relaxation and basket-capacity compression preserve this accuracy while reducing solution times, enabling large-scale optimization.