DistrictNet: Decision-aware learning for geographical districting

Authors: cheikh  ahmed
polytechnique  montreal
axel  parmentier
thibaut  vidal
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 22:45:01

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.

Main paper: 
 introduction: 
 Districting aims to partition a geographical area made of several basic units (BUs) into small, balanced, and connected areas known as districts. Districting has a wide array of applications in many areas such as electoral politics (Williams, 1995; Webster, 2013; Ricca et al., 2013) , sales territory design (López-Pérez and Ríos-Mercado, 2013; Zoltners and Sinha, 2005) , school zoning (Ferland and Guénette, 1990) , and distribution (Zhou et al., 2002; Zhong et al., 2007) . These problems are challenging because of the combinatorial complexity of assigning BUs to districts.In this paper, we focus on districting and routing, one of the more complex forms of districting. In that case, the goal is to minimize the routing costs over all districts, where each district is serviced by a vehicle starting from a common depot. Since districting is a long-term strategic decision, the delivery requests in each district are unknown and modeled as a point process. As a two-stage stochastic and combinatorial problem, districting and routing can be solved to optimality only on very small instances. For example, in our experiments, finding the optimal solution of a districting problem with 60 BUs and 10 districts required around 400 CPU-core days. Further, while several heuristic methods have been proposed based on estimating district costs (Daganzo, 1984; Figliozzi, 2007) , they tend to lead the search towards low-quality solutions on large instances (Ferraz et al., 2024) .In this study, we present a structured-learning approach called DISTRICTNET that integrates an optimization layer in a deep learning architecture, as shown in Figure 1 . DISTRICTNET learns to approximate districting problems with a simpler one: the capacitated minimum spanning tree (CMST). DISTRICTNET predicts the cost of each arc of the CMST graph using a graph neural network (GNN) trained in a decision-aware fashion. This surrogate optimization model captures the structure of districting problems while being much more tractable. Using the CMST as a surrogate model is especially relevant because there is a surjection from the space of districting solutions to the space of CMST solutions. In other words, there always exists a CMST solution that is optimal for the original problem. The main challenge is to train a model that can find it. These edge weights parameterize a CMST, which is solved using a black-box combinatorial solver.The CMST solution ŷ is finally converted into a districting solution λ. Training this pipeline in a decision-aware manner requires propagating a loss gradient back to the GNN.DISTRICTNET is trained to imitate a few optimal solutions obtained on small instances. We show that it leads to high-quality solutions for large districting problems and great out-of-distribution generalization. Further, our approach is robust to changes in the problem parameters such as a varying number of districts. This is valuable for practitioners, who usually evaluate a family of problems before picking a solution.Our contributions. We present a structured learning approach to obtain high-quality solutions to large districting problems. The main component of our pipeline is a combinatorial optimization layer, a parameterized CMST, that acts as a surrogate to the original districting problem. We show how to learn from districting solutions by embedding CMST solutions into a suitable space and constructing target CMST solutions from districting ones. This allows training DISTRICTNET by imitation, minimizing a Fenchel-Young loss on a set of target solutions obtained on small instances. The value of our approach is demonstrated on real-world problems as DISTRICTNET generalizes to large problems and outperforms existing benchmarks by a large margin thanks to the combination of GNN and structured learning. While we focus our experiments on districting and routing, the method presented is not tailored to this specific application. DISTRICTNET is generic and could be applied to any geographical districting problem. 
