Pith. sign in

REVIEW 3 major objections 4 minor 14 references

DistrictNet: Decision-aware learning for geographical districting

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A GNN trained on 30-BU towns finds near-optimal districts in cities up to 2,000 BUs, with about 10% lower routing costs than four baselines.

desk verdict DistrictNet is a genuinely new decision-aware CMST surrogate with real empirical gains, but the paper overclaims consistency and the theoretical foundation is weaker than presented. read the letter →

arxiv 2412.08287 v1 pith:P5B7L6C5 submitted 2024-12-11 cs.LG math.OC

Cheikh Ahmed , Alexandre Forel , Axel Parmentier , Thibaut Vidal This is my paper · ORCID
classification cs.LGmath.OC
keywords districtingcapacitatedminimumspanningtreegraphneuralnetworkdecision-awarelearningFenchel-Younglosscombinatorialoptimizationlayerroutinggeneralization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

DistrictNet claims that a graph neural network can learn to solve real-world geographical districting-and-routing problems by predicting edge weights for a capacitated minimum spanning tree (CMST), then converting the optimal CMST into districts. The training is decision-aware: the model imitates optimal solutions of tiny instances, using a Fenchel-Young loss whose gradient flows through a black-box CMST solver. On seven real cities with 120 to 983 basic units and on a 2,000-unit region, the resulting solutions cost about 10% less than existing district-cost estimators embedded in local search, and the improvement is consistent across city sizes and district sizes. The paper presents this as evidence that a structured surrogate optimization layer generalizes far better than learned cost estimators alone.

What carries the argument

The machinery is the capacitated minimum spanning tree as a differentiable optimization layer: a CMST finds $k$ subtrees of bounded size minimizing the sum of edge weights, and here the edge weights $\theta$ are predicted by a GNN. The CMST layer solves $\max_{y \in \mathcal{Y}} \theta^\top y$ over the convex hull of feasible subtree incidence vectors, and the optimal subtree partition maps surjectively to a districting partition. Training uses the Fenchel-Young loss $L_{\mathrm{FY}}(\theta,\bar{\mu}) = \Omega^*(\theta) + \Omega(\bar{\mu}) - \theta^\top \bar{\mu}$, with gradients estimated by perturbed optimizers, and targets $\bar{\mu}$ are expected CMST solutions built from optimal districts by running Kruskal with random edge weights.

What would settle it

Take a mid-size city (for example 60 BUs and 10 districts) where optimal districting is computable by full enumeration, train DistrictNet on the paper's 30-BU instances, and compare its output's true Monte-Carlo TSP cost to that exact optimum. If the CMST solution induced by learned weights is systematically more than a few percent worse than optimal districting, the surrogate-fidelity assumption fails; a cheaper check is to build a synthetic instance whose true district costs are deliberately non-additive, such as a river crossing penalty, and see whether the reported 10% margin persists.

Watch

Extended reading notes

Core claim

The central claim is that a parameterized CMST is a faithful surrogate for the districting-and-routing problem, and that a GNN can learn CMST edge weights from a handful of optimal small instances so that solving the CMST yields near-optimal districts on large out-of-distribution cities. The paper relies on a surjection from CMST solutions to district solutions: any district is the vertex set of a subtree, so for every districting problem there exists a CMST whose optimal solution coincides with the optimal districting. DistrictNet learns this CMST by minimizing a Fenchel-Young loss against target CMST moments reconstructed from optimal districting solutions via a randomized spanning-tree constructor. Empirically it reports cost reductions of roughly 10% over four benchmarks, up to 13% in the best cases, and a 2,000-BU instance solved within the same pipeline that was trained on 30-BU instances.

Load-bearing premise

The whole approach rests on the idea that the true cost of a district can be captured by adding up learned numbers on the edges of a tree inside that district, so the best tree partition is also the best district partition. If real district costs cannot be squeezed into that additive form, the learned model has no guarantee of matching the true optimum and only the test cities stand behind it.

Editorial extensions

