Summary
The paper discusses the development and evaluation of a new method called
DISTRICTNET for addressing districting and routing problems using neural networks.
The approach focuses on minimizing the Fenchel Young loss and generalizing to large
out-of-distribution instances from training on smaller instances. The method involves
a representation of the instances as a set of graph weights learned by GNN. These weights
are fed to a CMST algorithm to obtain the spatial partitioning. Comparative
benchmarks include linear regression models and graph neural networks trained
for cost estimation. Results show that DISTRICTNET can achieve lower costs with
a small number of training examples but benefits from more examples,
with diminishing returns.
Strengths
Some key strengths of the research presented in this paper include a structured learning approach to obtain high-quality solutions to large districting problems, the robustness of the approach to changes in problem parameters, and the ability to generalize to out-of-distribution instances.
Weaknesses
I am not familiar with the routing literature and I had a very hard time to read this paper. The supplementary
material is essential and the authors should consider if the mathematical treatment
of several issues that were not relevant for the algorithm proposed should not be moved to
the appendix in exchange of bringing some of the appendix to the main paper. For example,
I was lost about the district demand and cost features along the paper. This is
explained in the appendix.
The datasets are small, with the number of areas varying between 120 and 983.
They use an additional set of 27 cities, 25 of them with less than 100 areas and a
maxium of 684.
The benchmarks did not include what the authors call the quick heuristic methods.
I also found other recent papers in important venues dealing with this districting
problem by partitioning a minimum spanning tree as in the paper and with simpler
methods.
Teixeira, L. V., Assunção, R. M., & Loschi, R. H. (2019). Bayesian space-time partitioning by sampling and pruning spanning trees. Journal of Machine Learning Research, 20(85), 1-35.
Luo, Z. T., Sang, H., & Mallick, B. (2021). A Bayesian contiguous partitioning method for learning clustered latent variables. Journal of Machine Learning Research, 22(37), 1-52.
Luo, Z. T., Sang, H., & Mallick, B. (2021). BAST: Bayesian additive regression spanning trees for complex constrained domain. Advances in Neural Information Processing Systems, 34, 90-102.
McCartan, C., & Imai, K. (2023). Sequential Monte Carlo for sampling balanced and compact redistricting plans. The Annals of Applied Statistics, 17(4), 3300-3323.