Tractable Approximations for Assortment Planning with Product Costs

Assortment planning under a logit demand model is a difficult problem when there are product-specific fixed costs. We develop a new continuous relaxation of the problem that is based on the parametrization of the problem on the total assortment attractiveness. This relaxation provides an upper bound on the optimal expected profit. We show that the upper bound can be computed efficiently and allows us to generate feasible solutions with attractive performance guarantees. We analytically prove that these are close to optimal when products are homogeneous in terms of preference weights. Moreover, our formulation can be easily extended to incorporate additional constraints on the assortment, or multiple customer segments. Finally, we provide numerical experiments that show that our method yields tight upper bounds, performs competitively with respect to other approaches found in the literature, and is able to speed up commercial branch-and-bound procedures by tightening the optimality gap.