If this is right

  • Practitioners can train on 100 small optimal instances of 30 BUs and deploy the same model on cities hundreds of times larger, obtaining solutions in minutes rather than CPU-core days.
  • DistrictNet generalizes across city structures and target district sizes, so a single trained model can evaluate a family of districting settings before a final choice is made.
  • The reported cost reduction of about 10% is statistically significant against BD, FIG, PREDGNN, and AVGTSP under a fixed ILS time budget, and the margin tends to grow with district size.
  • Because the training pipeline only needs district partitions as targets, the same CMST surrogate could be retrained for other district cost functions, such as fairness or compactness objectives.
  • DistrictNet also produces more compact districts, measured by Reock's score, indicating that the learned solutions are geographically tighter and not merely cheaper in tour length.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper's experiments, the same decision-aware imitation scheme could be applied to other NP-hard graph partition problems whose solutions admit a tree structure, such as school zoning or sales territory design, without redesigning the optimization layer.
  • The additive edge-weight model cannot represent arbitrary district cost functions exactly; the surjection guarantee only says an optimal CMST exists for some weights, not that learned weights will find it, so out-of-distribution success remains an empirical property that should be re-tested when demand distributions or district constraints change.
  • A testable extension is to train DistrictNet on geographies with asymmetric demand or barriers such as rivers and highways, to see whether the learned edge weights absorb these costs; if not, the 10% margin may shrink on such instances.
  • A controlled comparison between the Fenchel-Young imitation objective and direct cost regression, keeping the CMST structure fixed, would isolate how much of the gain comes from decision-aware training as opposed to the surrogate model itself.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes DistrictNet, a decision-aware learning pipeline for geographical districting-and-routing. A graph neural network predicts edge weights for a capacitated minimum spanning tree (CMST) surrogate, the CMST is solved as a combinatorial optimization layer, and a Fenchel-Young loss is used to train the network by imitating optimal solutions on small synthetic instances. The method is evaluated on seven real-world cities (120--983 basic units) and on one 2,000-BU region, with claims of roughly 10% average cost reduction against existing heuristics and of strong out-of-distribution generalization.

Significance. If the empirical claims hold, this is a practically valuable contribution: training on small instances and solving a linear CMST surrogate in minutes is far cheaper than exact stochastic districting, and the paper's public code and careful experimental design (held-out cities, a Wilcoxon test, in-distribution optimality-gap study in Table 6, and compactness analysis in Table 8) are commendable. However, the headline claim of consistent ~10% improvement is weakened by the paper's own detailed results, and the theoretical motivation for the surrogate is not fully established. The central contribution is therefore defensible but needs revision before the claims can be accepted as stated.

major comments (3)
  1. [Section 5.2, Appendix C.2 (Table 7)] The statement that 'DISTRICT NET consistently outperforms the benchmarks as it produces districting solutions with significant cost reductions of around 10% compared to all other methods' is contradicted by the paper's own Table 7. DistrictNet is not the best method on 8 of 35 test instances, and it is worse than the non-learning AVGTSP baseline on Manchester t=3 (1165.72 vs 1158.66), Manchester t=30 (316.55 vs 299.69), and Paris t=3,6,12,20 (relative losses of +4.7% to +9.7%), while tying AVGTSP on Paris t=30. Moreover, Table 1's average of 4.44% relative to AVGTSP is not 'around 10%'; the larger savings are concentrated in UK cities closer to the training distribution. Please report per-city and per-target win/loss/tie counts, add confidence intervals or error bars, and revise the 'consistently outperforms' and 'around 10%' wording to reflect the average and its variability accurately.
  2. [Section 3, Section 4.2] The assertion that 'there always exists a CMST problem such that their optimal solutions coincide' does not follow from the surjectivity argument given in Section 3. Surjectivity shows only that every districting solution can be represented as a set of subtrees; it does not establish that arbitrary district costs can be expressed as additive edge weights, nor that the optimal CMST solution for the learned weights will coincide with or well-approximate the optimal districting solution. This is the load-bearing assumption of the method, because the GNN edge weights are the only mechanism by which the surrogate can capture district costs. The paper provides no proof or approximation guarantee for this surrogate fidelity. Please either supply a precise proof with the required conditions, or explicitly state that surrogate fidelity is an empirical assumption supported solely by the experiments.
  3. [Section 5.2, Table 2, Result 2] The claim that DistrictNet 'generalizes to even the largest real-world problems' rests on a single run on the 2,000-BU Ile-de-France instance, with no error bars or repetition. In Table 2, DistrictNet improves over AVGTSP by only 2.6% and over PRED GNN by 4.0%, which is much smaller than the average improvements reported on smaller cities. This single point estimate does not support the strong wording of Result 2. Please provide multiple runs with variance, or substantially temper the generalization claim for very large instances.