problem statement: 
 We model a geographical area as an undirected graph G = (V, E), where V is a set of vertices representing the BUs and E is a set of edges representing the connections between them. A district d ⊂ V is a subset of BUs. We say that a district d is connected if its graph is connected. Let 1(•) be the indicator function that returns one if its argument is true and zero otherwise. We denote by D the set of connected districts and N = |V | the number of BUs.Routing costs. Let d ∈ D be a connected district. In districting and routing, the cost of a district is the expected distance of the smallest route that satisfies the demand requests. Hence, it is the expected cost of a traveling salesman problem C TSP (d) = E ξ [TSP(d, ξ)], where ξ is the collection of demand requests in a district d.Since the demand is not known a priori, it is modeled as a random variable. We assume that an average demand-generating distribution exists for each basic unit over the planning horizon so that ξ i ∼ D v , ∀v ∈ V . Let v 0 be an additional vertex that represents the depot and is connected to all other nodes. Let also Π(ξ) be the set of all routes that satisfy the demand requests of a district d while starting and finishing at the depot, and denote by dist(π) the total travel distance of a route π ∈ Π. Given a set of demand requests ξ, the minimum transportation costs are achieved by the route that visits all demand locations with minimum distance starting and ending at the depot so that TSP(d, ξ) = min π∈Π(ξ)dist(π).The district cost can be computed through a Monte Carlo evaluation by sampling a large set of demand scenarios and solving multiple independent TSPs. This evaluation is costly for large cities and districts. Therefore, evaluating the cost of a districting solution is hard even if districts can be evaluated in parallel.Districting. The districting and routing problem minimizes the sum of all district costs. Let C TSP (d) denote the cost of a district d. A districting problem can be formulated in a general form asEQUATIONEQUATIONEQUATIONwhere λ d is a binary variable that tracks whether a district is selected. Constraint (1b) states that each BU is selected in exactly one district of the solution. Constraint (1c) specifies that exactly k districts are selected.Additional constraints on the districts can be readily added to the problem. For instance, districting and routing typically aim to obtain districts close to a target size t and include constraints on the minimum and maximum size of a district. Problem (1) can be formulated over a restricted set of districts D r ⊆ D that satisfy the minimum and maximum size constraints. Formally, it ensures that ∀d ∈ D r , d ≤ |d| ≤ d, where (d, d) are user-specified upper and lower bounds on the district size.Although seemingly simple, Formulation (1) has an exponential number of variables. The number of feasible connected districts of size t within a geographical area comprising N BUs is on the order of O((e(δ -1)) t-1 . N t ) where δ is the maximum number of neighbors for a given BU (Komusiewicz and Sommer, 2021) . For instance, a city of N = 120 BUs and a target size of t = 20 with δ = 13 has on the order of 10 29 possible connected districts. The districting-and-routing problem has also been shown to be NP-hard by Ferraz et al. (2024) . Hence, solving Problem (1) to optimality is only possible for small problem sizes.Existing approaches. For real-world cities, evaluating a district's cost is too computationally demanding to be performed at each step of a search algorithm. Existing methods replace the cost C TSP (d) with a surrogate cost estimator. The defining aspect of existing methods is the specific model used to estimate the routing costs. Most approaches are based on the formula of Beardwood-Halton-Hammersley (BHH) , which estimates the distance to connect randomly distributed points (Beardwood et al., 1959) . This formula has been embedded into a hybrid search method combining a gradient method and a genetic algorithm (Novaes et al., 2000) and an adaptive large neighborhood search metaheuristic (Lei et al., 2015) . Extensions of the BHH formula include Daganzo (1984) , who adapted it for routing problems, and Figliozzi (2007) who extended it further for non-uniformly distributed demand requests. Recent works have shown that the BHH formula estimates stochastic TPS costs remarkably well empirically against more sophisticated regression functions for uniform distributions (see, e.g., Kou et al., 2022) . Most closely related to our work, Ferraz et al. (2024) trained a GNN to predict district costs and embedded it in an iterative local search algorithm. They focused on solving single districting instances but did not investigate the generalization capabilities of their approach.In contrast to the literature, we learn to approximate districting problems by using a surrogate optimization problem trained in a decision-aware fashion. An advantage of this framework is that it applies to a wide range of constrained partitioning problems: it can work with any general districting cost function C(d). Hence, it could readily consider other metrics such as fairness, balancing and compactness of the district.Multi-instance learning and generalization. Often, practitioners do not solve a single districting problem but study a family of problems with varying settings and parameters. Because there is a substantial effort needed to train a model, our goal is to obtain a pipeline able to solve multiple instances of districting. In our setting, generalizing over multiple instances means being able to generalize across:• Cities: each city has unique geographical and social characteristics, which affect the optimal districting solution. Our model should be able to identify the impact of these differences on districting and provide high-quality solutions for different cities.• Instance sizes: the model should be able to handle instances with a different (typically larger) number of BUs than it was trained on. Since the training effort increases with the number of BUs, this allows solving large instances with a small training budget.• Problem parameters: the model should be able to generalize to slight variations in the problem parameters, such as the minimum and maximum size of districts.3 DISTRICTNET: From CMST to Districting DISTRICTNET takes as input a labeled graph containing all the data of an instance. A graph neural network ϕ w turns this labeled graph into edge weights. These weights parameterize a CMST instance, which is then solved using a dedicated algorithm. The CMST solution is then converted into a districting solution.The first component of DISTRICTNET is a GNN ϕ w : R d f → R that assigns a weight to an edge depending on its feature vector. Applying this model to all edges of an instance returns a vector of edge weights θ ∈ R |E| . Our model is made of two components: graph convolution layers that learn latent representations of graph edge features, and a deep neural network that converts these latent representations into edge weights.The GNN is made of L graph convolutional layers that update the features of edges through message passing. Following Morris et al. (2019) , the update rule at the l-th layer is given byEQUATIONe is the feature vector of edge e at the l-th layer, σ is a non-linear activation function, W 0 and W 1 are learnable weight matrices, and N (e) is the set of neighboring edges of an edge e. Convolutional layers allow to capture the structure of the graph while being able to apply the prediction model to any graph size and connectivity structure. After the convolutional layers, a fully connected deep neural network transforms the latent representation produced by the GNN into an edge weight.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] .Justification: The paper states all important assumptions when stating the problem in Section 2. The main limitation is that, although our approach could be applied to a wide variety of partitioning problems, this paper focuses only on districting and routing. This is discussed in the conclusion.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
combinatorial optimization layer: 
 The second component of DISTRICTNET is the CMST layer parameterized by the vector of edge weights θ. This layer acts as a surrogate for the original districting problem. The CMST is a wellstudied graph optimization problem based on the minimum spanning tree problem. A minimum spanning tree is the subset of edges of a weighted graph that spans all vertices of the graph while minimizing the sum of the weight of its edges. Classically, the CMST extends this problem with the constraint that the number of vertices in each subtree does not exceed a predetermined capacity.Let T be the set of connected subtrees with minimum and maximum size (d, d) . We consider that an edge e is in a subtree s if both its extreme points are inside the subtree. The CMST problem with a target number of subtrees is then given byEQUATIONEQUATIONEQUATION)Formulation (3) highlights the strong link between the CMST and the districting problem in (1). Both problems partition a graph into connected components with cardinality constraints. Any CMST solution can be converted into a districting solution by collecting all the nodes of a subtree into a district. Since several subtrees lead to the same district, this is a surjective mapping from the space of subtrees T to the space of districts D. This also implies that, for any districting problem, there always exists a CMST problem such that their optimal solutions coincide.Solving the CMST. Solving CMST problems is much more amenable than solving districting problems since it is a single-stage optimization problem with a linear objective. However, it remains a combinatorial problem. Several methods have been proposed to solve it, ranging from expensive exact methods to quick heuristics.DISTRICTNET is agnostic to the choice of CMST solver. In our experiments, we use the exact formulation in (3) to solve small instances to optimality, and we apply an iterated local search (ILS) heuristic for large instances. ILS alternates between two steps: (i) a local improvement step that guides to a local minimum, and (ii) a perturbation step to diversify the search. A key component of the algorithm is the initial solution. Randomly allocating BUs to districts is unlikely to return feasible solutions and, even when it does, it often leads to very poor solutions. Here, we use a modified Kruskal algorithm to exploit the structure of the CMST and quickly find a good initial solution. The details of our implementation of the ILS are given in Appendix A.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] .Justification: Our main theoretical result is that the randomized reconstruction introduced to construct CMST targets from district targets leads to the Fenchel-Young loss. The steps needed to recover this result are described in details in Section 4.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
