Tree decompositions enable efficient assortment optimization under complex product models
Tree Decomposition of Product and Nest Graphs for Assortment Optimization under the Generalized Nested Logit Model
Data Structures and Algorithms
Summary
Choosing the best set of products to offer customers is hard when products belong to many overlapping groups, which affects how customers substitute one product for another. The authors show this problem is tough even in simple cases. They introduce ways to look at how products and groups connect using graphs and special tree-like structures. This approach helps find efficient or approximate solutions in many cases. Their tests show the model fits customer choice data better than older models.
What this means in practice
- •For retail pricing teams: Calculate optimal product sets to offer under complex customer choice models allowing overlapping product categories.
- •For ecommerce platform engineers: Use tree decomposition methods to efficiently approximate best product assortments when complex substitution patterns exist.
Authors
Yuheng Wang, Paat Rusmevichientong, Huseyin Topaloglu
Abstract
The generalized nested logit model extends the nested logit model by allowing each product to belong to multiple nests. The overlapping nests in the generalized nested logit model can capture complex substitution patterns, and the model has found applications in many areas. We study the assortment optimization problem under the generalized nested logit model and prove that it is NP-hard when there are only two nests or when any two distinct nests have at most one product in common. Motivated by these complexity results, we introduce novel concepts of product and nest graphs that capture which products are included in which nests. We use the tree decompositions of the graphs to characterize when the assortment optimization problem admits efficient solution methods. When the treewidth of a product graph is bounded, the assortment optimization problem can be solved in polynomial time. If the treewidth of the product graph is unbounded but the treewidth of the nest graph is bounded, then there exists a fully polynomial-time approximation scheme. These results represent the first polynomial-time algorithms for assortment optimization under the generalized nested logit model. Our numerical experiments on synthetic and real datasets show that the generalized nested logit model provides a better fit to the data than many existing models in the literature.