The Value of Robust Assortment Optimization Under Ranking-based Choice Models

We study a class of robust assortment optimization problems that was proposed by Farias, Jagabathula, and Shah (2013). The goal in this class of problems is to find an assortment that maximizes a firm’s worst-case expected revenue under all ranking-based choice models that are consistent with the historical sales data generated by the firm’s past assortments. Despite its significance in the revenue management literature, this class of robust optimization problems is widely believed to be computationally intractable, and no practical algorithms for solving these problems have been developed thus far.

Our main contributions in this paper are three-fold. First, we establish that optimal assortments for these robust optimization problems have a simple structure that is closely related to the structure of revenue-ordered assortments. Second, we demonstrate that the class of robust optimization problems can be solved in reasonable computation times in various settings of practical importance. Specifically, we develop exact algorithms for solving the robust optimization problems that run in polynomial time for any fixed number of past assortments. Moreover, when the firm’s past assortments satisfy a common assumption, we show that the robust optimization problem can be reformulated as a compact mixed-integer linear optimization problem of size that is polynomial in the number of products as well as the number of past assortments. Third, we use our algorithms and structural results to derive a number of managerial insights regarding the value of robust optimization and the risks of estimate-then-optimize in the context of data-driven assortment optimization with ranking-based choice models.