DistrictNet: Decision-aware learning for geographical districting

• URL: http://arxiv.org/abs/2412.08287v1
• Date: Wed, 11 Dec 2024 11:02:48 GMT
• Title: DistrictNet: Decision-aware learning for geographical districting
• Authors: Cheikh Ahmed, Alexandre Forel, Axel Parmentier, Thibaut Vidal,
• Abstract summary: Districting is a complex problem that consists in partitioning a geographical area into small districts. We present a structured learning approach to find high-quality solutions to real-world districting problems in a few minutes. Our approach outperforms existing methods as it can significantly reduce costs on real-world cities.
• Score: 47.36059095502583
• License:
• 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.

Related papers

• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems. We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• Swap-based Deep Reinforcement Learning for Facility Location Problems in Networks [11.613708854129037]
  Facility location problems on graphs are ubiquitous in real world and hold significant importance. We propose a swap-based framework that addresses the p-median problem and the facility relocation problem on graphs. We also introduce a novel reinforcement learning model demonstrating a keen awareness of complex graph structures.
  arXiv  Detail & Related papers  (2023-12-25T09:00:25Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
  This work proposes new characterizations of linear programming (ILP) with the concept of boundary solutions. We develop a new local search algorithm Local-ILP, which is efficient for solving general ILP validated on a large heterogeneous problem dataset. Experiments conducted on the MIPLIB dataset show the effectiveness of our algorithm in solving large-scale hard ILP problems.
  arXiv  Detail & Related papers  (2023-04-29T07:22:07Z)
• A machine learning framework for neighbor generation in metaheuristic search [4.521119623956821]
  We propose a general machine learning framework for neighbor generation in metaheuristic search. We validate our methodology on two metaheuristic applications.
  arXiv  Detail & Related papers  (2022-12-22T01:58:04Z)
• Less Emphasis on Difficult Layer Regions: Curriculum Learning for Singularly Perturbed Convection-Diffusion-Reaction Problems [21.615494601195472]
  We show that learning multi-scale fields simultaneously makes the network unable to advance its training and easily get stuck in poor local minima. We propose a novel curriculum learning method that encourages neural networks to prioritize learning on easier non-layer regions while downplaying learning on harder layer regions.
  arXiv  Detail & Related papers  (2022-10-23T10:15:32Z)
• Hierarchical Planning for Resource Allocation in Emergency Response Systems [0.8602553195689513]
  A classical problem in city-scale cyber-physical systems is resource allocation under uncertainty. Online, offline, and decentralized approaches have been applied to such problems, but they have difficulty scaling to large decision problems. We present a general approach to hierarchical planning that leverages structure in city-level CPS problems for resource allocation under uncertainty.
  arXiv  Detail & Related papers  (2020-12-24T15:55:23Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  We propose a new low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from Leiden-k-cut. This proposed algorithm is scalable, outperforms state-of-the-art algorithms, and outperforms in real-world time with little additional cost.
  arXiv  Detail & Related papers  (2020-12-04T15:46:30Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  This paper presents an approach named MineReduce, which uses mined patterns to perform problem size reduction. We present an application of MineReduce to improve a for the heterogeneous fleet vehicle routing problem.
  arXiv  Detail & Related papers  (2020-05-15T08:49:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.