minor comments (4)
  1. [Table 1] Please clarify that the relative percentages are cost increases relative to DistrictNet, with lower being better, and consider reporting the absolute costs or a boxplot in addition to the average.
  2. [Appendix A.4] The text says the target CMST solution in Equation (5) is 'constructed using a single observation of our random constructor', but later states that 'the randomized target constructor uses 1,000 samples'. Please reconcile these two statements, as they affect the reported bias-variance properties of the training procedure.
  3. [Figure 3] The legend of Figure 3 lists BD, FIG, and PRED GNN but omits AVGTSP, even though the surrounding text refers to benchmark methods generally; please include AVGTSP or explain its omission.
  4. [Table 2] There is a typo in the header 'A VGTSP'; it should read 'AVGTSP'. Additionally, the blue/orange highlighting in Table 7 is not accessible in grayscale print; consider adding textual markers.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: predictions are evaluated on held-out real-world cities and the CMST-surjection is an expressivity argument, not an input-equivalent derivation.

full rationale

The derivation chain is self-contained. DistrictNet is trained by imitating optimal solutions of 100 generated N=30 instances (Section 5.1, Appendix B.2) and evaluated on 35 independent real-city instances (Section 5.2, Table 7), so the reported costs are not fit-determined. The key theoretical premise—'there is a surjection from the space of CMST solutions to the space of districting solutions' and 'there always exists a CMST problem such that their optimal solutions coincide' (Section 3)—is a constructive expressivity claim: any feasible district is spanned by a tree, so a target districting solution can be encoded as a forest and assigned edge weights making that forest optimal. It does not assert that the learned GNN weights will find that forest, nor does it define the predicted cost in terms of the training target; optimality of the learned weights remains an empirical question. The Fenchel-Young loss and perturbed-optimizer gradient (Section 4.2) are cited from Blondel et al. (2020), Berthet et al. (2020), and Dalle et al. (2022); Dalle et al. includes a co-author, but the cited identities are parameter-free mathematical facts used as training machinery, not as evidence for the paper's empirical conclusions. The only in-scope concern is a descriptive inconsistency: the main text says DistrictNet 'consistently outperforms' with 'cost reductions of around 10%' (Section 5.2), while Appendix C.2 (Table 7) shows it is not best on 8 of 35 instances and is worse than non-learning AVGTSP on Manchester t=3,30 and Paris t=3,6,12,20. This weakens the strength of the empirical claim, but it is a correctness/over-claim issue, not a circular one: the reported best results are not forced by construction. No fitted parameter is renamed as a prediction, no load-bearing self-citation chain is used, and no known result is repackaged under new coordinates.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the surrogate fidelity of CMST edge weights, the accuracy of Monte Carlo cost evaluation, and the transferability from small to large instances. The existence claim in Section 3 is an ad hoc assumption. No new physical entities are introduced; the learned weights and the demand rate kappa are the main fitted or hand-set numbers.

free parameters (3)
  • GNN edge-weight parameters theta = learned from 100 training instances (no closed form)
    These weights define the CMST surrogate cost; the entire method's solution quality depends on this fit. They are not derived from first principles, only optimized to imitate target solutions on small instances.
  • Demand rate factor kappa = 96/(8000*t)
    Chosen so that a district with t BUs has about 100 demand requests per period. It is a hand-set modeling constant that defines the stochastic demand, hence shapes all training targets and evaluated costs.
  • Perturbation temperature epsilon and number of samples M = M=20; epsilon not specified in the text
    Hyperparameters of the Fenchel-Young gradient estimator; M is given, but epsilon is mentioned only as a symbol. These affect the bias-variance tradeoff of the stochastic gradient used in training.