training districtnet by imitation: 
 DISTRICTNET is trained to imitate the solutions of a training set x i , λin i=1 . Each instance x i = (G i , f i ) is a labeled graph with G i = (V i , E i ) the instance graph and f i = f e i ∈ R d f ,∀e ∈ E i the set of edge feature vectors. A target districting solution λi is associated with each instance x i . Since producing optimal or near-optimal districting problems is hard, building this training set is expensive. Thus, we train our model on a dataset of small instances with the hope that it generalizes well on large instances. Training DISTRICTNET by imitation amounts to solvingmin w n i=1 L ϕ w (x i ), ȳi ,where L : (θ, ȳ) → L(θ, ȳ) is a loss function that quantifies the distance between a CMST solution corresponding to the edge weights θ with a target CMST solution ȳ. However, our training set does not contain any CMST targets but only districting targets. Training DISTRICTNET is thus achieved by three main steps: (i) introducing a new embedding of CMST solutions, (ii) converting districting targets λi into CMST targets ȳi , and (iii) defining a suitable loss function with desirable properties and deriving its gradient.A CMST solution is entirely characterized by its edges. We can therefore build an embedding Y of the set V of solutions ν of the CMST problem given in (3) in R |E| as Y = y(ν) : ν ∈ V} where y(ν) = y e (ν) e∈E and y e (ν) = s∈T ν s 1(e ∈ s). We can then reformulate Problem (3) asEQUATIONwhere, with a slight abuse of notation, we changed the problem from min to max, which is without loss of generality. Since Y is finite, its convex hull C is a polytope. Therefore, the linear program given by max µ∈C θ ⊤ µ is equivalent to Problem (4). The change of notation from a vertex y to a moment µ emphasizes that µ takes values inside the convex hull C. We now use the shorthand notation µ * (θ) to denote an optimal solution to argmax µ∈C θ ⊤ µ.From Districting to CMST. As discussed previously, there is a surjection from the space of CMST solutions to the space of districting solutions. Given a target districting solution λ, we denote by Y( λ) the set of feasible CMST solutions that lead to λ.To recover a target CMST solution, we introduce the constructor algorithm A : λ → y that maps a districting solution λ to a CMST solution y ∈ Y(λ). This algorithm can be randomized. For instance, DISTRICTNET constructs districting solutions by solving a minimum spanning tree problem with random edge weights for each district d ∈ λ. This can be efficiently done by applying Kruskal's algorithm in parallel for all the selected districts.Finally, we define our target CMST solution μ ∈ C asEQUATIONwhich is taken as an expectation over the realizations of the randomized algorithm A. This allows us to convert our training set x i , λi Let μ be a target CMST solution. We want DISTRICTNET to minimize the non-optimality of µ * (θ) compared to the target μ, that is, minimizing the loss max µ∈C θ ⊤ µ -θ ⊤ μ. Minimizing this loss directly does not work because θ = 0 is a trivial optimal solution. However, given a smooth strictly convex regularization function Ω(y), we can define the regularized problem (Blondel et al., 2020) EQUATIONand the smoothed version of the non-optimality loss as:EQUATIONDenote by Ω * (θ) the Fenchel conjugate of Ω, the regularized loss in Equation ( 7) is equal to Dalle et al., 2022) , which we recognize as the Fenchel-Young inequality (Blondel et al., 2020 ). Fenchel's duality theory then ensures that this loss has desirable properties. Notably, it is convex in θ, non-negative, equal to 0 only if ȳ is the optimal solution of ( 6), and its gradient can be expressed asL FY (θ, μ) = Ω * (θ) + Ω(μ) -θ ⊤ μ (∇ θ L(θ, μ) = argmax µ∈C θ ⊤ µ -Ω(µ) -μ.Practically, it remains to choose a suitable regularization function Ω. When using a black-box oracle, a convenient choice that exploits the link between perturbation and regularization (Berthet et al., 2020; Dalle et al., 2022) is to define Ω(µ) as the Fenchel dual of the perturbed objectiveF (θ) = E max µ∈C (θ + Z) ⊤ µ, where Z is a random variable with positive and differentiable density on R |E| . In that case, the gradient of the Fenchel Young loss with respect to θ can be computed as (Berthet et al., 2020 )EQUATIONA stochastic gradient can therefore be conveniently computed using the Monte Carlo approximation Summary. The novelty of our approach lies in our reconstruction of a CMST moment μ from a districting solution λ, which can be seen as a partially specified target ȳ. Alternatives in the literature generally consider completing the partially specified solution into the fully specified solution that minimizes the Fenchel Young loss (Cabannnes et al., 2020; Stewart et al., 2023) . Our approach has the advantage of leading to the classic Fenchel Young loss, which is convex, whereas the infinum loss of Stewart et al. (2023) is only a difference of convex functions.1 M M m=1 argmax µ∈C (θ + Z m ) ⊤ µQuestion: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] .Justification: The paper includes all the details needed to implement and reproduce our experiments. This includes but is not limited to providing all hyperparameter values as well as pseudo-code for the key algorithms. 
