Learning Scenario Representation for Solving Two-stage Stochastic Integer Programs
TL;DR
Solving two-stage stochastic integer programs (SIPs) is notoriously difficult because it combines NP-hard combinatorial optimization with a massive number of uncertain "scenarios." This paper introduces a deep generative framework using Conditional Variational Autoencoders (CVAE) to learn low-dimensional representations of these scenarios. By clustering in this learned latent space, the authors can drastically reduce the number of scenarios needed to find high-quality solutions, achieving near-optimal results much faster than traditional solvers.
What Problem Does This Paper Address?
Many real-world problems—like logistics, energy grid management, and inventory control—involve making a "first-stage" decision (e.g., building a warehouse) before "second-stage" uncertainties (e.g., actual customer demand) are revealed. These are modeled as Stochastic Integer Programs (SIPs).
The challenge is two-fold:
- Complexity: Integer programs are already NP-hard.
- Scenario Explosion: To accurately model uncertainty, you might need thousands of scenarios. Solving an optimization problem across all of them simultaneously is often computationally impossible.
Existing "scenario reduction" techniques usually look only at the probability distribution of the scenarios themselves, ignoring the specific structure of the optimization problem (the "context"). This paper aims to learn scenario representations that are "context-aware," making the reduction process much more effective.
Methods
The authors propose a Conditional Variational Autoencoder (CVAE) architecture tailored for graph-based SIPs.
- Contextual Embedding: They use a Graph Convolutional Network (GCN) to encode the deterministic part of the problem (the "context," like the layout of a network) into a vector.
- Scenario Encoding: The GCN also embeds each individual scenario. These embeddings are mapped into a low-dimensional latent space.
- Conditional Decoding: A decoder attempts to reconstruct the original scenario using both the latent representation and the context. This ensures the latent space captures how a scenario relates specifically to the problem instance.
- Semi-Supervised Learning (CVAE-SIPA): In an advanced version, they add a sub-network to predict the "objective value" (the cost) of a scenario. By training on a tiny fraction (1%) of labeled data from a heavy-duty solver (CPLEX), the latent space becomes even more informative for optimization.
- Downstream Tasks: Once trained, the encoder maps all scenarios into the latent space. They then use simple K-medoids clustering to pick $K$ representative scenarios to solve the actual SIP.
Datasets
The method was evaluated on two classic graph-based optimization problems:
- Network Design Problem (NDP): Deciding which edges in a graph to open to minimize transportation costs under uncertain demand.
- Facility Location Problem (FLP): Deciding where to build facilities to serve customers whose presence is uncertain.
The authors generated synthetic datasets for these problems, including "normal" sizes and larger "generalization" instances (doubling or quadrupling the number of nodes/scenarios) to test the robustness of the neural network.
Key Insights and Ideas
- Context Matters: Traditional scenario reduction is like summarizing a book by looking at word frequencies. This method is like summarizing a book by understanding the plot. By conditioning the autoencoder on the problem "context," the latent representations reflect how a scenario actually impacts the optimization objective.
- Latent Clustering > Raw Clustering: Clustering in the low-dimensional latent space consistently outperformed clustering in the high-dimensional raw scenario space. The latent space acts as a filter, stripping away noise and keeping only the features relevant to the problem.
- The Power of 1%: Even with very few "ground truth" objective values (semi-supervised learning), the model (CVAE-SIPA) significantly improved solution quality. This suggests that the model effectively learns the "landscape" of the cost function.
- Zero-Shot Generalization: A model trained on small graphs (e.g., 14 nodes) could be applied directly to much larger graphs (e.g., 44 nodes) and still produce excellent scenario reductions without retraining.
Key Results
The proposed method demonstrates exceptional performance in both accuracy and computational efficiency, particularly on large-scale problems.
- Accuracy: On the Network Design Problem, the proposed CVAE-SIPA achieved errors as low as 0.03% to 0.24% compared to the optimal solution, significantly outperforming standard K-medoids and other deep learning baselines.
- Speed: While an exact solver (CPLEX) might take 23 minutes to 1 hour for large instances (as seen in the generalization tables above), the CVAE-based approach provided high-quality approximations in seconds.
- Scalability: The method maintained high performance even when the number of scenarios was increased from 200 to 800, where traditional solvers began to struggle with memory and time constraints.
Limitations and Future Work
- Manual Hyperparameters: The number of representative scenarios ($K$) still needs to be chosen manually. The authors suggest that automating the selection of $K$ based on the desired accuracy-speed tradeoff is a promising next step.
- Graph-Centric: The current implementation relies heavily on GCNs, making it best suited for problems that can be naturally represented as graphs.
- Multi-stage Extension: The paper focuses on two-stage SIPs. Real-world problems often have multiple stages of decision-making and uncertainty, which would require a more complex temporal modeling approach.
Summary updated