assumptions (4)
  • ad hoc to paper For any districting problem, there exists a CMST problem whose optimal solution maps to the optimal districting solution.
    Stated in Section 3 and used to justify the CMST surrogate. Surjectivity alone does not imply that a single additive edge-weight model can represent arbitrary district cost functions; the claim is unproven and likely false in general.
  • domain assumption The expected TSP cost of a district is well approximated by the sum of learned edge weights over a spanning tree of that district.
    This is the central modeling assumption of the surrogate; the paper does not independently test the approximation error of this surrogate.
  • domain assumption Optimal solutions for training instances (N=30, t=3), computed by full enumeration with Monte Carlo cost estimates, are accurate enough to serve as imitation targets.
    Training relies on these targets. Cost estimates use 100 scenarios and LKH, which is an approximation of the true expected TSP cost.
  • standard math The Fenchel-Young loss gradient can be computed by Monte Carlo perturbation (Equation 8).
    This follows from Berthet et al. (2020) and Dalle et al. (2022), assuming the CMST solver returns exact optima; in training this is satisfied by enumeration.

how reviews work

0 comments
Cite this review

Pith. "Pith review of DistrictNet: Decision-aware learning for geographical districting." pith.science (2026). https://pith.science/paper/P5B7L6C5

@misc{pith2026241208287,
  author       = {Pith},
  title        = {Pith review of: DistrictNet: Decision-aware learning for geographical districting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P5B7L6C5}},
  note         = {Machine review of arXiv:2412.08287}
}
read the original abstract

Districting is a complex combinatorial problem that consists in partitioning a geographical area into small districts. In logistics, it is a major strategic decision determining operating costs for several years. Solving districting problems using traditional methods is intractable even for small geographical areas and existing heuristics often provide sub-optimal results. We present a structured learning approach to find high-quality solutions to real-world districting problems in a few minutes. It is based on integrating a combinatorial optimization layer, the capacitated minimum spanning tree problem, into a graph neural network architecture. To train this pipeline in a decision-aware fashion, we show how to construct target solutions embedded in a suitable space and learn from target solutions. Experiments show that our approach outperforms existing methods as it can significantly reduce costs on real-world cities.

Figures

Figures reproduced from arXiv: 2412.08287 by the authors.

