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

• URL: http://arxiv.org/abs/2507.10834v1
• Date: Mon, 14 Jul 2025 22:04:29 GMT
• Title: From Small to Large: A Graph Convolutional Network Approach for Solving Assortment Optimization Problems
• Authors: Guokai Li, Pin Gao, Stefanus Jasin, Zizhuo Wang,
• Abstract summary: We develop a graph representation of the constrained assortment optimization problem.<n>We then train a graph concolutional network to learn the patterns of optimal assortments.<n>We propose two inference policies based on the GCN's output.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Assortment optimization involves selecting a subset of substitutable products (subject to certain constraints) to maximize the expected revenue. It is a classic problem in revenue management and finds applications across various industries. However, the problem is usually NP-hard due to its combinatorial and non-linear nature. In this work, we explore how graph concolutional networks (GCNs) can be leveraged to efficiently solve constrained assortment optimization under the mixed multinomial logit choice model. We first develop a graph representation of the assortment problem, then train a GCN to learn the patterns of optimal assortments, and lastly propose two inference policies based on the GCN's output. Due to the GCN's inherent ability to generalize across inputs of varying sizes, we can use a GCN trained on small-scale instances to facilitate large-scale instances. Extensive numerical experiments demonstrate that given a GCN trained on small-scale instances (e.g., with 20 products), the proposed policies can achieve superior performance (90%+ optimality) on large-scale instances (with up to 2,000 products) within seconds, which outperform existing heuristic policies in both performance and efficiency. Furthermore, we extend our framework to a model-free setting where the underlying choice model is unknown but transaction data is available. We also conduct numerical experiments to demonstrate the effectiveness and efficiency of our proposed policies in this setting.

Related papers

• Generative Diffusion Models for Resource Allocation in Wireless Networks [77.36145730415045]
  We train a policy to imitate an expert and generate new samples from the optimal distribution.<n>We achieve near-optimal performance through the sequential execution of the generated samples.<n>We present numerical results in a case study of power control.
  arXiv  Detail & Related papers  (2025-04-28T21:44:31Z)
• GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
  We present a Graph Diffusion-based Solution Generation (GDSG) method.<n>This approach is designed to work with suboptimal datasets while converging to the optimal solution large probably.<n>We build GDSG as a multi-task diffusion model utilizing a Graph Neural Network (GNN) to acquire the distribution of high-quality solutions.
  arXiv  Detail & Related papers  (2024-12-11T11:13:43Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• Multi-Objective Optimization for Sparse Deep Multi-Task Learning [0.0]
  We present a Multi-Objective Optimization algorithm using a modified Weighted Chebyshev scalarization for training Deep Neural Networks (DNNs) Our work aims to address the (economical and also ecological) sustainability issue of DNN models, with particular focus on Deep Multi-Task models.
  arXiv  Detail & Related papers  (2023-08-23T16:42:27Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Towards Optimization and Model Selection for Domain Generalization: A Mixup-guided Solution [43.292274574847234]
  We propose Mixup guided optimization and selection techniques for domain generalization. For optimization, we utilize an out-of-distribution dataset that can guide the preference direction. For model selection, we generate a validation dataset with a closer distance to the target distribution.
  arXiv  Detail & Related papers  (2022-09-01T02:18:00Z)
• Data-informed Deep Optimization [3.331457049134526]
  We propose a data-informed deep optimization (DiDo) approach to solve high-dimensional design problems. We use a deep neural network (DNN) to learn the feasible region and to sample feasible points for fitting the objective function. Our results indicate that the DiDo approach empowered by DNN is flexible and promising for solving general high-dimensional design problems in practice.
  arXiv  Detail & Related papers  (2021-07-17T02:53:54Z)
• Policy-GNN: Aggregation Optimization for Graph Neural Networks [60.50932472042379]
  Graph neural networks (GNNs) aim to model the local graph structures and capture the hierarchical patterns by aggregating the information from neighbors. It is a challenging task to develop an effective aggregation strategy for each node, given complex graphs and sparse features. We propose Policy-GNN, a meta-policy framework that models the sampling procedure and message passing of GNNs into a combined learning process.
  arXiv  Detail & Related papers  (2020-06-26T17:03:06Z)
• Simultaneous Decision Making for Stochastic Multi-echelon Inventory Optimization with Deep Neural Networks as Decision Makers [0.7614628596146599]
  We propose a framework that uses deep neural networks (DNN) to optimize inventory decisions in complex multi-echelon supply chains. Our method is suitable for a wide variety of supply chain networks, including general topologies that may contain both assembly and distribution nodes.
  arXiv  Detail & Related papers  (2020-06-10T02:02:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.