Swap-based Deep Reinforcement Learning for Facility Location Problems in Networks

• URL: http://arxiv.org/abs/2312.15658v1
• Date: Mon, 25 Dec 2023 09:00:25 GMT
• Title: Swap-based Deep Reinforcement Learning for Facility Location Problems in Networks
• Authors: Wenxuan Guo, Yanyan Xu, Yaohui Jin
• Abstract summary: 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.
• Score: 11.613708854129037
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Facility location problems on graphs are ubiquitous in real world and hold significant importance, yet their resolution is often impeded by NP-hardness. Recently, machine learning methods have been proposed to tackle such classical problems, but they are limited to the myopic constructive pattern and only consider the problems in Euclidean space. To overcome these limitations, we propose a general swap-based framework that addresses the p-median problem and the facility relocation problem on graphs and a novel reinforcement learning model demonstrating a keen awareness of complex graph structures. Striking a harmonious balance between solution quality and running time, our method surpasses handcrafted heuristics on intricate graph datasets. Additionally, we introduce a graph generation process to simulate real-world urban road networks with demand, facilitating the construction of large datasets for the classic problem. For the initialization of the locations of facilities, we introduce a physics-inspired strategy for the p-median problem, reaching more stable solutions than the random strategy. The proposed pipeline coupling the classic swap-based method with deep reinforcement learning marks a significant step forward in addressing the practical challenges associated with facility location on graphs.

Related papers

• CHARME: A chain-based reinforcement learning approach for the minor embedding problem [16.24890195949869]
  We propose a novel approach utilizing Reinforcement Learning (RL) techniques to address the minor embedding problem, named CHARME. CHARME includes three key components: a Graph Neural Network (GNN) architecture for policy modeling, a state transition algorithm ensuring solution validity, and an order exploration strategy for effective training. In details, CHARME yields superior solutions compared to fast embedding methods such as Minorminer and ATOM.
  arXiv  Detail & Related papers  (2024-06-11T10:12:10Z)
• 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)
• GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
  We propose an adaptive Graph Attention Sampling with the Edges Fusion framework to solve vehicle routing problems. Our proposed model outperforms the existing methods by 2.08%-6.23% and shows stronger generalization ability.
  arXiv  Detail & Related papers  (2024-05-21T03:33:07Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  We introduce the first-ever completely equivariant model and training to solve problems. It is essential to capture the multiscale structure of the input graph. We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
  arXiv  Detail & Related papers  (2023-10-24T06:22:20Z)
• Network Alignment with Transferable Graph Autoencoders [79.89704126746204]
  We propose a novel graph autoencoder architecture designed to extract powerful and robust node embeddings. We prove that the generated embeddings are associated with the eigenvalues and eigenvectors of the graphs. Our proposed framework also leverages transfer learning and data augmentation to achieve efficient network alignment at a very large scale without retraining.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• Neural combinatorial optimization beyond the TSP: Existing architectures under-represent graph structure [9.673093148930876]
  We analyze how and whether recent neural architectures can be applied to graph problems of practical importance. We show that augmenting the structural representation of problems with Distance is a promising step towards the still-ambitious goal of learning multi-purpose autonomous solvers.
  arXiv  Detail & Related papers  (2022-01-03T14:14:28Z)
• Physics informed neural networks for continuum micromechanics [68.8204255655161]
  Recently, physics informed neural networks have successfully been applied to a broad variety of problems in applied mathematics and engineering. Due to the global approximation, physics informed neural networks have difficulties in displaying localized effects and strong non-linear solutions by optimization. It is shown, that the domain decomposition approach is able to accurately resolve nonlinear stress, displacement and energy fields in heterogeneous microstructures obtained from real-world $mu$CT-scans.
  arXiv  Detail & Related papers  (2021-10-14T14:05:19Z)
• On the Difficulty of Generalizing Reinforcement Learning Framework for Combinatorial Optimization [6.935838847004389]
  Combinatorial optimization problems (COPs) on the graph with real-life applications are canonical challenges in Computer Science. The underlying principle of this approach is to deploy a graph neural network (GNN) for encoding both the local information of the nodes and the graph-structured data. We use the security-aware phone clone allocation in the cloud as a classical quadratic assignment problem (QAP) to investigate whether or not deep RL-based model is generally applicable to solve other classes of such hard problems.
  arXiv  Detail & Related papers  (2021-08-08T19:12:04Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  This paper proposes a novel spatial-spectral HSI classification method via multiple random anchor graphs ensemble learning (RAGE) Firstly, the local binary pattern is adopted to extract the more descriptive features on each selected band, which preserves local structures and subtle changes of a region. Secondly, the adaptive neighbors assignment is introduced in the construction of anchor graph, to reduce the computational complexity.
  arXiv  Detail & Related papers  (2021-03-25T09:31:41Z)
• Differentiable Causal Discovery from Interventional Data [141.41931444927184]
  We propose a theoretically-grounded method based on neural networks that can leverage interventional data. We show that our approach compares favorably to the state of the art in a variety of settings.
  arXiv  Detail & Related papers  (2020-07-03T15:19:17Z)
• Local Propagation in Constraint-based Neural Network [77.37829055999238]
  We study a constraint-based representation of neural network architectures. We investigate a simple optimization procedure that is well suited to fulfil the so-called architectural constraints.
  arXiv  Detail & Related papers  (2020-02-18T16:47:38Z)

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.