Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search

• URL: http://arxiv.org/abs/2005.09330v1
• Date: Tue, 19 May 2020 09:50:35 GMT
• Title: Dynamic Partial Removal: A Neural Network Heuristic for Large Neighborhood Search
• Authors: Mingxiang Chen, Lei Gao, Qichang Chen, Zhixin Liu
• Abstract summary: This paper presents a novel neural network design that learns the for Large Neighborhood Search (LNS) LNS consists of a destroy operator and a repair operator that specify a way to carry out the neighborhood search to solve the Combinatorial Optimization problems.
• Score: 6.297706165407368
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a novel neural network design that learns the heuristic for Large Neighborhood Search (LNS). LNS consists of a destroy operator and a repair operator that specify a way to carry out the neighborhood search to solve the Combinatorial Optimization problems. The proposed approach in this paper applies a Hierarchical Recurrent Graph Convolutional Network (HRGCN) as a LNS heuristic, namely Dynamic Partial Removal, with the advantage of adaptive destruction and the potential to search across a large scale, as well as the context-awareness in both spatial and temporal perspective. This model is generalized as an efficient heuristic approach to different combinatorial optimization problems, especially to the problems with relatively tight constraints. We apply this model to vehicle routing problem (VRP) in this paper as an example. The experimental results show that this approach outperforms the traditional LNS heuristics on the same problem as well. The source code is available at \href{https://github.com/water-mirror/DPR}{https://github.com/water-mirror/DPR}.

Related papers

• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve Combinatorial optimization (CO) problems. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventionals.
  arXiv  Detail & Related papers  (2024-07-23T13:34:35Z)
• Graph Convolutional Branch and Bound [1.8966938152549224]
  This article demonstrates the effectiveness of employing a deep learning model in an optimization pipeline. In this context, neural networks can be leveraged to rapidly acquire valuable information.
  arXiv  Detail & Related papers  (2024-06-05T09:42:43Z)
• Iterative Soft Shrinkage Learning for Efficient Image Super-Resolution [91.3781512926942]
  Image super-resolution (SR) has witnessed extensive neural network designs from CNN to transformer architectures. This work investigates the potential of network pruning for super-resolution iteration to take advantage of off-the-shelf network designs and reduce the underlying computational overhead. We propose a novel Iterative Soft Shrinkage-Percentage (ISS-P) method by optimizing the sparse structure of a randomly network at each and tweaking unimportant weights with a small amount proportional to the magnitude scale on-the-fly.
  arXiv  Detail & Related papers  (2023-03-16T21:06:13Z)
• Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
  We first propose a new graph neural network (GNN) model designed using a probabilistic method. Our approach introduces a new way of applying GNNs towards enhancing the classical backtracking algorithm used in AI.
  arXiv  Detail & Related papers  (2022-11-26T00:01:01Z)
• RDRN: Recursively Defined Residual Network for Image Super-Resolution [58.64907136562178]
  Deep convolutional neural networks (CNNs) have obtained remarkable performance in single image super-resolution. We propose a novel network architecture which utilizes attention blocks efficiently.
  arXiv  Detail & Related papers  (2022-11-17T11:06:29Z)
• Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut [0.0]
  In Nature Machine Intelligence 4, 367 (2022), Schuetz et al provide a scheme to employ neural graph networks (GNN) to solve a variety of classical, NP-hard optimization problems. It describes how the network is trained on sample instances and the resulting GNN is evaluated applying widely used techniques to determine its ability to succeed. However, closer inspection shows that the reported results for this GNN are only minutely better than those for gradient descent and get outperformed by a greedy algorithm.
  arXiv  Detail & Related papers  (2022-10-02T20:50:33Z)
• Imbedding Deep Neural Networks [0.0]
  Continuous depth neural networks, such as Neural ODEs, have refashioned the understanding of residual neural networks in terms of non-linear vector-valued optimal control problems. We propose a new approach which explicates the network's depth' as a fundamental variable, thus reducing the problem to a system of forward-facing initial value problems.
  arXiv  Detail & Related papers  (2022-01-31T22:00:41Z)
• DeepSplit: Scalable Verification of Deep Neural Networks via Operator Splitting [70.62923754433461]
  Analyzing the worst-case performance of deep neural networks against input perturbations amounts to solving a large-scale non- optimization problem. We propose a novel method that can directly solve a convex relaxation of the problem to high accuracy, by splitting it into smaller subproblems that often have analytical solutions.
  arXiv  Detail & Related papers  (2021-06-16T20:43:49Z)
• Online Limited Memory Neural-Linear Bandits with Likelihood Matching [53.18698496031658]
  We study neural-linear bandits for solving problems where both exploration and representation learning play an important role. We propose a likelihood matching algorithm that is resilient to catastrophic forgetting and is completely online.
  arXiv  Detail & Related papers  (2021-02-07T14:19:07Z)
• A Deep-Unfolded Reference-Based RPCA Network For Video Foreground-Background Separation [86.35434065681925]
  This paper proposes a new deep-unfolding-based network design for the problem of Robust Principal Component Analysis (RPCA) Unlike existing designs, our approach focuses on modeling the temporal correlation between the sparse representations of consecutive video frames. Experimentation using the moving MNIST dataset shows that the proposed network outperforms a recently proposed state-of-the-art RPCA network in the task of video foreground-background separation.
  arXiv  Detail & Related papers  (2020-10-02T11:40:09Z)
• Deep Adaptive Inference Networks for Single Image Super-Resolution [72.7304455761067]
  Single image super-resolution (SISR) has witnessed tremendous progress in recent years owing to the deployment of deep convolutional neural networks (CNNs) In this paper, we take a step forward to address this issue by leveraging the adaptive inference networks for deep SISR (AdaDSR) Our AdaDSR involves an SISR model as backbone and a lightweight adapter module which takes image features and resource constraint as input and predicts a map of local network depth.
  arXiv  Detail & Related papers  (2020-04-08T10:08:20Z)

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.