arXiv:2611.15817 · v1

Tree Decomposition of Product and Nest Graphs for Assortment Optimization under the Generalized Nested Logit Model

首次提交 2026-11-12 02:31

版本更新 2026-11-12 02:31

雷达观测 2026-11-13 14:16

摘要

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.

作者备注：32 pages in main text, 18 pages in appendices