DistrictNet: Decision-aware learning for geographical districting
Authors: Cheikh Ahmed
Alexandre Forel
Axel Parmentier
Thibaut Vidal
Venue: NeurIPS 2024 poster (2024)
Keywords: routing
combinatorial optimization
decision-focused learning
Primary area: optimization
TL;DR: We solve real-world districting problems in a few minutes using a structured learning pipeline.

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.

DISTRICTNET: Decision-aware learning for geographical districting
Cheikh Ahmed
Alexandre Forel Polytechnique Montreal alexandre wox.andre.foel@polllpp..o fooel@polyatl.cccmmmmmmmmommm ca
Polytechnique Montreal
bbeikhabballlne ahmed@polymtl.co
Axel Parmentier CERMICS, École des Ponts axel www.eeeeieeereepp........
Thibaut Vidal Polytechnique Montreal thibaut vidal@polymtl..aa
Abstract
Districting is complex combinatorial problem that consists in partitioning ge- ographical area into small districts. logistics, it 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 structured learning approach to find high-quality solutions to real-world districting problems in few minutes. It is based on integrating combinatorial optimization layer, the capaci- tated minimum spanning tree problem, into graph neural network architecture. To train this pipeline in decision-aware fashion, show how to construct target solutions embedded ments show that our approach outperforms existing methods as it can significantly reduce costs on real-world cities.
suitable space and learn from target solutions. Experi-
Introduction
Districting aims partition a geographical area made of several basic units (BUs) into small, balanced, and connected areas known as districts. Districting has wide array of applications in many areas such as electoral politics (Williams, 1995; Webster, 2013; Ricca al., 2013), sales territory design (López-Péree) and Ríos-Mercado, 2013; Zolmers and Sinha, 2005), school zoning (Ferland and Guénette, 1990), and distribution (Zhou al., 2002: Zhong et al., 2007). These problems are challenging because of the combinatorial complexity of assigning BUs to districts.
In this paper, focus districting and routing, 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 vehicle starting from common depot. Since districting is 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 solved 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 al., 2024).
In this study, we present a puuctured-leamingg approach called DISTRICTNET that integrates an optimization layer in deep learning architecture, 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 of the CMST graph using graph neural network (GNN)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

trained in a decision-awer -warr 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 surjection from the space of districting solutions to the space of CMST solutions. other words, there always exists CMST solution that is optimal for the original problem. The main challenge is to train a model that can find it.
i
Solver min o
Decoder
Graph instance
GNN
CMST
Figure DISTRICTNET solves complex districting problem by parameterizing and solving CMST. The GNN e predicts a vector of edge weights 0 based on the covariates of the instance x. These edge weights parameterize CMST, which solved using black-box combinatorial solver. The CMST solution is finally converted into a districting solution Å. Training this pipeline in decision-aware manner requires propagating a loss gradient back to the GNN.
DISTRICTNET is trained to imitate few optimal solutions obtained on small instances. We show that leads to high-quality solutions for large districting problems and great out-o--distribution generalization. Further, our approach is robust changes in the problem parameters such varying number of districts. This is valuable for practitioners, who usually evaluate family of problems before picking 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 surrogate to the original districting problem. We show how to learn from districting solutions by embedding CMST solutions into suitable space and constructing target CMST solutions from districting ones. This allows training DISTRICTNET by imitation, minimizing a Fenchel- loss 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 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.
2 Problem statement
We model geographical area as an undirected graph G = E), where V is a set of vertices representing the BUs and a set of edges representing the connections between them. district d C V is subset of BUs. We say that district d is connected if its graph is connected. Let 1 1(.) be the indicator function that returns one if its argument true and zero otherwise. We denote by D the set of connected districts and N [V] the number of BUs.
Routing costs. Let D be connected district. In districting and routing, the cost of 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 Crsp(d) = Eg (SP(d, E)), where & is the collection of demand requests in district d.
Since the demand is known a priori, it is modeled random variable. We assume that average demand-generating distribution exists for each basic unit over the planning horizon so that
& ~ Dr Ve e V. Let to other nodes. Let also II(E) be the set of all routes that satisfy the demand requests of a district d while starting and finishing the depot, and denote by dist(T) the total travel distance of a route E II. Given 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
additional vertex that represents the depot and connected to all
(d) min dist(mr). *EIT(E)

---

