Efficient Local-Search Heuristics for Online and Offline Assortment Optimization

We consider the key operational problem of optimizing the mix of offered products to maximize revenues when product prices are exogenous, and product demand follows a general discrete choice model. The key challenge is the computational difficulty of finding the best assortment, which may require an exhaustive search. Existing approaches address the challenge by either deriving efficient algorithms for specific parametric choice models or by studying the performance of general-purpose heuristics. The former approach results in algorithms that lack portability to other structures; whereas the latter approach has resulted in algorithms that may have poor performance in practice. We study a portable and easy-to-implement local search heuristic. We show that it efficiently finds the global optimum for the Markov chain model with performance guarantees for general choice structures. Empirically, it is better than prevailing heuristics when no efficient algorithms exist. It is within 0.02\% of optimality in our numerical studies for non-MC choice models. Moreover, we propose a learning algorithm based on our local search heuristic and show that the learning algorithm enjoys minimal learning regret for the Markov chain model. Our learning algorithm can also be employed for more general choice models.