# From Small to Large: A Graph Convolutional Network Approach for Solving Assortment Optimization Problems

arXiv: https://arxiv.org/abs/2507.10834 · HTML: https://mlsanity.com/paper/2507.10834/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 71 references that are in the map.
- First posted on arXiv 14 Jul 2025.

## Builds on (most cited first, 21 of 21)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement](https://mlsanity.com/paper/1509.08251/) (2015)
- [Predicting Choice with Set-Dependent Aggregation](https://mlsanity.com/paper/1906.06365/) (2019)
- [Representing Random Utility Choice Models with Neural Networks](https://mlsanity.com/paper/2207.12877/) (2022)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [Learning to Pivot as a Smart Expert](https://mlsanity.com/paper/2308.08171/) (2023)
- [Transformer Choice Net: A Transformer Neural Network for Choice Prediction](https://mlsanity.com/paper/2310.08716/) (2023)
- [Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments](https://mlsanity.com/paper/1606.01371/) (2016)
- [A Neural Network Based Choice Model for Assortment Optimization](https://mlsanity.com/paper/2308.05617/) (2023)

## Abstract (arXiv)

Assortment optimization seeks to select a subset of substitutable products, subject to constraints, to maximize expected revenue. The problem is NP-hard due to its combinatorial and nonlinear nature and arises frequently in industries such as e-commerce, where platforms must solve thousands of such problems each minute. We propose a graph convolutional network (GCN) framework to efficiently solve constrained assortment optimization problems. Our approach constructs a graph representation of the problem, trains a GCN to learn the mapping from problem parameters to optimal assortments, and develops three inference policies based on the GCN's output. Owing to the GCN's ability to generalize across instance sizes, patterns learned from small-scale samples can be transferred to large-scale problems. Theoretical results are established to show the expressive power of the proposed GCN, and explain the underlying mechanism of the size generalization ability. Numerical experiments show that a GCN trained on instances with 20 products achieves over 85% of the optimal revenue on problems with up to 2,000 products within seconds, outperforming existing heuristics in both accuracy and efficiency. We further extend the framework to settings with an unknown choice model using transaction data and demonstrate similar performance and scalability.