numerical study: 
 We now evaluate the performance of DISTRICTNET on real-world districting and routing problems. We run repeated experiments and compare our approach to other learning-based benchmarks. We investigate the following aspects of DISTRICTNET: (i) its ability to generalize to large out-ofdistribution instances from training on a few small instances, (ii) to variations in the instance parameters such as the district sizes, (iii) the role of the CMST surrogate model to allow this generalization.Our experiments are implemented in Julia (Bezanson et al., 2017) except for the district evaluation methods, which are taken from Ferraz et al. (2024) and implemented in C++. All experiments are run on a computing grid. Each experiment is run on two cores of an AMD Rome 7532 with 2.4 GHz and is allocated 16 GB RAM. The code to reproduce all experiments presented in this paper is publicly available at https://github.com/cheikh025/DistrictNet under an MIT license.Our instances include all the real-world cities in the United Kingdom used by Ferraz et al. (2024) and we extend it with additional cities in France. Hence, our test set contains seven real-world cities in the United Kingdom and France (Bristol, Leeds, London, Lyon, Manchester, Marseilles, and Paris), which contain between 120 and 983 BUs. Our goal is to provide high-quality solutions for several values of the target district size t. This target size sets the bounds (d, d) on the district size t ± 20% and the target number of districts as k = ⌊N/t⌋.Features. Each BU is summarized by a set of characteristics including its population, density, area, perimeter, compactness, and distance to the depot. For test instances, these summarizing statistics are taken from real-world data. The edge feature vector is constructed by averaging the feature vectors of the two BUs it connects. Additionally, we include the distance between the center of the two connecting BU into the edge feature vector. Thus, an instance is fully described by its geographical and population data.Training set. To assemble a large and diverse training set, we generate new cities by perturbing real-world ones. First, we read the geographical data of 27 real-world cities in England (excluding the ones from the test set). From these initial cities, we generate n = 100 random connected subgraphs of size N = 30 BUs and sample the population of each BU according to a normal distribution N (8 000, 2 000) truncated between 5 000 and 20 000. For each instance x i , we compute its optimal solution for the target size t = 3 by fully enumerating the possible districting solutions and evaluating their costs. This procedure generates our training set of n = 100 instances and associated solutions.Benchmarks. We evaluate our method against four benchmark approaches that are based on learning estimators of district costs C TSP (d). They can be combined with any search method. In these experiments, they are also integrated within an ILS with a time limit of 20 min.We include (i) the method of Daganzo (1984) (BD), (ii) the method of Figliozzi ( 2007 2024) train a GNN model to predict district costs for a fixed city and set of problem parameters and show that this approach outperforms BD and FIG.Since our focus is on generalization to multiple cities and problem parameters, our implementation extends the one of Ferraz et al. (2024) : we train a single GNN using data from multiple small cities and evaluate its ability to generalize out-of-distribution. In contrast, AVGTSP estimates district costs by solving a TSP over the barycentres of all BUs within a district. This is a single-scenario approximation of the original stochastic districting problem that considers the expected demand realization in each BU.The above benchmarks do not use a surrogate optimization model. Instead, they are trained in a traditional supervised learning fashion: to minimize the cost-estimation error on a training set of 10 000 districts and true costs taken from the same training instances as DISTRICTNET.The details of our simulation setting, implementation, and additional experimental results are provided in the appendix.We evaluate the ability of the different methods to generate good solutions on a diverse set of outof-distribution instances. All methods are evaluated using the same performance metric: the total districting cost C TSP (d) of a districting solution as presented in Problem (1), where the expected costs are evaluated using a Monte Carlo approximation. We restrict the cities to N = 120 BUs and vary the target district size t ∈ {3, 6, 12, 20, 30} for each of our seven test cities. This provides a set of 35 test instances, completely independent of the training data. The results are presented in Table 1 in the form of an ablation study. The table shows the relative difference in average costs achieved by each method on the test instances and the statistical significance is assessed using a one-sided Wilcoxon test. Example districting solutions are also given in Figure 2 .Table 1 shows that DISTRICTNET consistently outperforms the benchmarks as it produces districting solutions with significant cost reductions of around 10% compared to all other methods. The benchmarks all provide similar performance, even PREDGNN, which uses a graph neural network but does not use structured learning. This highlights the ability of DISTRICTNET to generalize across various city structures and for larger instances thanks to the combination of a graph neural network and a differentiable optimization layer.Result 1. DISTRICTNET can solve a large family of districting problems with varying geographical and population data as well as varying problem parameters. We perform an additional experiment to investigate the generalization to cities of large sizes. In Figure 3 , we show the cost of the districting solution obtained with the benchmark methods relative to DISTRICTNET for varying city sizes. A value greater than 100% means that the benchmark performs worse than DISTRICTNET. We increase the number of BUs for each city and keep constant the target number of BUs in a district as t = 20. The time limit of ILS is kept to 20 min for all methods when N < 400 and increased to 60 min when N ≥ 400. 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 large instance with 2,000 BUs in the Ile-de-France region. Each method is allowed 60 minutes to compute the districting solution, with the target district size set to 20 BUs. The results are presented in Table 2 . DistrictNet provides the best performance, showing that it generalizes even to instances that are more than 60 times larger than the training ones.Result 2. DISTRICTNET provides high-quality solutions to even the largest real-world problems.Why does unstructured learning fail? One potential explanation for the poor performance of the benchmarks, in particular for PREDGNN, is the change in distribution between the training and test instances. As shown in Figure 4 , the distribution of district costs varies greatly with the city and parameters. Since there is a shift in the data-generating distribution, the benchmarks, which ignore the structure of the districting problems, are not able to accurately predict the district costs resulting in poor overall performance. The value of data for decision-aware learning. Finally, we investigate the value of training data for DISTRICTNET. In Figure 5 , we study the out-of-distribution performance of DISTRICTNET as the size of the training set increases. We show the average districting cost over all cities and target sizes relative to the cost for n = 20 and add a 95% confidence interval as a shaded area. A value smaller than 100% means that DISTRICTNET improves compared to its training with n = 20. The figure shows that DISTRICTNET can achieve low costs even with a surprisingly small number of training examples (n = 50). Increasing the number of examples tends to improve the results although with a diminishing return. Result 4. DISTRICTNET can be trained with a small computational budget and benefits from increasing the number of training examples.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] .Justification: The code used to generate all experiments in this paper is joined as supplementary material. It will be made openly available on an online repository under an MIT license after publication. Our submission includes a ReadMe file indicating how to run all experiments in the paper.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
