Research map / Probabilistic and scientific modeling / Variational and generative sampling
Learning to Build Solutions in Stochastic Matching Problems Using Flows (Student Abstract)
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.
Applies GFlowNets with trajectory balance to learn to sample optimal-ish exchange plans for kidney exchange problems, comparing against MIP, random greedy and random uniform baselines.
Problem
Sampling diverse, high-reward exchange plans (near-optimal solutions) for kidney exchange problems, a combinatorial matching problem with cycles, as a step toward fair dynamic allocation.
Approach
Uses GFlowNets trained with a trajectory-decomposable trajectory balance loss, building exchange plans as sequences of selected cycles, so sampling is proportional to a reward tied to the number of matched patients.
Key results
- OptLearn reaches 0.928 expected ratio of optimal on a single instance vs 0.873 (RandUniform) and 0.877 (RandGreedy).
- OptLearn-Multi reaches 0.897 on multiple instances vs 0.795 and 0.821 for random baselines.
- Trained on size-50 graphs, OptLearn-Multi achieves 0.936, 0.872, 0.782 on sizes 50, 100, 200 versus RandGreedy's 0.841, 0.821, 0.706.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GFlowNet sampling on a single KEP instance instead of RandGreedy | OptLearn · Single instance | expected ratio of optimal solution: 0.877 -> 0.928 | Helped |
| Use GFlowNet sampling on a single KEP instance instead of RandUniform | OptLearn · Single instance | expected ratio of optimal solution: 0.873 -> 0.928 | Helped |
| Train a GFlowNet on multiple KEP graphs instead of using RandGreedy | OptLearn-Multi · Multiple instances | expected ratio of optimal solution: 0.821 -> 0.897 | Helped |
| Train a GFlowNet on multiple KEP graphs instead of using RandUniform | OptLearn-Multi · Multiple instances | expected ratio of optimal solution: 0.795 -> 0.897 | Helped |
| Train on multiple KEP graphs and sample solutions instead of using RandGreedy | OptLearn-Multi · KEP graphs, size 50 | expected ratio of optimal solution: 0.841 -> 0.936 | Helped |
| Train on multiple KEP graphs and sample solutions instead of using RandUniform | OptLearn-Multi · KEP graphs, size 50 | expected ratio of optimal solution: 0.829 -> 0.936 | Helped |
| Train on size-50 KEP graphs and sample size-100 graphs instead of using RandGreedy | OptLearn-Multi · KEP graphs, size 100 | expected ratio of optimal solution: 0.821 -> 0.872 | Helped |
| Train on size-50 KEP graphs and sample size-100 graphs instead of using RandUniform | OptLearn-Multi · KEP graphs, size 100 | expected ratio of optimal solution: 0.795 -> 0.872 | Helped |
| Train on size-50 KEP graphs and sample size-200 graphs instead of using RandGreedy | OptLearn-Multi · KEP graphs, size 200 | expected ratio of optimal solution: 0.706 -> 0.782 | Helped |
| Train on size-50 KEP graphs and sample size-200 graphs instead of using RandUniform | OptLearn-Multi · KEP graphs, size 200 | expected ratio of optimal solution: 0.631 -> 0.782 | Helped |
Limitations
- Preliminary static-case results only; dynamic setting and fairness not yet addressed
- Gap to optimal remains (about 0.90 expected ratio), and performance degrades on larger graphs
Experimental setup
Datasets: simulated KEP graphs (size 50, tested on 50, 100, 200)
Benchmarks: simulated KEP graphs of size 50, 100, 200
Metrics: expected ratio of optimal solution
Baselines: OptMIP RandUniform RandGreedy
Builds on: GFlowNet trajectory balance
Closest papers by meaning
- Flow Factorization for Efficient Generative Flow Networks (AAAI 2025 · similarity 0.87)
- A Theory of Non-acyclic Generative Flow Networks (AAAI 2024 · similarity 0.86)
- Order-Preserving GFlowNets (ICLR 2024 · similarity 0.86)
- Local Search GFlowNets (ICLR 2024 · similarity 0.86)
- Expected flow networks in stochastic environments and two-player zero-sum games (ICLR 2024 · similarity 0.86)
- Pre-Training and Fine-Tuning Generative Flow Networks (ICLR 2024 · similarity 0.86)
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.