Research map / Graph learning / Graph algorithms and clustering
HGCN2SP: Hierarchical Graph Convolutional Network for Two-Stage Stochastic Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes HGCN2SP, a hierarchical GCN policy trained with PPO that selects an ordered subset of scenarios for two-stage stochastic programs, using solver time and decision consistency as reward.
Problem
Solving two-stage stochastic programs (2SP) with many scenarios is computationally expensive; existing scenario reduction methods ignore scenario order and solver feedback and often rely on clustering or sampling.
Approach
A two-level hierarchical graph (scenario-level bipartite MIP graphs plus an instance graph over scenarios weighted by parameter cosine similarity) encoded by a hierarchical GCN, with an attention-based sequential decoder that selects k scenarios in order, trained by PPO using negative solve time and a decision-matching reward.
Key results
- On CFLP_10_20_200 with k=5, HGCN2SP achieves 2.47% error in 2.45 s versus 6.86% for CVAE-SIPA in 2.40 s.
- On CFLP_10_20_500 with k=5, HGCN2SP achieves 3.43% error versus 10.18% for CVAE-SIP and 11.53% for CVAE-SIPA.
- On NDP_2_2_10_200, HGCN2SP underperforms CVAE-SIPA at k=5 (33.03% vs 24.59%) but is faster (0.17 s vs 0.54 s).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use HGCN2SP instead of CVAE-SIP for scenario selection | CFLP_10_20_200, k=5 · CFLP_10_20_200 | Error (%): 6.60 -> 2.47 | Helped |
| use HGCN2SP instead of CVAE-SIPA for scenario selection | CFLP_10_20_200, k=5 · CFLP_10_20_200 | Time (s): 2.40 -> 2.45 | Hurt |
| use HGCN2SP instead of CVAE-SIPA for scenario selection | NDP_2_2_10_200, k=10 · NDP_2_2_10_200 | Error (%): 6.06 -> 8.10 | Hurt |
| use HGCN2SP instead of CVAE-SIPA for scenario selection | NDP_2_2_10_200, k=10 · NDP_2_2_10_200 | Time (s): 1.01 -> 0.40 | Helped |
| use HGCN2SP instead of CVAE-SIPA for scenario selection | CFLP_20_40_200, k=10 · CFLP_20_40_200 | Error (%): 1.50 -> -0.63 | Helped |
| use HGCN2SP instead of CVAE-SIP for scenario selection | CFLP_20_40_200, k=10 · CFLP_20_40_200 | Time (s): 145.20 -> 124.71 | Helped |
| use HGCN2SP instead of CVAE-SIPA for scenario selection | NDP_2_2_20_200, k=10 · NDP_2_2_20_200 | Error (%): 7.83 -> 10.62 | Hurt |
| use HGCN2SP instead of CVAE-SIP for scenario selection | NDP_2_2_20_200, k=10 · NDP_2_2_20_200 | Time (s): 2.17 -> 1.01 | Helped |
| use HGCN2SP instead of CVAE-SIP for scenario selection | CFLP_10_20_500, k=5 · CFLP_10_20_500 | Error (%): 10.18 -> 3.43 | Helped |
| use HGCN2SP instead of CVAE-SIPA for scenario selection | NDP_2_2_10_500, k=10 · NDP_2_2_10_500 | Error (%): 8.15 -> 8.17 | No clear effect |
| use HGCN2SP instead of CVAE-SIP for scenario selection | NDP_2_2_10_500, k=10 · NDP_2_2_10_500 | Time (s): 1.14 -> 0.40 | Helped |
| add high-level graph layers (ablation) | HGCN2SP on CFLP_10_20_200, k=5 · CFLP_10_20_200 | Error (%): 8.35 -> 2.47 | Helped |
Surprising findings
- On NDP, HGCN2SP underperforms CVAE-SIPA in error, attributed to the many edge decision variables making the reward insensitive to small first-stage changes.
- On CFLP with k=10, HGCN2SP's solving time (14.72 s) is higher than CVAE-SIP (12.38 s) and CVAE-SIPA (10.23 s) on the 200-scenario setting.
Limitations
- Training requires costly optimal solutions (about 3 hours per CFLP instance), making data collection expensive.
- Underperforms CVAE-SIPA on NDP error rates.
- Selection ordering and reward design depend on problem-specific alpha weights (0.001 for CFLP, 0.01 for NDP).
Experimental setup
Datasets: CFLP instances (CFLP_10_20_200) NDP instances (NDP_2_2_10_200)
Benchmarks: CFLP_10_20_200 NDP_2_2_10_200 CFLP_20_40_200 NDP_2_2_20_200 CFLP_10_20_500 NDP_2_2_10_500
Metrics: error rate (%) solving time (s)
Baselines: Gurobi CSSC NN-P NN-E CVAE-SIP CVAE-SIPA
Builds on: Attention Model (Kool et al.) PPO GCN CVAE-SIP
Closest papers by meaning
- Neur2SP: Neural Two-Stage Stochastic Programming (NeurIPS 2022 · similarity 0.89)
- Decision Focused Scenario Learning for Contextual Stochastic Programming (NeurIPS 2026 · similarity 0.87)
- Learning Scenario Representation for Solving Two-stage Stochastic Integer Programs (ICLR 2022 · similarity 0.87)
- Probabilistic Hierarchical Goal Network Planning with UCT (AAAI 2026 · similarity 0.86)
- Learning Scenario Reduction for Two-Stage Robust Optimization with Discrete Uncertainty (NeurIPS 2026 · similarity 0.86)
- Efficient Reinforcement Learning by Discovering Neural Pathways (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.