related literature: 
 In this work, we find near-optimal solutions to complex combinatorial problems by introducing a combinatorial layer in a deep neural network trained in a decision-aware fashion. Our work lies at the intersection of the learning-to-optimize literature and decision-aware learning.Learning to optimize. Recent years have seen a significant increase in the use of machine learning for solving hard combinatorial optimization problems. Several graph-based learning approaches have been proposed for general combinatorial problems (Cappart et al., 2023) . Deep reinforcement learning has been applied to solve typical combinatorial problems such as the traveling salesman and knapsack problems (Bello et al., 2016) and the minimum vertex cover and maximum cut problems (Dai et al., 2017) . Gasse et al. (2019) presented a technique to improve the branch-and-bound process in mixed-integer linear programming by using graph convolutional neural networks.The main advantage of learning-based methods is that, after a potentially expensive training procedure, they can generate good solutions to combinatorial problems in a short time. This has been shown to be effective in solving routing problems, which are complex combinatorial problems. Joshi et al. (2019) applied a beam search to solve the Euclidean TSP using GNNs and show notable improvements in solution quality, speed, and efficiency. Kool et al. (2019) combined a greedy rollout baseline and a deep attention model to solve several challenging routing problems such as the orienteering problem and the prize-collecting TSP.Decision-aware learning. Decision-aware learning, on the other hand, looks into including an optimization layer in deep learning architectures. A key challenge in this area is to propagate a meaningful gradient through this non-smooth layer. Amos and Kolter (2017) developed a method to compute the gradients of quadratic programs by differentiating the Karush-Kuhn-Tucker optimality conditions. In the case of (integer) linear programs, propagating this gradient can be performed for instance by introducing a log-barrier term to the LP relaxation (Mandi and Guns, 2020) , using a piecewise-linear interpolation technique (Vlastelica et al., 2019) , or using perturbation (Berthet et al., 2020) . We refer the interested reader to Mandi et al. (2023) and Sadana et al. (2023) for surveys on decision-aware learning and its generalization as contextual stochastic optimization. Decision-aware learning has diverse applications such as approximating hard optimization problems by learning linear surrogate models (Ferber et al., 2023; Dalle et al., 2022) .Decision-aware learning allows the integration of complex algorithms with combinatorial behavior into deep learning architectures. Wilder et al. (2019) learn to solve hard combinatorial problems by learning from incomplete graphs using a differentiable k-means clustering algorithm. Stewart et al. (2023) present a differentiable clustering approach with a partial cluster-connectivity matrix. Our paper differs in two significant ways. First, we use a surrogate model with substantially more structure than clustering since it includes constraints on the size of the districts. This raises computational challenges, since the surrogate model remains NP-hard, but allows significant benefits in the quality of solutions. Second, while we have "full" districting solutions available, i.e., we know exactly what nodes need to be in the same clusters for a given training example, we have no information on the corresponding CMST solution. This leads us to introduce a randomized target construction algorithm, which leads to a well-defined loss function with advantageous properties.Our approach belongs to the research stream that learns to approximate hard problems by easier ones. Key advantages of these approaches include being efficient at inference time since most of the computation effort is shifted offline, and great performance on test instances if they remain close to the training distribution. There are also downsides. First, until now, there are no known worst-case theoretical guarantees on the quality of the solution. Second, learning may be intensive computationally, both when generating the training instances and in the training algorithm. We refer the reader to Aubin-Frankowski et al. ( 2024) for a general discussion of these aspects and an analytical characterization of generalization bounds.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] .Justification: The key aspects of our experimental setting are described at the beginning of Section 5 and the full details are provided in the appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion: 
 This paper presented a general pipeline to learn to solve graph-partitioning problems. It integrates a CMST as a surrogate optimization layer, which allows it to capture efficiently the structure of graph partitioning while providing solutions in a short time. We demonstrate the value of our pipeline on a districting and routing application. We show that our method outperforms recent and traditional benchmarks and is able to generalize to out-of-distribution instances. Thus, it can be trained on a small set of examples and applied to a wide array of cities, instance sizes, and hyperparameters.Future work could investigate alternative approaches to solve the CMST problem during training and testing, such as exact methods based on column generation, which would integrate seamlessly with the pipeline presented in this paper. A limitation of our approach is applying DISTRICTNET only to districting and routing. Other geographical partitioning problems such as designing voting or school districts could be considered in future research.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] .Justification: We perform a statistical analysis of the results and include it in the ablation study in Table 1 . Figure 5 also includes a confidence interval.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] .Justification: The characteristics of the worker is given at the beginning of Section 5.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] .Justification: We have reviewed and the NeurIPS Code of Ethics and consistently adhere to it.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] . Justification: Our work focuses on solving a hard combinatorial problem in short time. It focuses on a logistic application. To the best of our knowledge, there are no negative societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] . Justification: In our view, the paper does not pose a risk of misuse. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] . Justification: The creators of the code reused in this paper are properly credited, both in the main body and appendices. When possible, a link to the source of the assets is provided. 
 
 Appendix: In this part, we provide details on the four methods considered in this paper and their implementations. We include:• in Appendix A.1 an illustration of how DISTRICTNET converts a districting problem into a CMST problem, and the training algorithm of DISTRICTNET, • in Appendix A.2 the pseudo-code algorithm of ILS and its main components, and • in Appendix A.3 background details on our benchmarks used in this paper as well as the architecture and hyperparameters used in our experiments.First, we show an illustrative example to highlight the similarity between districting problems and CMST problems. Then, we provide the algorithms used to train DISTRICTNET.We illustrate the link between districting problems and CMST problems in Figure 6 . First, we show a simple districting instance with N = 7 BUs with the source node shown as a yellow star. In Figure 6 (b), we show the corresponding CMST instance that would be obtained when applying DISTRICTNET to predict the edge costs. The width of each edge is shown proportional to the edge's weight. In Figure 6 (c) we show the solution of this CMST instance. The solution has two subtrees stemming from the source node. Each subtree corresponds to a district. DISTRICTNET is trained following Algorithm 1. The hyperparameters of DISTRICTNET include the typical ones used in deep learning (number of epochs, batch size, learning rate) as well as the hyperparameters of the perturbation (number of samples M and temperature ε). We note again that, in our implementation, DISTRICTNET uses the exact approach to solve each perturbed CMST, which is based on enumerating all the possible districting solutions and solving the exact formulation given in (3). for all (x, y) in B do 6:Predict edge costs θ ← ϕ(x)7:Sample perturbations Z (1) , . . . , Z (M ) ∼ N (0, 1)8:for m = 1 to M do 9:Perturb edge costs θ (m) ← θ + εZ (m) 10:Solve perturbed CMST to obtain y (m) 11:end for 12:Average perturbed solutions ŷ ← 1 M M m=1 y (m) 13:Evaluate gradient of FY loss ∇ θ L FY (y, ϕ(x))14:Make gradient step on parameters of ϕ 15:end for 16:end for 17: end for 18: Return Trained model ϕAll districting and CMST problems on large instances are solved using ILS. The detailed algorithm is given in Algorithm 2. ILS iteratively applies two methods: a local search that guides a solution to a local optimum, and a perturbation that explores the solution space. The local search algorithm is given in pseudocode in Algorithm 3. 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 the results of Ferraz et al. (2024) A feasible districting or CMST solution is a set of connected BUs of size k, where each subset has a number of BUs within the minimum and maximum acceptable size. Obtaining a feasible solution that satisfies these constraints is already NP-hard (Dyer and Frieze, 1985) and we observe that the 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 4. This algorithm starts with all nodes in their own cluster and sorts all edge weights in increasing order. Then, it greedily merges clusters on the extreme points of the edges with lowest cost if the size of the merged cluster is below the maximum size. This provides a first solution that may still have too many clusters. In that case, we run the greedy merging algorithm given in Algorithm 5. This algorithm further reduces the number of clusters by continuously merging the two neighboring clusters that have the smallest combined size until the number of clusters meets the desired target k. However, the initial solutions obtained may not always meet the limit size requirements. To address this, we have incorporated a penalty function in the local search algorithm, which penalizes clusters not conforming to size limits, thereby guiding the local search towards feasible solutions. In our experiments, a feasible solution is thus almost always found at the first iteration of the ILS algorithm.Empirically, this method efficiently finds feasible initial solutions in our main experiments. However, they are not sufficient for the largest instances (when N ≥ 600 in our experiments). Thus, we introduce an additional repair algorithm given in Algorithm 6, which is used only in the experiment presented in Figure 3 . 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. Daganzo (1984) , BD estimates the cost of a district asEQUATIONwhere A d = i∈d a i represents the total area of the district with a i being the area of the i-th BU, and R d denotes the expected number of demand requests within the district. The term ∆ d is the average distance between the depot and a demand point. Because we do not make assumptions on the shape of the BUs, we compute this term using a Monte Carlo approximation. The parameter β is a parameter that adjusts the influence of area and demand on the cost. Hence, BD is a linear regression and training it amounts to finding the right value for β.Following Figliozzi (2007) , the cost of a district is given byEQUATIONwhere β = (β 1 , β 2 , β 3 , β 4 ) now represents a vector of parameters that modulates the cost estimation.Clearly, FIG is an extension of BD and we train it in the same way.PREDGNN. Following Ferraz et al. (2024) , PREDGNN uses a GNN to estimate the cost of a district, i.e., dist PREDGNN (d) = Φ(G d ), where Φ is the trained GNN and G d is a district graph. The district graph is a labeled graph where each node i ∈ d is described by the featuresEQUATIONwhere p i is the population of the BU i, q i its perimeter, a i its area, ρ i its density, δ i its distance to the depot, and e id is an inclusion variable that takes the value 1 if BU i belongs to the district d and 0 otherwise. The GNN processes G d to learn a latent representation that captures the structure of the district. This is done in two phases. First, a message-passing algorithm is applied at the node level, then an aggregation layer summarizes the whole graph into a single latent vector. This latent graph representation is then fed to a feedforward NN to predict the district cost. This architecture is summarized in Figure 7 .Example districtx iLearning model: GNN and feedforward NN h(x i )Cost estimate 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, which outputs a cost estimate.Key differences with DISTRICTNET. PREDGNN and DISTRICTNET both use GNN to learn the structure of labeled graphs. PREDGNN uses node-based features available at the BU level. In contrast, DISTRICTNET uses edge-based features, averaging the attributes of the two BUs connected to each edge. Hence, while PREDGNN focuses on the properties of individual BUs, DISTRICTNET also captures the spatial relationships between connected BUs. Further, DISTRICTNET does not use the final aggregation layer for global graph embedding of PREDGNN since it is applied independently to each edge. This allows a finer-grained representation of the graph.AVGTSP. This benchmark replaces the districting-and-routing problem in Equation ( 1) by the surrogate optimization problem given byEQUATIONthat is, it exchanges the min and expectation operations in the objective function of the original problem. This yields a deterministic problem, where the expected districting cost is approximated by the cost of the expected demand in each BUs. In many stochastic problems, this approach often leads to poor results (see e.g., Chapter 4.2 of Birge and Louveaux (2011) ). This is because this approximation ignores the variance of the random variable ξ.Still, we implement this method as a non-learning-based baseline. In our setting, the demand distribution is known and the expected demand in each BU can be easily computed. For each BU, the average demand request E ξ [ξ] is a single request that appears at the barycentre of the area. Evaluating a district cost thus reduces to solving a TSP over the barycentres of all its BUs. As for all other methods, we integrate this approximation in an iterated local search.Several hyperparameters control the different methods used in this paper. We give here the architectures and hyperparameters used in all our experiments. We also provide a summary of the computational effort for training the model in Table 3 . The table illustrates well the two main sources of computational efforts for the GNN-based methods. The training time of PREDGNN is relatively longer because it uses a large number of district costs examples. On the other hand, DISTRICTNET needs to evaluate more districts to find the optimal solutions of its 100 training instances but is quick to train. This can be seen in the second column of Table 3 that shows the number of districts whose cost is evaluated to compute the optimal solution of n = 100 instances. Notably, the district cost evaluation can all be performed in parallel. Architecture. The GNN of DISTRICTNET uses three graph convolution layers, each with a hidden size of 64 and Leaky ReLU activation functions. The DNN section uses three dense layers: two layers mapping with 64 inputs to 64 outputs and then one layer with an output of size 32. All three layers use Leaky ReLU activations. Finally, the final layer converts the latent 32-dimension vector into a one-dimensional output.For PREDGNN, we maintain the structure proposed by Ferraz et al. (2024) , with the exception that we replace the Structure2vec layers with GraphConv layers. The update rule for the GraphConv layers isx t+1 i = ReLU(W 1 x t i + j∈N (i) W 2 x t j ), where W 1 and W 2 are the weight matrices and N (i) is the set of neighbors for node i. In contrast, the Structure2vec update rule applied in the original model isx t+1 i = ReLU(W 1 x t i + W 2 j∈N (i) x t j ). This is a minor modification and should not alter its performance, as also stated by Ferraz et al. (2024) .The architecture of PREDGNN thus consists of four GraphConv layers. Each layer has a hidden size of 64 units and uses ReLU activation functions. The final layer produces an output of size 1028. We then aggregate these node embeddings to form a global graph embedding. This global embedding is initially processed by a feedforward layer, resulting in a 100-dimensional vector. A second and final layer reduces this to a single output, representing the cost of the district.Hyperparameters. The only hyperparameter of BD and FIG is the number of samples used in the Monte Carlo approximation of the average distance to requests. We use 100 scenarios in all our experiments.PREDGNN uses a batch size of |B| = 64, a learning rate of 1e -4 , and train the model for 10 4 epochs. We further set a time limit of 24 hours for training and stop the process early if no significant change of the loss (i.e., greater than 1e -4 ) is observed in the last 1 000 epochs.DISTRICTNET uses a batch size of |B| = 1 and a learning rate with initial value of 1e -3 with a decay rate of 0.9 applied every 10 epochs and a minimum rate of 1e -4 . The model is trained for 100 epochs. The target CMST solution in Equation ( 5) is constructed using a single observation of our random constructor (Kruskal with random weights). The perturbation Z is set to a multivariate standard Gaussian and we M = 20 samples to approximate the expected gradient in Equation ( 8). The randomized target constructor uses 1 000 samples.In this part, we describe how to collect and generate the real-world data used in all experiments. First, we describe the test instances, the four large cities on which we evaluate all the methods. Then, we present how we use real-world data to generate a set of training instances that can be arbitrarily large. We also discuss the distributional assumptions used to simulate the random demand over a city.We use the four cities of Bristol, Leeds, London, and Manchester for our test instances. A summary of these instances is given in Table 4 . 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 of each city and BUs can be accessed at Uber Movement: https://movement.uber.com/. Additionally, census data is available at the Office for National Statistics (ONS) website: ONS. For the French cities, geographical data including the boundaries were obtained from Opendatasoft. Population data for these regions was sourced from the National Institute of Statistics and Economic Studies (INSEE) available at INSEE. For our experiments, we utilize real-world data from a diverse set of 27 cities shown in Table 5 . Apart from two outliers, these cities are smaller than our test instances, with around 30 to 50 BUs. While we read the true boundaries of the cities, we generate their population randomly. We use a normal distribution N (8 000, 2 000) truncated within the range [5 000, 20 000] to be close to the true population distribution of BUs.To generate the city graphs used in the training of DISTRICTNET, we sample randomly connected subgraphs from the train cities. The training instance generation process is given in pseudocode in Algorithm 7, and the subgraph sampling algorithm is given in Algorithm 8. 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. We suppose that the demand within each BU follows a fixed distribution. In each period (e.g., a day), a number of demand requests in each BU. The number of demand requests follows a Poisson distribution with the rate being proportional to the population density of the BU, expressed as n × κ. Here, n represents the population count of the BU, and κ is set to 96/(8 000 × t). This value of κ is selected to realistically approximate a scenario where a district typically handles around a hundred stops. Each demand request is located randomly with a uniform distribution over the geographic location covered by the BU.Evaluating the cost of a district requires solving a stochastic TSP since C TSP (d) = E ξ [TSP(d, ξ) ]. This is done through a Monte Carlo estimation. To accurately estimate the operational costs of our districting solutions, we sample 100 demand scenarios for each basic unit. For each district, we collect the demand requests from the BUs it contains and solve 100 independent TSP problems. We then evaluate a district's expected operational cost by averaging the calculated TSP costs.Each TSP is solved using the Lin-Kernighan-Helsgaun (LKH) algorithm (Lin and Kernighan, 1973; Helsgaun, 2017) . We use the publically available implementation from: http://akira.ruc.dk/ ~keld/research/LKH-3/. This heuristic is widely accepted as a state-of-the-art heuristic for TSPs. It is based on a local search strategy that consistently returns near-optimal solutions. Justification: The claims presented in the abstract and introduction accurately reflect the paper's contributions and scope and are substantially supported by the experimental results.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: This paper introduces and evaluates a new learning to optimize approach to solving districting problems. The paper's strengths include the following: it focuses on a class of problems that is common in practice and should be of interest to a broad audience; the paper's approach identifies and exploits a novel relationship between CMST and partitioning; and an experimental analysis on real-world data sets show that the approach (1) outperforms a range of benchmark approaches representative of various threads of prior work on this problem (including a additional benchmark approach proposed by one of the reviewers and added during the review period), and (2) shows great ability to generalize to large-scale problems. The major weakness of the paper is that the presentation is confusing in many spots. It is unclear in its explanations of some key technical aspects of the approach and, in other places, assumes background information that can only be found in the supplementary material, all of which leads the reader in doubt abut the significance of the paper's contributions. The reviewers have made several suggestions for how to improve the presentation, and in the discussion period, the authors proposed revisions that make the paper's technical contributions clearer and have satisfied reviewer concerns. Please incorporate all of your proposed additions and revisions in the final version of the paper.

