A Branch-and-Cut Algorithm for the Latent Class Logit Assortment Problem

ISABEL MÉNDEZ-DÍAZ; JUAN JOSÉ MIRANDA BRONT; GUSTAVO VULCANO; PAULA ZABALA

Hammamet

Simposio; International Symposium on Combinatorial Optimization; 2010

We study the product assortment problem of a retail operation that faces a stream of customers heterogeneous with respect to preferences. Upon arrival, each customer checks the offer set displayed by the firm, and either chooses one of those products according to a multinomial-logit (MNL) criterion or quits without purchasing. The firm´s goal is to maximize the expected revenue extracted from each customer. The general version of the logit assortment problem is known to be NP-Hard. In this paper, we analyze uncapacitated and capacitated (i.e., with a limited number of products to display) versions of it, and propose a branch-and-cut algorithm that is computationally feasible and leads to high-quality solutions.