Research map / Learning theory and algorithms / Combinatorial and search optimization
DistrictNet: Decision-aware learning for geographical districting
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 DistrictNet, which trains a GNN to predict edge weights of a capacitated minimum spanning tree surrogate, using imitation with a Fenchel-Young loss on target CMST solutions built from small optimal districting solutions.
Problem
Districting and routing: partitioning a geographical area of basic units into connected, size-balanced districts minimizing expected routing (stochastic TSP) costs; exact solutions are intractable for realistic city sizes and existing cost-surrogate heuristics yield suboptimal solutions.
Approach
Embed a combinatorial optimization layer (a parameterized capacitated minimum spanning tree) in a GNN so that edge weights are learned by decision-aware imitation; districting targets are converted to CMST moment targets via randomized Kruskal, and training minimizes a Fenchel-Young loss.
Key results
- DistrictNet yields about 10% lower average relative cost than BD (9.92%), FIG (10.01%) and PredGNN (11.91%) and 4.44% lower than AvgTSP across 35 test instances (N=120).
- On a 2,000-BU Ile-de-France instance, DistrictNet cost 2205.7 vs 2262.7 for AvgTSP and 2295.2 for PredGNN.
- Trained on only 100 instances of 30 BUs with a training time of 38 minutes, versus 16 hours for PredGNN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use structured learning with a CMST optimization layer and GNN instead of BD cost estimation | Districting and routing · 35 test instances (7 cities, N=120; t=3, 6, 12, 20, 30) | average relative cost: 9.92 % -> 0.0 % | Helped |
| Use structured learning with a CMST optimization layer and GNN instead of FIG cost estimation | Districting and routing · 35 test instances (7 cities, N=120; t=3, 6, 12, 20, 30) | average relative cost: 10.01 % -> 0.0 % | Helped |
| Add structured learning with a CMST optimization layer to GNN-based cost prediction | GNN-based districting and routing · 35 test instances (7 cities, N=120; t=3, 6, 12, 20, 30) | average relative cost: 11.91 % -> 0.0 % | Helped |
| Use structured learning with a CMST optimization layer and GNN instead of AvgTSP without learning | Districting and routing · 35 test instances (7 cities, N=120; t=3, 6, 12, 20, 30) | average relative cost: 4.44 % -> 0.0 % | Helped |
| Use DistrictNet instead of BD | Districting and routing · Ile-de-France, 2,000 BUs (t=20) | absolute cost: 2379.0 -> 2205.7 | Helped |
| Use DistrictNet instead of FIG | Districting and routing · Ile-de-France, 2,000 BUs (t=20) | absolute cost: 2388.8 -> 2205.7 | Helped |
| Use DistrictNet instead of PredGNN | Districting and routing · Ile-de-France, 2,000 BUs (t=20) | absolute cost: 2295.2 -> 2205.7 | Helped |
| Use DistrictNet instead of AvgTSP | Districting and routing · Ile-de-France, 2,000 BUs (t=20) | absolute cost: 2262.7 -> 2205.7 | Helped |
| Increase the number of DistrictNet training examples | DistrictNet · Out-of-distribution test instances across cities and target sizes | relative cost | Helped |
Surprising findings
- The simple AvgTSP heuristic with no learning outperforms the supervised GNN benchmark PredGNN, which is attributed to distribution shift between training and test instances.
- DistrictNet generalizes to instances more than 60 times larger than the training instances.
Limitations
- Only applied to districting and routing; generality to other geographic partitioning problems not demonstrated.
- No worst-case guarantees on solution quality.
- Training requires exact enumeration of optimal districting solutions on small instances, which is computationally expensive.
Experimental setup
Datasets: Uber Movement geographical data ONS census population data INSEE population data for French cities synthetic training instances from 27 English cities
Benchmarks: Bristol Leeds London Manchester Lyon Marseilles Paris Ile-de-France 2000 BUs
Metrics: relative districting cost (Monte Carlo expected TSP cost) p-value (one-sided Wilcoxon test)
Baselines: BD FIG PredGNN AvgTSP
Builds on: Fenchel-Young loss perturbation-based differentiable optimization PredGNN Beardwood-Halton-Hammersley formula
Closest papers by meaning
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.82)
- Learning Domain-Independent Heuristics for Grounded and Lifted Planning (AAAI 2024 · similarity 0.82)
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.82)
- Destroy and Repair Using Hyper-Graphs for Routing (AAAI 2025 · similarity 0.82)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.82)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.82)
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.