Figure 1
Figure 1. DISTRICTNET solves a complex districting problem by parameterizing and solving a CMST. The GNN ϕ predicts a vector of edge weights θ based on the covariates of the instance x. These edge weights parameterize a CMST, which is solved using a black-box combinatorial solver. The CMST solution yˆ is finally converted into a districting solution λˆ. Training this pipeline in a decision-aware manner requires propagating a … view at source ↗
Figure 2
Figure 2. Districting solutions given by BD, FIG, PredictGNN, and DistrictNet for the city of [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Cost relative to DISTRICTNET for target district size t = 20 and varying city size. The results show that DISTRICTNET provides very good solutions up to the largest city sizes. It consistently outperforms the benchmarks even for large cities. These results are achieved despite DISTRICTNET being trained on small instances of size N = 30 BUs. We investigate further the scalability of our approach by considering a larg… view at source ↗
Figures from the paper (6 more)
Figure 5
Figure 5. Figure 5: Relative cost of DISTRICTNET with increasing data. The value of data for decision-aware learning. Finally, we investigate the value of training data for DISTRICTNET. In [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: Small (a) districting problem converted into (b) a CMST problem with edge weights and [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: PREDGNN estimates the cost of a district using a GNN and a feedforward NN. First, the GNN applies a message-passing algorithm to capture the structure of the graph. Then, an aggregation layer provides the graph embedding. This is post-processed by the feedforward NN, w…
Figure 4
Figure 4. Figure 4: FIG 4.24 % 15.98 % 0.27 % 4.09 % 12.16 % 0.42 % [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]
Figure 8
Figure 8. Figure 8: Districting solutions given by BD, FIG, PredictGNN, and DistrictNet for the city of [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]
Figure 9
Figure 9. Figure 9: Districting solutions given by BD, FIG, PredictGNN, and DistrictNet for the city of [PITH_FULL_IMAGE:figures/full_fig_p022_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 9 canonical work pages

  1. [3]

    Dalle, L

    G. Dalle, L. Baty, L. Bouvier, and A. Parmentier. Learning with combinatorial optimization layers: a probabilistic approach. arXiv preprint arXiv:2207.13513,

    arXiv

  2. [4]

    Technical Report, Roskilde University. C. K. Joshi, T. Laurent, and X. Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227,

    arXiv 1906

  3. [5]

    The lowest cost is shown in blue and the second-best in orange

    The table shows the districting cost achieved by the methods on each test city and for each target district size. The lowest cost is shown in blue and the second-best in orange. It highlights that DISTRICT NET provides the lowest count on 27 out of 35 test instances. Further, it shows that DISTRICT NET lead to significant savings, as it can reduce costs b...

    work page 1961

  4. [7]

    This probability is typically very low

    The perturbation algorithm is the same as the local search one except that each possible move is implemented with a given probability even if it does not improve the solution. This probability is typically very low. In our experiments, after hyperparameter tuning, we find that a probability of 1.5% works well in most instances, which is consistent with th...

    work page 2024

  5. [8]

    This procedure allows us to create a training set of arbitrary size that contains realistic (but small-sized) training instances

    Finally, an artificial central depot is placed at the centroid of the resultant polygon. This procedure allows us to create a training set of arbitrary size that contains realistic (but small-sized) training instances. Note also that there is no contamination between the training and test instances. 18 Table 5: Cities used to generate training instances a...

    work page 1973

  6. [9]

    This repair algorithm adjusts each district to meet the specified minimum and maximum size constraints by adding or removing nodes from neighboring districts while maintaining overall connectivity. Algorithm 6 Repair Require: Current districting solution S Sort districts in S by size in increasing order for each district d ∈ S do if |d| < dthen Add nodes ...

    work page 1984

  7. [10]

    First, the GNN applies a message-passing algorithm to capture the structure of the graph

    Example district xi Learning model: GNN and feedforward NN h(xi) Cost estimate Figure 7: PRED GNN estimates the cost of a district using a GNN and a feedforward NN. First, the GNN applies a message-passing algorithm to capture the structure of the graph. Then, an aggregation layer provides the graph embedding. This is post-processed by the feedforward NN,...

    work page 2011

  8. [12]

    It shows that, while the area and density may vary across cities, the population statistics are relatively constant

    The table shows the statistics on the population, area, and density of the BUs composing the four test cities. It shows that, while the area and density may vary across cities, the population statistics are relatively constant. This is not surprising since BUs tend to be designed to have similar populations. The geographical data including the boundaries ...

    work page 2024

Show all 14 references
  1. [32]

    Finally, the final layer converts the latent32-dimension vector into a one-dimensional output

    All three layers use Leaky ReLU activations. Finally, the final layer converts the latent32-dimension vector into a one-dimensional output. For PRED GNN , we maintain the structure proposed by Ferraz et al. (2024), with the exception that we replace the Structure2vec layers wi...

    2024

  2. [1959]

    Bello, H

    I. Bello, H. Pham, Q. V . Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 11

    arXiv

  3. [1985]

    (2024) does not scale well to large instances

    and we observe that the 14 flow formulation proposed by Ferraz et al. (2024) does not scale well to large instances. Hence, we develop the following heuristic. Given a set of edge weights, we first use the modified Kruskal algorithm given in Algorithm

    2024

  4. [2013]

    Sadana, A

    U. Sadana, A. Chenreddy, E. Delage, A. Forel, E. Frejinger, and T. Vidal. A survey of contextual optimization methods for decision making under uncertainty. arXiv preprint arXiv:2306.10374,

  5. [2017]

    Aubin-Frankowski, Y

    P.-C. Aubin-Frankowski, Y . De Castro, A. Parmentier, and A. Rudi. Generalization bounds of surrogate policies for combinatorial optimization problems. arXiv preprint arXiv:2407.17200,

    arXiv

  6. [2020]

    Mandi, J

    J. Mandi, J. Kotary, S. Berden, M. Mulamba, V . Bucarey, T. Guns, and F. Fioretto. Decision- focused learning: Foundations, state of the art, benchmark and future opportunities. arXiv preprint arXiv:2307.13565,

    arXiv

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.