Reviews: review: paper_summary: paper_summary: The authors use CMST to solve the problem of districting and routing in large scale scenarios. Finding the relationship between CMST and partitioning is quite beneficial for researchers engaged in related research. 

However, it is worth noting that the authors only report the performance of the model on the 'cost' metric, and do not investigate the performance of the method on the common metrics of traditional districting task. What's more, they do not discuss the efficiency of the method. I hope that the authors can supplement this. 

Another problem is that the baseline methods compared seem to be relatively old except for PREDGNN. The districting methods I know in terms of road network, such as CCH, have not been used as the baseline method. I hope the author can clarify the criteria for baseline selection.
strength_weakness: strength_weakness: It is worth noting that the authors only report the performance of the model on the 'cost' metric, and do not investigate the performance of the method on the common metrics of traditional districting task. What's more, they do not discuss the efficiency of the method. I hope that the authors can supplement this. 

Another problem is that the baseline methods compared seem to be relatively old except for PREDGNN. The districting methods I know in terms of road network, such as CCH, have not been used as the baseline method. I hope the author can clarify the criteria for baseline selection.
questions: questions: Please see the weaknesses.
limitations: limitations: Yes. The authors claim that though the proposed method can be applied to a wide variety of partitioning problems, they only focus on the districting and routing problem in this paper. In fact, I think it's a very valuable question to discuss because the evaluation metric of the partitioning problem and that of the districting and routing problem are different. I think it is necessary for the authors to give more explanation of why their method can be applied to a wider range of partitioning problems.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Add "routing" to the paper title.

