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

ISABEL MÉNDEZ-DÍAZ; JUAN 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 ofcustomers heterogeneous with respect to preferences. Upon arrival, each customerchecks the offer set displayed by the firm, and either chooses one of those productsaccording to a multinomial-logit (MNL) criterion or quits without purchasing. Thefirm?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. Inthis paper, we analyze uncapacitated and capacitated (i.e., with a limited numberof products to display) versions of it, and propose a branch-and-cut algorithm thatis computationally feasible and leads to high-quality solutions.