The district cost can be computed through a Monte Carlo evaluation by sampling 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.
The districting and routing problem minimizes the sum of all district costs. Let (ds denote the cost of district d. A districting problem can be formulated in general form as
Districting,
min (0(0)))
(ds:(d)
(Ia)
s.t. E 1(i d)
Vi E V,
(lb)
EMED>==
(1c)
where Xa is binary variable that tracks whether district is selected. Constraint (1b) states that each BU is selected in exactly one district of the solution. Constraint (Ic) specifies that exactly & 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 target size t and include constraints the minimum and maximum size of district. Problem (1) can be formulated over a restricted set of districts D C 'D that satisfy the minimum and maximum size constraints. Formally, it ensures that vd E D" d S |d| I d, where (d. d) are user-specified upper and lower bounds on the district size.
Although seemingly simple, Formulation (1) has exponential number of variables. The number of feasible connected districts of size within geographical area comprising N BUs is on the order of O((e(8 - 1))²=1 A where 8 is the maximum number of neighbors for given BU (Komusiewicz and Sommer, 20. For instance, a city of N = 120 BUs and a target size of t = 20 with d = 13 has on the order of 1 possible connected districts. The been shown to be NP-hard by Ferraz et al. (2024). Hence, solving Problem (I) to optimality is only possible for small problem sizes.
problem has also
Existing approaches. For real-world cities, evaluating district's cost too computationally demanding to be performed at each step of search algorithm. Existing methods replace the cost CTsP(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 Geardwood-HHlton- Hammerrlyy (BHH), which estimates the distance to connect randomly distributed points (Beardwood et al., 1959). This formula has been embedded into 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 (1 (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 surrogate optimization problem trained in a decision-aware fashion. An advantage of this framework is that applies wide range of constrained partitioning problems: it work with any general districting cost function (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 substantial effort needed to train model, our goal 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.
3

---

Instance sizes: the model should be able to handle instances with 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 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 input labeled graph containing all the data of an instance. A graph neural network du 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 districting solution.
The first component of DISTRICTNET is a GNN ow : R + R that assigns weight to an edge depending on its feature vector. Applying this model all edges of an instance returns vector of edge weights 0 E R |i 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 al. (2019), the update rule at the I-th layer is given by
((+1) = a (w/ ( + (W(e)l EjENio) w("ng)) e
(2)
where h is the feature vector of edge e at the 1-th layer, a is a non-linear activation function, Wo and W are learnable weight matrices, and N(e)) is the set of neighboring edges of an edge 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.
3.1
Combinatorial Optimization Layer
The second component of DISTRICTNET is the CMST layer parameterized by the vector of edge weights 0. This layer studied graph optimization problem based on the minimum spanning tree problem. minimum spanning tree is the subset of edges of 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 predetermined capacity.
surrogate for the original districting problem. The CMST is well-
Let T be the set of connected subtrees with minimum and maximum size (d. d). We consider that an edge is in subtree if both its extreme points are inside the subtree. The CMST problem with target number of subtrees is then given by
min Dc (0.1))
ΣNET V Σ -ee
--ee
(3a)
s.t. Σ 1(1 E 8)V, = 1,
Vi WEV. V,
(3b)
Us V, =k k.
(3c)
Formulation (3) highlights the strong link between the CMST and the districting problem in (I). Both problems partition 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 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 single-stage optimization problem with linear objective. However, it remains

---

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) solve small instances to optimality, and we apply 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) 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 very poor solutions. Here, we use a modified Kruskal algorithm to exploit the structure of the CMST and quickly find good initial solution. The details of our implementation of the ILS are given in Appendix A.
4 Training DISTRICTNET by imitation
DISTRICTNET is trained to imitate the solutions of a training set { A }= Each instance xi (Gs, fi) is a labeled graph with G; = (Vi, E,) the instance graph and fi = { E Rd,, Ve E E.} the set of edge feature vectors. A target districting solution X; is associated with each instance T., Since producing optimal near-optimal districting problems is hard, building this training 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 solving
min
where L: (0. + L( is a loss function that quantifies the distance between CMST solution corresponding to the edge weights with a target CMST solution y. 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 new embedding of CMST solutions, (ii) converting districting targets X; into CMST targets yi, and (iii) defining suitable loss function with desirable properties and deriving its gradient.
4.1 Embedding and target solutions
A CMST solution is entirely characterized by its edges. We can therefore build an embedding ) of the set V of solutions & of the CMST problem given in (3) in R E as y = {ы(v)) E V} where u(v) (ue(v))eBB and (e) = E.ET [ee E s). We can then reformulate Problem (3) as
max 0 y. yEY
(4)
where, 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 polytope. Therefore, the linear program given by max 0 μ is equivalent to Problem (4). The change of notation from a vertex to moment μ emphasizes that takes values inside the convex hull C. We now use the shorthand notation μ² (0) to denote an optimal solution to argmax,ee' 01 μ..
From Districting to CMST. As discussed previously, there is surjection from the space of CMST solutions to the space of districting solutions. Given a target districting solution A, we denote by (A) the set of feasible CMST solutions that lead to X.
To recover a target CMST solution, we introduce the constructor algorithm A À r> y that maps a districting solution X to CMST solution y E (A)). 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 E X. This can be efficiently done by applying Kruskal's algorithm in parallel for all the selected districts.
Finally, we define our target CMST solution f E C as
(5) which is taken as an expectation over the realizations of the randomized algorithm A. This allows us to convert our training set {s,, Ae) into (x,, W.) and enables training DISTRICTNET by imitation.
á = (x
5

---

4.2 Fenchel- Fenchel-Young loss and stochastic gradient
Let j be a target CMST solution. We want DISTRICTNET to minimize the non contoiiiaaltty of μ²' (0) compared the target p. that is, minimizing the loss maX 0 μ - p. Minimizing this loss directly does not work because 0 = 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)
max o- (
(6)
MEC
and the smoothed version of the non-optimality loss as:
LrY (0, ())
max 0 p- p (0 (2()) MEC
Denote by (f) the Fenchel conjugate of 52, the regularized loss in Equation (7) is equal to LFv(O, (i) 22 + (2(z) -0 0 j (Dalle et al., 2022), which we recognize as the Senchel-Young inequality (Blondel et al., 2020). Fenchel's duality theory then ensures that this loss has desirable properties. Notably, it is convex in 0, non-negative, equal to 0 only if ú is the optimal solution of (6), and its gradient can be expressed as VeL(0, ()) argmaxpec (0 μ (2(4)) -p.
Practically, it remains to choose a suitable regularization function Ω. When using 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 objective F(0) = max (0 + 2)TTi ul. where Z a random variable with positive and differentiable density on E In that case, the gradient of the Fenchel Young loss with respect to 0 can be computed as (Berthet et al., 2020)
VoLFr(O, Ezlu"(0 + 2)]
(8)
stochastic gradient can therefore be conveniently computed using the Monte Carlo approximation M Em= argmax,eed (0 + 7 T μu for the expectation, where { are sampled perturbations. If A is randomized, we also use a Monte Carlo approximation to estimate jr.
Summary. The novelty of our approach lies in our reconstruction of CMST moment jú from districting solution Å, which can be seen as partially specified target g. 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.
5 Numerical Study
We now evaluate the performance of DISTRICTNET on real-world districting and routing problems. We run repeated experiments and compare our approach other learning- based benchmarks. We investigate the following aspects of DISTRICTNET: (i) its ability to generalize to large out-of- distribution instances from training on 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 al. (2024) and implemented in C++. All experiments on a computing grid. Each experiment is run on two cores of an AMD Rome 7532 with 2.4 GHz and allocated 16 GB RAM. The code to reproduce all experiments presented in this paper is publicly under an MIT license.
run
available at https: //////g //ggttttttuh//g////////ge com/ hheikhh25/Distriiee
5.1 Experimental Setting
Our instances include all the real-world cities 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, I 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 ks [N/t].
Features. Rach BU is summarized by a set of characteristics including its population, density, area, perimeter, compactness, and distance the depot. For test instances, these summarizing statistics 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 normal distribution (8 000, 2 000) truncated between 000 and 20 000. For each instance 2i; we compute its optimal solution for the target size 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 Crsp(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 Figliozii (2007) (FIG), (iii) the method of Ferraz et al. (2024) (PREDGNN), and (iv) deterministic approximation of the stochastic districting problem called AVGTSP. The first two approaches are extensions of BHH's formula and therefore are simple linear regression models. The third benchmark is based on training graph neural networks to estimate the district costs. Ferraz et al. (2024) train a GNN model to predict district costs for fixed city and set of problem parameters and show that this approach outperforms BD and FIG. Since our focus on generalization to multiple cities and problem parameters, our implementation extends the one of Ferraz et al. (2024): train single GNN using data from multiple small cities and evaluate its ability to generalize auttof-distribution. In contrast, AvGTSP estimates district costs by solving TSP over the barycentres of all BUs within 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 surrogate optimization model. Instead, they are trained in a traditional supervised learning fashion: to minimize the cost-estimation error on 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.
5.2 Main results
We evaluate the ability of the different methods to generate good solutions a diverse set of out- of-distribution instances. All methods are evaluated using the same performance metric: the total districting cost Crsp(d) of districting solution 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 1 E (3,6 6, 12, 20, 303 for each of our seven test cities. This provides 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 I 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 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.
7

---

(c) PREDGNN, (d) DISTRICINET, Figure 2: Districting solutions given by BD, FIG, PredicIGNN, and DistrictNet for the city of Manchester with district target sizes 20 BUs. The depot is shown as a white star.
(a) BD. (b) FIG,
Table 1: Ablation study showing the value of combining GNN and structured learning.
Average relative cost
p-value
Benchmark I: BD, linear regression
9.92 %
4.9e-09
Benchmark 2: FIG, linear regression
10,01 %
8.9c-09
Benchmark 3: PREDGNN, unstructured learning with GNN
11,91 %
1.5e-10
Benchmark 4: AvGTSP, learning.
4.44 %
2.7e-04
DISTRICTNET: structured learning with CMST and GNN
0.0 %
Large cities. We perform an additional experiment to investigate the generalization to cities of large sizes. In Figure 3, we show the of the districting solution obtained with the benchmark methods relative to DISTRICTNET for varying city sizes. 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 ILS is kept to 20 min for all methods when N < 400 and increased 60 min when N > 400.
(a) Bristol
(b) Leeds
(c) London
Rel. cost [io S6
120
120
110
115
110
110
105
105
105
100
100
150
190
240
150
240
290
200
300
700
900
City size
City size N
City size
BD
FIG PREDGNN
Figure 3: Cost relative to DISTRICTNET for target district size f 20 and varying city size.
The results show that DISTRICTNET provides very good solutions up to the largest city sizes. consistently outperforms the benchmarks even for large cities. These results are achieved despite DISTRICTNET being trained 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 generalizes even to instances that 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 district costs varies greatly with the city and parameters. Since there is shift in the lata-generating distribution, the benchmarks, which ignore the structure the districting problems, are able to accurately predict the district costs resulting in poor overall performance.

---

Table Comparison of districting costs for the Ile-de-France France region with 2,000 BUs.
Method
BD
FIG
PREDGNN
AvGTSP
DISTRICTNET
Absolute cost
2379.0
2388.8
2295.2
2262.7
2205.7
Cost relative to DISTRICTNET
+7.8%
+8.3%
+4.0%
+2.6%
0.0%
Result 3. Thanks to its surrogate optimization layer, DISTRICTNET captures the general structure of the districting problem. Thus, it is less sensitive to shifts in the dala-generating distribution.
(a) Bristol
(b) Leeds
(c) London
Relative [in S6
100
200
201-
150
00
99
Cost
150
98
60
50
50
20
96
20
50
100
150
200
Target size
Target size
Target size
Training size n
Figure Distribution of district cost for varying target size.
Relative cost of DISTRICTNET with increasing data.
Figure
The value of data for decision-aware learning, Finally, we investigate the value of training data for DISTRICTNET. In Figure 5, we study the -ut-o--distribution performance 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 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 diminishing return.
and add 95% confidence interval shaded area. A value smaller
Result 4. DISTRICTNET can be trained with small computational budget and benefits from increasing the number of training examples.
6 Related literature
In this work, we find near-optimal solutions to complex combinatorial problems by introducing a combinatorial layer in deep neural network trained in decision-aware fashion. Our work lies the intersection of the learning-to-optimize literature and decision-awar learning.
Learning to optimize. Recent years have seen 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 al., 2023). Deep reinforcement learning has been applied to solve typical combinatorial problems such as the traveling salesman and knapsack problems (Bello al., 2016) and the minimum vertex cover and maximum problems (Dai et al., 2017). Gasse et al. (2019) presented technique to improve the branch-and- process in mixed-integer linear programming by using graph convolutional neural networks.
The main advantage of learning-basee methods that, after potentially expensive training procedure, they can generate good solutions 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 beam search to solve the Euclidean TSP using GNNs and show notable improvements in solution quality, speed, and efficiency. Kool 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-awand learning, on the other hand, looks into including an optimization layer in deep learning architectures. key challenge this area is to propagate meaningful gradient through this non-smooth layer. Amos and Kolter (2017) developed a method to compute the gradients of quadratic programs by differentiating the Barus--Kun--Tuckee conditions. In the case of (integer) linear programs, propagating this gradient can be performed for
optimality

---

instance by introducing log-barrier term to the LP relaxation (Mandi and Guns, 2020), using piecewise-linear interpolation technique (Vlastelica al., 2019), 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-aweed 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 al. (2019) learn solve hard combinatorial problems by learning from incomplete graphs using differentiable k-means clustering algorithm. Stewart et al. (2023) present a differentiable clustering approach with a partial conseer-onncttiiity matrix. Our paper differs in two significant ways. First, we use a surrogate model with substantially more structure than clustering since 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 given training example, we have information on the corresponding CMST solution. This leads us to introduce a randomized target construction algorithm, which leads to 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 shifted offline, and great performance on test instances 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 the solution. Second, learning may intensive computationally, both when generating the training instances and in the training algorithm. We refer the reader Aubin-Frankowski et al. (2024) for a general discussion of these aspects and an analytical characterization of generalization bounds.
7 Conclusion
This paper presented general pipeline to learn to solve graph-partitioning problems. It integrates CMST as a surrogate optimization layer, which allows it to capture efficiently the structure of graph partitioning while providing solutions in 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 generalize to out-of-distribution instances. Thus, it can be trained 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.
Acknowledgements
This research was enabled by support provided by Calcul Québec and the Digital Research Alliance of Canada, as well as funding from the SCALE AI Chair in Data-Driven Supply Chains. The authors also acknowledge the support of IVADO and the Canada First Research Excellence Fund (AFogé</CFREF).
References
B. Amos and J. Z. Kolter. OptNet: Differentiable optimization as layer in neural networks. In International Conference on Machine Learning, volume 70, pages 136-145. PMLR, 2017.
P.-. Aubin-Frankowski, Y. De Castro, A. Parmentier, and A. Rudi. Generalization bounds of surrogate policies for combinatorial optimization problems. arXiv preprint arXiv:2407.17200, 2024.
10

---

J. Beardwood, J. H. Halton, and J. M. Hammersley. The shortest path through many points. Mathe- matical Proceedings of the Cambridge Philosophical Sociery, 55(4):299-321) 1959.
I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.0980 0.0940, 11 2016.
Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J.-P. Vert, and F. Bach. Learning with differentiable perturbed optimizers. Advances in Neural Information Processing Systems, 13:9508-9515 2020.
Bezanson, A. Edelman, S. Karpinski, and V. B. Shah. Julia: fresh approach to numerical computing. SIAM Review, 59(1):65-98, 2017.
R. Birge and Louveaux. Introduction to stochastic programming. Springer Science & Business Media, 2011.
M. Blondel, A. Martins, and Niculae, Learning with Fenchel- Young losses. Journal of Machine Learning Research, 21(1):1314-182) 2020.
V. Cabannnes, A. Rudi, and Bach. Structured prediction with partial labelling through the infimum loss. In International Conference on Machine Learning, pages 1230-1233 PMLR, 2020.
Q. Cappart, D. Chételat, B. Khalil, Lodi, C. Morris, and Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1 61, 2023.
C. F. Daganzo. The distance traveled to visit points with a maximum of с stops per vehicle: An analytic model and application. Transportation Science, 18(4):331-350, 1984.
H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L.. Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, 30, 2017.
G. Dalle, L.. Baty, L. Bouvier, and A. Parmentier, Learning with combinatorial optimization layers: a probabilistic approach. arXiv preprint 22X.::2207..35133 2022.
M. Dyer and A. Frieze. On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics,
1985.
A. M. Ferber, T. Huang, Zha, M. Schubert, B. Steiner, Dilkina, and Tian. SurCo: Learning lin- ear SURrogates for COmbinatorial nonlinear optimization problems. In International Conference on Machine Learning, pages 10034-10052. PMLR, 2023.
J. A. Ferland and G. Guénette. Decision support system for the school districting problem. Operations Research, 38(1):15 1990.
A. Ferraz, Q Cappart, and T. Vidal. Deep learning for data-driven ceneeiiing-ad-rruttti arXiv preprint, 2024.
M. A. Figliozzi. Analysis of the efficiency of urban commercial vehicle tours: Data collection, methodology, and policy implications. Transportation Research Part B: Methodological, 41(9): 1014-1032, 2007.
M. Gasse, D. Chételat, N. Ferroni, I.. Charlin, and A. Lodi. Fxact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.
K. Helsgaun. An extension of the Lin-Kernighan-Helggani TSP solver for constrained traveling salesman and vehicle routing problems, 2017. Technical Report, Roskilde University.
C. K. Joshi, Laurent, and X. Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.
C. Komusiewicz and Sommer. Enumerating connected induced subgraphs: Improved delay and experimental comparison. Discrete Applied Mathematics, 303:262-282, 1.2

---

W. Kool, H. van Hoof, and M. Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Kou, B. Golden, and S. Poikonen. Optimal tsp tour length estimation using standard deviation as a predictor. Computers & Operations Research, 148: 105993, 2022.
H. Lei, G. Laporte, Y. Liu, and T. Zhang. Dynamic design of sales territories. Computers and Operations Research, 56:84 2015.
S. Lin and B. W. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21:498-516, 1973.
F. López-Pérez and R. Z. Ríos-Mercado. Embotelladoras area uses operations research to improve territory design plans. Interfaces, 43(3):209- 2013.
J. Mandi and T. Guns. Interior point solving for LP-based prediction-oppimiisatio. In Advances in Neural Information Processing Systems, volume 33, pages 7272-7282, 2020.
Mandi, J. Kotary, S. Berden, M. Mulamba, V. Bucarey, Guns, and F. Fioretto. Decision- focused learning: Foundations, state of the art, benchmark and future opportunities. arXiv preprint arXiv:2307.13500 2023.
C. Morris, M. Ritzert, M. Fey. W. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe, Weisfeiler and leman go neural: Higher-order graph neural networks, Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2019.
A. G. Novaes, J. F. S. de Cursi, and O. D. Graciolli. A continuous approach to the design of physical distribution systems. Computers Operations Research, 27(9):877-893, 2000.
E. C. Reock, note: Measuring compactness as a requirement of legislative apportionment. Midwest Journal of Political Science, 5(1):70-74, 1961. ISSN 00263397. URL http: http://uow.jstoor org/ stable/ Stable/21088 2109043.
F. Ricca, A. Scozzari, and B. Simeone. Political districting: from classical models to recent ap- proaches. Annaly of Operations Research, 204:271-299, 2013.
U. Sadana, A. Chenreddy, E. Delage, A. Forel, E. Frejinger, and T. Vidal. survey of contextual optimization methods for decision making under uncertainty. arXiv preprint arXiv:2306. 10374, 2023.
Stewart, F. S. Bach, L. López, and Q. Berthet. Differentiable clustering with perturbed spanning forests. In Advances in Neural Information Processing Systems, 2023.
M. Vlastelica, A. Paulus, V. Musil, G. Martius, and M. Rolinck. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.
G. R. Webster. Reflections on current criteria to evaluate redistricting plans. Political Geogruphy, 32: 3-14, 2013.
B. Wilder, E. Ewing, B. Dilkina, and M. Tambe. End to end learning and optimization on graphs. Advances in Neural Information Processing Systems, 32, 2019.
J. Williams. Political redistricting: review. Papers in Regional Science, 74(1):13 40, 1995.
H. Zhong, R. W. Hall, and M. Dessouky. Territory planning and vehicle dispatching with driver learning. Transportation Science, 41(1):74-89, 2007.
G. Zhou, H. Min, and M. Gen. The balanced allocation of customers to multiple distribution centers in the supply chain network: genetic algorithm approach. Computers & Industrial Engineering, 43(1-22 43(1-2):251-2611 2002.
A. A. Zoltnrr and P. Sinha. Sales territory design: Thirty years of modeling and implementation. Marketing Science, 24(3):313 3311, 2005.
12

---

A Supplementary Material: Methods and Implementation
In this part, we provide details on the four methods considered this paper and their implementations.
We include:
in Appendix A.1 illustration of how DISTRICTNET converts districting problem into
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.
A.1 Additional Details on DISTRICTNET and Implementation
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.
A.1.1 Illustrative Example
We illustrate the link between districting problems and CMST problems in Figure 6. First, show a simple districting instance with = 7 BUs with the source node shown as a yellow star. In Figure 6 (b), 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 (c) show the solution of this CMST instance. The solution has subtrees stemming from the source node. Each subtree corresponds to a district.
(a) Districting instance with N = 7 (b) CMST instance with edge width (c) Optimal CMST solution for BUs
shown proportional to their weights 3
Figure 6: Small (a) districting problem converted into (b) CMST problem with edge weights and (c) its corresponding solution: d1 (1, 4] and d2 (5, 6, 7}.
A.1.2 Training Algorithm
DIstRIcTNET is trained following Algorithm 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 samples and temperature e). We note again that, in our implementation, DISTRICTNET uses the exact approach to solve each perturbed CMST, which based on enumerating all the possible districting solutions and solving the exact formulation given in (3).
13

---

Algorithm Training DISTRICTNET
Require: Dataset D {zz, 3e] 1: Initialize GNN model &
2: for to _aw__pocha_aaaaaaap do
3: for all b to nb_ bb_baacheessssee do
4: Get batch B of training examples from D
5: for all (z, y) in B do
6:
Predict edge costs Sample perturbations Z(1)
((x)
7:
2(d)) (001
8:
for m = 1 to A do
9:
Perturb edge costs ((m) 0 + =Z(m)
10:
Solve perturbed CMST to obtain ymm) end for
11:
Average perturbed solutions E Mi Em= y(m)
13:
Evaluate gradient of FY loss V VoLry 2(x))
14:
Make gradient step parameters of
15:
end for
end for
17:
end for
Return Trained model Φ
A.2 Additional Details on Iterated Local Search (ILS)
All districting and CMST problems on large instances are solved using ILS. The detailed algorithm is given Algorithm ILS iteratively applies two methods: a local search that guides a solution to a local optimum, and perturbation that explores the solution space. The local search algorithm is given pseudocode in Algorithm 3. The perturbation algorithm the same as the local search one except that each possible move is implemented with given probability even if it does not improve the solution. This probability is typically very low. our experiments, after hyperparameter tuning, we find that probability of 1.5% works well in most instances, which is consistent with the results of Ferraz et (2024).
Algorithm 2 Iterated local search
Algorithm 3 Local search: LS
Input:
Initial districting solution So Initialize: Best solution Stest <- So while stopping criterion not met do Apply local search S: S" LSS if' cost(S") < cost(Stest) then
Input: Current districting solution S while improvement is found do
Initialize: Best move Mbeat = Ø for each pair of districts (Da, Db) order do
random
Store best solution: Sheat + S end if
Identify border nodes between D, and Ds for each border node i in D do
Apply perturbation S:: P(S') end while
Evaluate all possible moves: move to Db or swap with node j in D,
Return: Shest
Compare moves to mhest and keep best end for
if Misst improves the solution then Apply best move 5 <- -&best (S) end end for end while Return: S
A.2.1 Initial Solution
A feasible districting or CMST solution is set of connected BUs of size k, where each subset has number of BUs within the minimum and maximum acceptable size. Obtaining feasible solution that satisfies these constraints is already NP-hard (Dyer and Frieze. 1985) 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 4. This algorithm starts with all nodes in their
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 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.
Algorithm 4 Modified Kruskal
Algorithm 5 Greedy merging
Initialize cluster for each vertex G Sort edges of G by increasing weight as Esorted
while number districts larger than target k do
Find neighboring districts Da and D, with the smallest combined size
for each edge (u, v) in Esorted do if vertices u and v are different clusters and |M| + |u| < t then
Merge Da and D₁ end while
Merge clusters of and
end if end for
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 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 main experiments. However, they are not sufficient for the largest instances (when N 2 600 in our experiments). Thus, we introduce 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 removing nodes from neighboring districts while maintaining overall connectivity.
Algorithm Repair
Require: Current districting solution S Sort districts in S by size in increasing order for each district d do if [d] < d then
Add nodes from neighboring districts to D
end if
end for
Sort districts in S by size in decreasing order for each district d do if [d] d then
Remove nodes from d and add them to neighboring districts end if end for
A.3 Benchmark Methods
BD. Following Daganzo (1984), BD estimates the cost of district as
(dstæp(d) = AyR + 2Ad.
where A. Eied (i represents the total area of the district with a; being the area of the i-th BU, and R. denotes the expected number of demand requests within the district. The term A₂ is the average distance between the depot and demand point. Because we not make assumptions on the shape of the BUs, we compute this term using Monte Carlo approximation. The parameter 3 is
15

---

parameter that adjusts the influence of area and demand on the cost. Hence, BD is a linear regression and training amounts finding the right value for
FIG. Following Figliozzi (2007), the cost of a district is given by
Ad
distrIg (d) 31 AaRa + 32 B3y
31.
(10)
R
where 3 = (B1,, 82, $3, 34) now represents vector of parameters that modulates the cost estimation. Clearly, FIG is extension of BD and we train in the same way.
PREDGNN. Following Ferraz et al. (2024), PREDGNN uses a GNN to estimate the cost of a district, ie., distPanDNNN(d) (Ga), where @ is the trained GNN and Ga is district graph. The district graph is a labeled graph where each node i is described by the features
f (pis VPi, ai va,, qis Pt, Sg. Cs,d)
(11)
where p. is the population of the BU i, q, its perimeter, a, its area, P: its density, 8; its distance to the depot, and eid is an inclusion variable that takes the value 1 if BU belongs to the district d and O otherwise. The GNN processes Ga learn latent representation that captures the structure of the district. This is done in two phases. First, a message- peaasagg-pssiingggg algorithm is applied at the node level, then aggregation layer summarizes the whole graph into 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?
Cost estimate
b(a,)
Example district
Learning model: GNN and feedforward NN
Figure 7: PREDGNN estimates the cost of a district using a GNN and feedforward NN. First, the GNN applies message- message-passing passing algorithm to capture the structure of the graph. Then, aggregation layer provides the graph embedding. This is post-put 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 labeled graphs. PREDGNN uses node-basee based features available the BU level. In contrast, DISTRICTNET uses edge-based features, averaging the attributes of the two BUs connected each edge. Hence, while PREDGNN focuses on properties of individual BUs, NISTRICTNET also captures the spatial relationships hetween connected BUs. Further, DISTRICTNET does not use the final aggregation layer for global graph embedding of PREDGNN since is applied independently to each edge. This allows finer-grained representation of the graph.
AVGTSP. This benchmark replaces the districting-and-routiee problem in Equation (1) by the surrogate optimization problem given by
min (
(12)
dED
that is, it exchanges the min and expectation operations in the objective function of the original problem. This yiclds 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 g.
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 Eg(E] is single request that appears at the barycentre of the area. Evaluating a district cost thus reduces to solving TSP over the barycentres of all its BUs. As for all other methods, we integrate this approximation in iterated local search.
16

---

A.4 Architectures and Hyperparameters
Several hyperparameters control the different methods used in this paper. We give here the ar- chitectures 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 uses large number of district costs examples. On the other hand, DISTRICT 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 100 instances. Notably, the district cost evaluation can all be performed in parallel.
Table 3: Summary of parameters and computational effort for training the different methods.
Nb. training examples n
Nb. district cost evaluation
Training Time
BD FIG PREDGNN DISTRICTNET
10
104
8 seconds
10a
10a
3 seconds
104
10a
16 hours
10
62 10
38 minutes
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 imputs 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 -ie-dimensional output.
For PREDGNN, we maintain the structure proposed by Ferraz et al. (2024), with the exception that replace the Structure2vec layers with GraphConv layers. The update rule for the GraphCony layers is 2 ReLU(W1a + (j) Warf), where W1 and W2 are the weight matrices and (i) is the set of neighbors for node In contrast, the Structure2vec update rule applied in the original model is xf+ ReLU(W,xx + W2 EjEN(H) x.)). This is minor modification and should not alter its performance. as also stated by Ferraz al. (2024).
The architecture of PREDGNN thus consists of four GraphConv layers. Each layer has hidden size of 64 units and uses ReLU activation functions. The final layer produces output of size 1028. We then aggregate these node embeddings to form global graph embedding. This global embedding is initially processed by 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 all our experiments.
PREDGNN uses a batch size of [ 64, learning rate of 14-4, and train the model for 1 epochs. We further set time limit of 24 hours for training and stop the process early if no significant change of the loss (i.e., greater than 1e 4e is observed in the last 1 000 epochs.
DISTRICTNET uses a batch size of [B] = 1 and a learning rate with initial value of 13 with a decay rate of 0.9 applied every 10 epochs and 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 random constructor (Kruskal with random weights). The perturbation Z is set multivariate standard Gaussian and we M = 20 samples to approximate the expected gradient in Equation (8). The randomized target constructor uses 000 samples.
17

---

B Supplementary Material: Data Collection and Generation
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 use real-world data generate set of training instances that can be arbitrarily large. also discuss the distributional assumptions used to simulate random demand over a city.
B.1 Test Instances: Real-World Cities and Population
We use the four cities of Bristol, Leeds, London, and Manchester for our test instances. summary of these instances is given in Table 4. The table shows the statistics the population, area, and density of the BUs composing the four test cities. shows that, while the area and density may vary relatively constant. This is not surprising since BUs tend
across cities, the population statistics to be designed to have similar populations. The geographical data including the boundaries of each city and BUs be accessed Uber Movement: https: //movement... uber com/ Additionally, census data 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.
Table 4: Statistics on the BUs of the seven test cities, adapted from Ferraz al. (2024)
Bristol
Leeds
Manchester London
Paris
Lyon
Marseilles
Average
8.28
7.76
9.01
8.21
2.49
2.71
2.29
Std.
2.13
1.80
1.90
2.12
0.74
1.37
0.77
Population (thousands)
Minimum
5.23
5.20
5.43
4.96
0.36
0.28
0.58
Median
7.85
7.40
8.69
7.76
2.33
2.46
2.27
Maximum
18.16
16.17
24.97
15.87
4.83
6.47
4.88
Average
16.39
6.80
1.62
3.05
0.093
6.77
0.52
Std.
30.16
10.40
1.88
3.60
0.07
7.62
0.94
Area
Minimum
0.63
0.35
0.30
0.59
0.018
0.11
0.07
(km?)
Median
2.80
3.05
1.16
2.13
0.07
4.21
0.29
Maximum
171.21
94.13
22.30
35.69
0.45
38.96
6.81
Average
3.12
2.99
8.92
4.01
34.3
1.94
9.59
Std.
2.62
2.80
5.25
2.32
16.5
2.649
6.98
Density
Minimum
0.05
0,10
0.36
0.14
2.6
0.0039
85.18
Median
2.89
2,41
7.77
3.79
34.73
0.71
7.5
Maximum
12.72
25.20
28.27
16.36
129.09
11.45
32.6
B.2
Training Instances
For our experiments, we utilize real-world data from 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 citics, generate their population randomly. We use normal distribution. (8 000, 2 200) truncated within the range [5 000, 20 000] to be close to the true population distribution of BUs.
To generate the city graphs used 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 Algorithm Finally, an artificial
central depot is placed at the centroid of the resultant polygon. This procedure allows us to create 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 generate training instances and corresponding number of BUs
City
N
City
N
City
N
City
N
Barnet
41
Coventry
42
Leicester
37
Sefton
38
Birmingham
132
Derby
31
Liverpool
61
Sheffield
70
Bolton
35
Doncaster
39
Newham
37
Southwark
33
Bradford
61
Ealing
39
Nottingham
38
Stoke
34
Brent
34
Greenwich
33
Oldham
33
West Midlands
684
Brighton
33
Kirklees
59
Plymouth
32
Wigan
40
Cardiff
48
Lambeth
35
Rotherham
33
Algorithm 7 Training instance generation
Input: Number of instances n,, real-world training cities
for i = 1 to do
Sample a city from the train cities with probability proportional its size
Sample a connected subgraph of this city of size N = 30 BUs
Sample the population of each BU from truncated normal distribution
Place central depot
end for
Return: Set of n training instances
B.3 District Demand and District Cost
We suppose that the demand within each BU follows fixed distribution. In each period (e.g.. day), number of demand requests in each BU. The number of demand requests follows a Poisson distribution with the being proportional the population density of the BU, expressed Here, n represents the population count of the BU, and is set to 96/ 000 x t). This value of is selected to realistically approximate scenario where district typically handles around 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 Crsr = Eg [TSP(d, E)] This is done through Monte Carlo estimation. To accurately estimate the operational costs of 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-HHllsgaaa (LKH) algorithm (Lin and Kernighan, 1973; Helsgaun, 2017). We use the publically available implementation from: /ttp://akaraaa/ ruc. dk/ wwwpseearrc/aaaee
3/. This heuristic is widely accepted state-of-the-an art heuristic for TSPs. is based on a local search strategy that consistently returns near-optimal solutions.
Algorithm 8 Sampling a connected subgraph of size N
Input: Graph G. maximum size N Select a random starting node from G and set {u}
while [s] < N do
Build (s)., the of all BUs that neighbors of
Randomly select a node E (s(s) and add it to end while
Return: Connected subgraph of G
19

---

C Supplementary Material:
Additional Results
In this part, we provide additional experimental results. We give:
overview of results on small training and validation instances in Appendix C.I, a detailed table presenting the individual results of experiments in Appendix C.2, table presenting the compactness of the districts obtained in Appendix C.3, and examples districting solutions for all methods on various instances in Appendix C.4.
C.1 Out-of-Sample but In-Distribution
We perform a small experiment to investigate the in-distribution generalization ability of the different methods. That is, we study the setting where the training and test instances are sampled from the same distribution. We generate 200 instances following the procedure described Appendix B.2 and split this into two sets of 100 instances. The first set is used to train all the methods and the second is used to evaluate them out-of-sample.
All instances are of size N = 30 and with a target district size t 3. Hence. we can solve them to optimality reasonable time using a full enumeration of the possible districts and the exact formulation given in Problem (1). We solve to optimality all the districting problems of BD, FIG and PREDGNN and all the CMST problems of DISTRICTNET during both training and testing. Further, since we consider only small instances here, we can measure the optimality gap of all methods: the relative difference between the cost of the true optimal solution and the one of the methods.
The optimality gap of the four methods is shown in Table for both the training and testing instances. The results show that DISTRICTNET achieves the smallest average test gap from the optimal solutions compared to other benchmarks. BD and FIG have similar performance, which can be expected since they estimate the district costs similarly. PREDGNN has the worst average performance, although less variations since it has a smaller maximum gap than BD and FIG.
Table 6: Gap optimal districting solutions train and test instances.
Train
Test
Avg.
Max.
Min.
Avg.
Max.
Min.
BD
4.0 %
11.25 %
0.27 %
4.09 %
11.06 %
0.42 %
FIG
4.24 %
15.98 %
0.27 %
4.09 %
12.16 %
0.42 %
PREDGNN
3.37 %
10.05 %
0.05 %
4.64 %
11.89 %
0.22 %
DISTRICTNET
1.86 %
7.48 %
0.0 %
2.34 %
5.52 %
0.17 %
C.2 Detailed results for each city
In Table 7, we present the individual experiment results that have been summarized in the ablation study presented in Section 5. 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. highlights that DISTRICTNET provides the lowest count on 27 out of 35 test instances. Further, it shows that DISTRICTNET lead to significant savings, as it can reduce costs by up to 13% in the best case. Overall, the cost savings are higher for large target district sizes, and for cities in the United Kingdom that are closer to the training instances.
C.3 District compactness
Compactness is an important criterion in districting problems as often leads efficient and fair divisions. Compactness here does not refer to the topological property. In the districting terminology, it refers to shape property. We measure compactness using Reock's 's score, commonly used metric measure defined as the ratio of the area of the district to the area of the minimum enclosing circle that contains the district (Reock, 1961). higher score indicates greater compactness, with compactness equal to I when the district is circular. As shown in Table Table 8, DISTRICTNET consistently provides more compact districts compared other methods, suggesting that can design geographically tighter districts.
20

---

Table 7: Districting costs across different cities and target district sizes for our method and benchmarks.
The best result is shown in blue and the second best in orange. The last column shows the relative difference between DISTRICTNET and the best or second best method.
City
BD
FIG
PREDGNN
AvGTSP
DISTRICTNET
(Rel.)
1944.28
1915.43
1967.8
2015.68
1873.07
(-2.2%)
1274.12
1308.06
1269.82
1325.37
1192.9
-6.1%)
Bristol
12
896.3
912.61
861.38
859.18
819.54
-4.6%)
20
696.9
713.24
681.35
667.11
633.15
5.1%)
30
564.12
564.12
600.48
558.41
539.02
3.5%)
1438.21
1433.44
1498.61
1416.05
1400.64
(1.1%)
933.17
953.35
957.82
920.49
901.2
(-2.1%
Leeds
12
677.64
670.99
653.65
682.18
586.7
(-10.2%)
20
531.27
540.59
483.95
461.18
442.97
(-3.9%)
30
463.06
497.07
413.63
416.14
389.66
(-5.8%
745.08
745.78
748.21
773.0
737.51
(-10%)
6
494.7
486.35
502.83
495.72
465.67
(-4.3%)
London
12
346.06
331.42
350.25
329.04
300.48
(-87%)
20
271.57
265.67
282.67
249.75
227.66
(- -.8%)
30
207.12
219.87
228.5
211.41
182.55
11.9%)
1466.5
1466.41
1539.63
1570.19
1446.49
1.4%)
6
918.66
912.29
953.14 14
938.32
884.61
3.0%)
Lyon
626.17
627.82
649.68
614.44
585.75
4.7%)
20
554.02
549.88
595.85
500.44
471.62
5.8%)
30
549.62
517.66
495.97
494.76
432.99
12.5%)
1173.48
1162.94
1240.42
1158.66
1163.72
(0.6%)
6
781.3
770.16
824.39
739.87
733.74
(-08%)
Manch.
12
565.1
564.8
558.79
546.07
474.76
-1.11%
20
428.34
440.67
469.02
360.78
355.15
(-16%)
401.95
376.98
390.43
299.69
316.55
(5.6%)
466.65
469.52
487.0
498.72
476.58
(2.1%)
6
285.44
288.36
290.66
297.65
289.02
(1.3%)
Marseille
12
206.47
205.69
207.47
204.04
195.09
(-4.4%)
20
176.95
177.17
185.02
172.65
159.62
(-7.5%
30
164.84
164.84
168.23
156.09
148.71
(-4.7%)
185.43
187.54
189.15
176.03
192.38
(9.3%)
118.78
115.04
124.22
106.27
116.63
(9.7%)
Paris
12
82.37
85.32
87.67
74.57
81.64
(9.5%)
20
82.51
79.17
82.08
64.06
67.09
(4.7%)
30
76.55
81.18
76.12
61.8
61.8
(0.0%)
C.4 Example Districting Solutions
We illustrate the districting strategies of the four methods considered in this paper by showing examples of districting solutions the test instances. Figure 8 shows the districting solutions of the four methods for the city of London with t = and = 20 BUs. Figure shows the same results for the city of Manchester with = 6. These solutions correspond to the costs shown in Table 7. These figures show that DISTRICTNET tends to return compact, homogeneous districts. On the contrary, the three benchmarks tend to find districts in a "U" shape. This is especially visible for large district sizes such as = 20. Interestingly, BD and FIG provide visually similar results, especially for the city of I London.
21

---

Table 8: Compactness of districts found by the different methods. A higher value indicates better compactness.
City
BD
FIG
PREDGNN
AvGTSP
DISTRICTNET
Bristol
0.263
0.260
0.307
0.293
0.375
Leeds
0.266
0.259
0.279
0.328
0.393
London
0.256
0.246
0.213
0.305
0.375
Lyon
0.298
0.296
0.287
0.357
0.370
Manchester
0.253
0.276
0.223
0.308
0.351
Marseille
0.222
0.224
0.260
0.278
0.290
Paris
0.223
0.212
0.175
0.284
0.327
Average
0.254
0.253
0.249
0.307
0.354
6
(b) F
(c) PREDGNN, DISTRICTNET,
(e) BD. 20
(0) FIG, 20
(g) PREDGNN, 20 (h) DISTRICTNET, 20
Figure 8: Districting solutions given by BD, FIG, PredictGNN, and DistrictNet for the city of London with district target sizes of 6 and 20 BUs. The depot shown white star.
(b) FIG, - (c) PREDGNN, t 6 (d) DISTRICTNET t 6 Figure 9: Districting solutions given by BD. FIG, PredicIGNN, and DistrictNet for the city of Manchester with district target sizes of 6 BUs. The depot is shown as white star.
(a) 6
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: The claims presented in the abstract and introduction accurately reflect the paper's contributions and scope and 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
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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
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 that, although our approach could be applied 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 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
23

---

Question: For each theoretical result, does the paper provide the full set of assumptions and 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 cross- referenced.
All assumptions should be clearly stated or referenced 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 short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes].
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.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, 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 novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, 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 instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
24

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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 joined as supple- mentary material. It will be made openly available on an online repository under an MIT license after publication. Our submission includes ReadMe file indicating how to run all experiments in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
aswsonoliiiyyy (opplllyy)) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nniss.. cc/ cac//pulicc/ae /gwid//g///////eeee/eeo SoodeSubmissionle
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes].
Justification: The key aspects of our experimental setting are described at the beginning of Section 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 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.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes].
25

---

Justification: We perform a statistical analysis of the results and include it in the ablation study in Table 1. Figure also includes 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, confi- dence intervals, statistical significance tests, 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, 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.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 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 range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes].
Justification:
The characteristics of the worker given the heginning of Section 5.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate 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 (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https neurips. cc/public e/Ethi csGuidel ines?
Answer: [Yes].
Justification:
We have reviewed and the NeurIPS Code of Ethics and consistently adhere
it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
26

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: Our work focuses solving 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 no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification:
In our view, the paper does not pose risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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
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?
Question:
Answer: [Yes].
Justification: The creators of the code reused in this paper are properly credited, both the main body and appendices. When possible, link to the source of the assets provided.
27

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]..
Justification: The main asset introduced in this paper is the code. It is properly documented and follows best-practice as best as possible.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
28

---

Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
29


Reviews:
[{"review_id": "2IwrE0kLGf", "reviewer": "Reviewer_qHFv", "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. \n\nHowever, 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. \n\nAnother 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": "Please see the weaknesses.", "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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "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.", "weaknesses": "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. \n\nAnother 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and insightful comments. We answer your questions below and clarify the concerns discussed in the report.\n\n> 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. [...] 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. [...] 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.\n\nThank you for your comments. In this work, we focus on the 'cost' metric because our task at hand is to solve the problem $\\min_{\\lambda \\in \\Lambda} \\sum_{d \\in \\mathcal{D}} C_{TSP}(d) \\lambda_d$, where $C_{TSP}(d)$ is the expected cost of a stochastic TSP in district $d$. In other words, we want to partition the city into efficient districts from a logistics perspective. The cost of a district corresponds to the long-term expected cost of deliveries (TSP) in each area. In contrast with other districting objectives for which a closed-form formula is available (e.g., compactness) this setting is computationally challenging. This is because closed-form formulas to approximate TSP costs are inaccurate, and sampling scenarios and solving TSPs is too time-consuming to be integrated in a districting algorithm.\n\nOur contribution is a new decision-aware approximation and solution method. Our approach can be readily extended to other districting metrics. This is a valuable direction for future work, as also highlighted by Reviewer WW6p. To adapt DistrictNet to this setting, we only need to adapt the generation of the training instances. This is why we claim that our framework applies to a wide range of constrained partitioning problems: it can work with any general districting cost function of the form $C(d)$. Hence, it can consider other metrics such as fairness, balancing, compactness, etc. Because the task at hand remains a constrained partitioning problem, our surrogate CMST layer will still capture the structure of the problem.\n\nWe will make sure to include additional discussions on this aspect in the final version of the paper. We will suggest exploring other districting metrics as future work, and specify why DistrictNet is especially suitable in these settings.\n\nLastly, we have evaluated the compactness of our districting solutions using Reock's formula. The results (see below; a larger value indicates higher compactness) demonstrate that DistrictNet generally achieves the highest compactness on average. However, it is crucial to note that, in logistics, delivery costs are not always correlated with compactness. The shape and orientation of the districts relative to the depot's position can significantly impact TSP costs.\n\n|    | BD  | FIG | PredGNN | AvgTSP | DistrictNet |\n|---|---|---|---|---|---|\n| Bristol |0.124 | 0.125 | 0.124 | 0.142 | **0.173** |\n| Leeds |0.168 | 0.154 | 0.187 | 0.223 | **0.268** |\n| London |0.086 | 0.089 | 0.08 | 0.096 | **0.11** |\n| Lyon |0.183 | 0.177 | 0.209 | 0.213 | **0.258**|\n| Manchester |0.167 | 0.165 | 0.142 | 0.258 | **0.272** |\n| Marseille |0.143 | 0.143 | 0.177 | **0.195** | 0.185 |\n| Paris |0.169 | 0.182 | 0.157 | **0.278** | 0.274 |\n| *Average* |0.149 | 0.148 | 0.154 | 0.201 | **0.22** |\n\n> The authors do not discuss the efficiency of the method. I hope that the authors can supplement this.\n\nOur algorithm is made of three main components: the data generation, the learning algorithm (setting the weights of the neural network), and the inference algorithm (using the neural network to obtain a solution on a given instance). Learning is quite fast (see Table 2 in the appendix) and inference is very fast (20 minutes). For DistrictNet, the crux of computations is in the generation of training data. Yet, we show in Figure 5 that DistrictNet provides already good results with only 20 training examples.\n\nWe will improve the discussion of the efficiency of our methods following your recommendation.\n\n> Another problem is that the baseline methods compared seem to be relatively old except for PREDGNN. [...] I hope the author can clarify the criteria for baseline selection.\n\nTo our knowledge, the recent work of Ferraz et al. (2024) represents the state-of-the-art for districting and routing problems. The two benchmarks BD and FIG stem from the long history of analytical results on TSPs and, in particular, the formula of Beardwood et al. (1959) on approximation formulas in asymptotic regimes with many points. The recent work of Kou et al. (2022), *Optimal TSP tour length estimation using standard deviation as a predictor*, shows that more sophisticated regression methods do not significantly outperform the formula of Beardwood et al. That is why we include the two benchmarks BD and FIG even if they are relatively older.\n\nThis discussion will be added to the paper. Note also that we have included an additional benchmark method (AvgTSP) following the suggestion of Reviewer S4NW.\n\n> The districting methods I know in terms of road network, such as CCH, have not been used as the baseline method.\n\nThank you for this suggestion. We understand that you refer to Customizable Contraction Hierarchies (CCH), an efficient technique to compute distances over road networks. Please correct us if our interpretation is wrong.\n\nSince CCH is a technique designed to speed up shortest-path computations, it cannot be directly used in our districting-and-routing context to contract edges and speed up the method. This is because (1) customer positions in each district are random (they are calculated over 100 scenarios), and (2) we calculate TSPs and not shortest paths.\n\nWe thank you again for your review, which allowed us to significantly improve the discussion of the general value of DistrictNet for districting.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JeUFXObFCN", "reviewer": "Reviewer_WW6p", "summary": "The paper discusses the development and evaluation of a new method called \nDISTRICTNET for addressing districting and routing problems using neural networks.\nThe approach focuses on minimizing the Fenchel Young loss and generalizing to large \nout-of-distribution instances from training on smaller instances. The method involves \na representation of the instances as a set of graph weights learned by GNN. These weights \nare fed to a CMST algorithm to obtain the spatial partitioning. Comparative \nbenchmarks include linear regression models and graph neural networks trained \nfor cost estimation. Results show that DISTRICTNET can achieve lower costs with \na small number of training examples but benefits from more examples, \nwith diminishing returns.", "questions": "Add \"routing\" to the paper title.\n\nEach benchmark method has a different definition of a district cost. The outputs of each of \nthese algorithms are a result of these different cost definitions or are due to their \ndifferent approaches?", "limitations": "This is a theoretical paper with no immediate connection to societal impact.", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "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\nmaterial is essential and the authors should consider if the mathematical treatment \nof several issues that were not relevant for the algorithm proposed should not be moved to \nthe appendix in exchange of bringing some of the appendix to the main paper. For example,\nI was lost about the district demand and cost features along the paper. This is \nexplained in the appendix. \n\nThe datasets are small, with the number of areas varying between 120 and 983.\nThey use an additional set of 27 cities, 25 of them with less than 100 areas and a \nmaxium of 684.  \n\nThe benchmarks did not include what the authors call the quick heuristic methods.\nI also found other recent papers in important venues dealing with this districting \nproblem by partitioning a minimum spanning tree as in the paper and with simpler \nmethods. \nTeixeira, 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.\nLuo, 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.\nLuo, 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.\nMcCartan, C., & Imai, K. (2023). Sequential Monte Carlo for sampling balanced and compact redistricting plans. The Annals of Applied Statistics, 17(4), 3300-3323.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your detailed review of the paper and the helpful suggestions. We respond to your concerns and questions below.\n\n> The supplementary material is essential and the authors should consider [...] bringing some of the appendix to the main paper. For example, I was lost about the district demand and cost features along the paper.[...] 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?\n\nThank you for this comment. Essentially, we want find a districting solution $\\lambda$ that minimizes $\\min_{\\lambda \\in \\Lambda} \\sum_{d \\in \\mathcal{D}} C_{TSP}(d) \\lambda_d$, where $C_{TSP}(d)$ is the cost of district $d$. A district's cost is the expected cost of a \"stochastic\" TSP. The true cost $\\sum_{d \\in \\mathcal{D}} C_{TSP}(d) \\lambda_d$ is the main performance metric. This is the cost that we measure in all our experiments.\n\nEvaluating a district's cost $C_{TSP}(d)$ is too computationally demanding to be integrated into a districting algorithm at all steps of the search. Hence, the benchmarks approximate this cost during the search. This will be clarified in the paper.\n\nTo approximate districts' costs, the benchmarks train regression models using features of the districts. In contrast, DistrictNet does not learn to approximate the districting costs: it learns to parameterize a surrogate optimization problem. In the final version, we will present the key district features in the main body of the paper. Thank you for this suggestion!\n\n> The datasets are small, with the number of areas varying between 120 and 983.\n\nIn the paper, we train on instances containing 30 basic units (BUs) and evaluate on instances with up to 900 BUs. This is an increase of 30x from train to test, and 7.5x compared to the largest instances of Ferraz et al. (2024). This increase is not linear in terms of complexity: the complexity of districting problems increases exponentially with the number of BUs and the size of a district.\n\nOur experiments show that we can scale to the largest and most dense European urban areas and provide good solution qualities. Following your suggestion, we investigate whether our approach can scale even further by considering 2 000 BUs of the Ile-de-France region. DistrictNet provides the best performance, showing that it generalizes to instances that are more than 60 times larger than the training ones. This experiment will be added to the paper.\n\n|   BD  |   FIG  |   PredGNN  |   AvgTSP  |   DistrictNet  |\n|----|----|----|----|----|\n| 2379.0  |  2388.8  |  2295.2   |  2262.7  |  **2205.7** |\n| + 7.8\\%  | + 8.3\\%  | + 4.0\\%  | + 2.6\\%  |   **0.0**  |\n\n> They use an additional set of 27 cities, 25 of them with less than 100 areas.\n\nWe want to clarify: the 27 small cities presented in Appendix B.2 are used to generate the training data. Our test instances are at least four times larger containing more than 120 BUs. We intentionally train on cities with 30 BUs to show that DistrictNet can learn from small cities and generalize to much larger ones.\n\n> The benchmarks did not include what the authors call the quick heuristic methods.\n\nWe do include two quick heuristic methods: BD and FIG, which apply an iterated local search with continuous approximations of district costs. These methods stem from the seminal work of Beardwood et al. (1956): \\textit{The shortest path through many points}. Several recent works have shown that the formula of Beardwood et al. holds remarkably well against more sophisticated regression functions for uniform distributions; see, e.g., Kou et al. (2022), *Optimal TSP tour length estimation using standard deviation as a predictor*.\n\nFurther, following the recommendation of Reviewer CwjD, we introduced a new benchmark method. It approximates a district's cost by the cost of the TSP that goes through the barycentre of each of its BUs.\n\n> 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.\n\nThank you for referring us to the rich literature on partition sampling. The suggested works provide methods to sample districts with constraints on the balance, contiguity, and compactness of the partitioning. Balance is to be understood w.r.t. features such as mortality rates in Teixeira et al. These approaches are motivated by the fact that sampling from a uniform distribution of partitions tends to have low compactness. Hence, they recommend sampling from the spanning tree distribution.\n\nOur approach is fundamentally different. It is discriminative, in the sense that it strives to identify the single partition with minimum cost. In contrast, the suggested papers are generative: they output a distribution of partitions. Further, none of them considers districting-and-routing applications, and adapting them to handle routing applications is not straightforward.\n\nStill, our work and the literature on partition sampling have very interesting connections. A first idea could be to solve approximately the CMST problems by sampling from balanced partitioning partitions. In this way, we might replace our current search algorithm (iterated local search) with a specialized type of random search over spanning trees. A second idea is to integrate considerations about balance and compactness into the problem. To this end, given examples of districts that are compact and balanced, DistrictNet can be directly trained to learn to imitate them using a parameterized CMST.\n\nWe will include this discussion in the paper, and highlight the opportunities in future research on the integration of decision-aware partitioning and sampling from spanning trees. Thank you for this suggestion!\n\n> Add \"routing\" to the paper title.\n\nYes, we will specify that we solve districting-and-routing problems in the paper title.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yfwzNyIZeF", "reviewer": "Reviewer_S4NW", "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.", "questions": "- I am not sure why we should evaluate the p-value in this setting. Where does the randomness come from?\n- 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.\n\n~~~\n\nAfter discussions, I have updated my score.", "limitations": "In my opinion, the authors have addressed the issue adequately and mentioned these points.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The connection between CMST and the districting problem is utilized for decision-aware learning.\n- Compared with the recent existing work [Ferraz et al. 2024], a more powerful learning methodology through GNN and FY loss was studied and evaluated, demonstrated using real data (i.e., real districts in famous cities).\n- The experimental results show better results than those of existing solvers.", "weaknesses": "- 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.\n- 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you very much for your review and detailed evaluation of our paper. \n\n> 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.\n\nThank you for this remark. We follow Ferraz et al. (2024) in the sense that we use a GNN to embed graphs in a latent space. However, there is a major distinction: we use the GNN to parameterize a surrogate optimization model rather than to estimate the cost of a district. This is not a direct application at all. It requires a suitable loss function, constructing CMST targets to learn from, and an appropriate method to backpropagate gradients. The major benefit of this approach is its ability to generalize. As shown in Table 1, it is the combination of GNN and the CMST layer that allows finding good solutions with a single model on all the cities and sizes used in our experiments.\n\n> 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).\n\nThank you for this suggestion. We agree that the presentation of the datasets can be improved. To provide comparable results with Ferraz et al, we include the same districting tasks on cities in England. However, we expand the experimental setting by considering larger cities and by including cities in France. Thus, we consider some of the largest and most dense European urban areas. We show that we can solve real-world districting tasks and generalize over cities that are diverse in terms of geography and social characteristics.\n\n> I am not sure why we should evaluate the p-value in this setting. Where does the randomness come from?\n\nIn Table 1, we measure the empirical performance of our method on 35 districting tasks from real-world cities. The randomness comes from the selection of the test instances from the distribution of possible districting tasks. The $p$-value tells us that, even though we have a limited set of tasks, we can confidently tell that the difference in average performance is not due to random chance but to a clear advantage in the method.\n\n> 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.\n\nFormally, we solve the problem\n\n$\\min_{\\lambda \\in \\Lambda}\\sum_{d \\in \\mathcal{D}} E_{\\xi}[c_{TSP}(d, \\xi)] \\lambda_d$,\n\nwhere $c_{TSP}(d, \\xi)$ is the cost of the TSP in district $d$ with requests $\\xi$. The suggestion of the reviewer is to solve instead\n\n$\\min_{\\lambda \\in \\Lambda} \\sum_{d \\in \\mathcal{D}} c_{TSP}(d, E_\\xi[\\xi]) \\lambda_d$,\n\ni.e., switching the expectation and minimization operator.\n\nWe did not implement this benchmark because this approximation leads to poor results in many stochastic problems (see e.g., Chapter 4.2 of Birge and Louveaux, *Introduction to stochastic programming*). This is because this approximation ignores the variance of the random variable $\\xi$.\n\nWe followed your suggestion and implemented this method as a baseline. In our setting, the demand distribution is known, so we do not need to forecast it. For each basic unit, the average demand request $E_\\xi[\\xi]$ is a single request that appears at the barycentre of the area. Evaluating a district cost reduces to solving a TSP over the barycentres of all its BUs.\n\nWe integrate this approximation in an iterated local search and evaluate all our districting tasks. The results (called AvgTSP in the table below) show that this method finds districts of reasonably high quality and outperforms the other baselines. Still, DistrictNet outperforms it by more than 4\\% on average.\n\n| Method        | Avg Rel Diff       | p-value              |\n|---------------|--------------------|----------------------|\n| Benchmark 1, BD    | 10.02 \\% | 1.3e-08 |\n| Benchmark 2, FIG   | 10.17 \\% | 1.6e-08  |\n| Benchmark 3, PredGnn  | 11.56 \\% | 1.5e-10  |\n| **Benchmark 4, AvgTSP**   | 4.44 \\% | 2.7e-04  |\n| DistrictNet   | **0.0 \\%**             |     -                |\n\nWe will add this method to the paper with a formal description and a detailed analysis of its performance. Thank you for this great suggestion!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UBJQzxUZu9", "reviewer": "Reviewer_VFD5", "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.", "questions": "- It is unclear to me what the costs (objective) are in the numerical experiments. \n\n- Related to weakness 1, what is the downside of performing such conversion?", "limitations": "Discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Districting problems are common in practice, so I believe this paper is interesting to a broad community.\n\n2. The mapping from a districting problem to a minimum spanning tree problem is elegant and well justified. \n\n3. The numerical studies were well designed and excuted. I particularly appreciate the analysis related to the model's generalizablity, which we do not see in every learning to optimize paper. \n\n4. The paper was well structed and presented. I found it easy to follow.", "weaknesses": "- 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. \n\n- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your in-depth review, valuable suggestions, and overall positive appreciation of the paper.\n\n> Some benchmarks from the OR/optimization community are missing. When the demands are uniformly distributed, I believe the second-stage TSP objective value has some very nice closed-form approximations (continuous approximation). Such approximation usually leads to tractable problems with good performance. It'd be good to see some comparisons.\n\nThe two benchmarks we call BD and FIG belong precisely to the long stream of research on continuous approximations of TSPs. They trace back to Beardwood et al. (1956): *The shortest path through many points*. Several recent works have shown that the formula of Beardwood et al. (and its extension to districting problems, i.e., BD and FIG) holds remarkably well empirically against more sophisticated regression functions for uniform distributions; see e.g., Kou et al. (2022), *Optimal TSP tour length estimation using standard deviation as a predictor*.\n\nWe briefly discussed these results in the introduction of the paper. We will improve the presentation and recall it when introducing the benchmarks in the experiment section.\n\nNote also that we introduced a new benchmark method following the recommendation of Reviewer CwjD, which can be seen as a point-forecast approximation of the stochastic TSP.\n\n> 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.\n\nIn the paper, we train on instances containing 30 basic units (BUs) and test on instances with up to 900 BUs. This is an increase of 30x from train to test, and 7.5x compared to the largest instances of Ferraz et al. This increase is not linear in terms of complexity: the complexity of districting problems increases exponentially with the number of BUs and the size of a district.\n\nOur experiments show that we can scale to the largest and most dense European urban areas and provide good solution qualities. We intentionally train on cities with 30 BUs to show that DistrictNet can learn from small cities and generalize to very large ones. Following your suggestion, we investigate whether our approach can scale even further by considering 2 000 BUs of the Ile-de-France region. The results (see below) show that DistrictNet still performs best. This experiment will be added to the paper.\n\n|   |   BD  |   FIG  |   PredGNN  |   AvgTSP  |   DistrictNet  |\n|---|---|---|---|---|---|\n| Districting cost  | 2379.0  |  2388.8  |  2295.2   |  2262.7  |  **2205.7** |\n| Relative to best | + 7.8\\%  | + 8.3\\%  | + 4.0\\%  | + 2.6\\%  |   **0.0**  |\n\n> It is unclear to me what the costs (objective) are in the numerical experiments.\n\nEssentially, we want to find the solution to $\\min_{\\lambda \\in \\Lambda} \\sum_{d \\in \\mathcal{D}} C_{TSP}(d) \\lambda_d$ where $C_{TSP}(d)$ is the cost of district $d$ computed as the expected cost of a stochastic TSP in district $d$. The true cost $\\sum_{d \\in \\mathcal{D}} C_{TSP}(d) \\lambda_d$ is our main performance metric.\n\nAll the benchmarks approximate the cost $C_{TSP}(d)$, which is too computationally expensive to calculate in a search algorithm. To do this, they train regression models using features of the districts. DistrictNet does not approximate the districting costs: it learns to parameterize a surrogate optimization problem.\n\nAlthough all methods have a different approximation for district costs, they are all evaluated using the true performance metric $C_{TSP}(d)$ in our experiments. We will clarify this in the paper, thank you for highlighting this potential for improvement!\n\n> 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. [...] 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. [...] What is the downside of performing such conversion?\n\n\"Approximating a harder problem by an easier one\" can be seen as a paradigm shift for solving difficult combinatorial optimization problems. Classic approaches in OR rely on a purely combinatorial optimization approach. They design an algorithm that works for any problem instance and they tend to focus on worst-case complexity.\n\nOn the contrary, the \"approximate by an easier problem\" literature relies on learning. Its key advantage is being very efficient online because it shifts most of the computing time offline to the training algorithm. Provided that the learning architecture and surrogate optimization layer are well chosen, it enables excellent performance on the test instances if they remain close to the training distribution. Being a discriminative approach (instead of a generative one), it tends to require less data to obtain good performance.\n\nThere are also downsides. First, until now, there are no known \"worst-case\" theoretical guarantees on the quality of the solution. Instead, guarantees are in expectation over the training set, as is usual in ML. Further, the architecture (i.e., the neural network and surrogate optimization layer) may be poorly chosen. Finally, learning may be intensive computationally, both when generating the training instances and in the training algorithm. That is why we study the strategy of training on smaller instances and evaluating on larger ones.\n\nFor a general discussion of these aspects and an analytical characterization of generalization bounds, we recommend the preprint that appeared online a few days ago: Aubin-Frankowski et al. (2024), *Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems*, arXiv:2407.17200. \n\nWhile an extended discussion is beyond the scope of this paper, we will update our paper to present these advantages and limitations. Thank you for this encouraging suggestion!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## We thank the reviewers for their constructive comments and feedback

Dear Reviewers, Dear Area Chair,

We want to express our sincere thanks for the detailed reviews of our work and the constructive feedback. The reviewers have appreciated the value of our decision-aware approach to solve large districting problems and the potential of identifying the CMST as a differentiable optimization surrogate for partitioning problems

Several comments have been raised by multiple reviewers, addressing: (a) the definition of districting costs and the approximations used in the benchmarks, (b) what makes a districting task large, (c) what justifies the choice of benchmarks and whether others could be included, and (d) what makes DistrictNet applicable to other partitioning problems. We have answered these points in detail in each reviewer's rebuttal. We also provide additional results: a new benchmark method following the suggestion of Reviewer CwjD, and results on an even larger districting task with 2 000 basic units.

We are available to answer any remaining questions during the discussion period.

Meta-review: 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.
Decision: Accept (poster)