Each benchmark method has a different definition of a district cost. The outputs of each of 
these algorithms are a result of these different cost definitions or are due to their 
different approaches?
limitations: limitations: This is a theoretical paper with no immediate connection to societal impact.
paper_summary: paper_summary: This paper tackles the problem of geographical districting through decision-aware learning. The problem is challenging due to the large combinatorial number of possible district designs. By generalizing the GNN-based method (similar to [Ferraz et al.2024 arXiv]) based on decision-aware learning through the Fenchel-Young loss, the proposed method showed much better relative performance to the existing methods.
strength_weakness: strength_weakness: - Some unclear explanations of using GNN, compared with the existing work [Ferraz et al. 2024]; some parts just follow [Ferraz et al. 2024]. These points raise the insufficient explanation of the technical contributions.
- Datasets are not explained semantically (i.e., geographical differences, why these cities are selected, etc.) in the main text: It is important to explain the importance of the task and used datasets (I understand the page limit and appendix).
questions: questions: - I am not sure why we should evaluate the p-value in this setting. Where does the randomness come from?
- I understood that the average demands are required. Once BU and average demands are fixed, the solution seems to be (almost) unique. Can we combine some learning-based demand predictors? If the estimation is not correct, how can the districting results be affected? Some questions could be about district costs.

~~~

After discussions, I have updated my score.
limitations: limitations: In my opinion, the authors have addressed the issue adequately and mentioned these points.
paper_summary: paper_summary: This paper propose an ML-based method to solve districting problems that are known to be challenging. The core idea is to first convert the districting problem to a simpler capacitated minimum spanning tree problem and then leverage the existing learning to optimize method to perform imitation learning. Such conversion is valuable because the learning to optimize approach requires repeatedly solving the optimization problem of interest. Extensive numerical studies were presented, leading to a rich set of insights. I found the paper inspiring.
strength_weakness: strength_weakness: - The paper focus on a specific problem class (that is of common interest). The paper can benefit from drawing connections to other problem classes. The idea of converting a harder problem to an easier problem to enable the application of learning to optimize techniques is general and has potential. And I believe there should exist many other examples, in transportation and beyond. Conducting additional experiments on other problems is probably out of the scope of this paper, but it'd be great if the author can add more discussions related to its broader applicability. 

- Discussion/comparison related to some benchmarks from the OR/optimization community are missing. For example, when the demands are uniformly distributed, I believe the second-stage TSP objective value has some very nice closed-form approximations (see literature related to continuous approximation). Such approximation usually leads to tractable districting problem with good performance. I'd be good to see some comparisons related to that.

- I'm not fully convinced about the generalizability from small instances to larger instances as the size range experimented in this paper is relatively narrow.
questions: questions: - It is unclear to me what the costs (objective) are in the numerical experiments. 

- Related to weakness 1, what is the downside of performing such conversion?
limitations: limitations: Discussed.

Comments: title: Reviewers WW6p and qHFv
Thank you for your updates
comment: Thank you for your response and raising your score!
Thanks for addressing my questions and providing more detail. I will update my score.
The authors have provided extensive replies to the criticisms expressed in your reviews. Have these responses satisfied your concerns? If not, are there any further clarifying questions you would like to ask? The author discussion period ends tomorrow (Aug 13). Please respond.
Thank you for acknowledging our rebuttal and raising your score! We are glad that our rebuttal addressed your concerns.
Dear authors, thank you for your responses. My concerns have been addressed, and the answers clarified my understanding. I'll update my score.
Thank you for your response. All my concerns have been addressed.