Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt

• URL: http://arxiv.org/abs/2310.18264v1
• Date: Fri, 27 Oct 2023 16:51:41 GMT
• Title: Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt
• Authors: Yining Ma, Zhiguang Cao, Yeow Meng Chee
• Abstract summary: We present Neural k-Opt (NeuOpt), a novel learning-to-search (L2S) solver for routing problems. It learns to perform flexible k-opt exchanges based on a tailored action factorization method and a customized recurrent dual-stream decoder.
• Score: 30.510841880901655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we present Neural k-Opt (NeuOpt), a novel learning-to-search (L2S) solver for routing problems. It learns to perform flexible k-opt exchanges based on a tailored action factorization method and a customized recurrent dual-stream decoder. As a pioneering work to circumvent the pure feasibility masking scheme and enable the autonomous exploration of both feasible and infeasible regions, we then propose the Guided Infeasible Region Exploration (GIRE) scheme, which supplements the NeuOpt policy network with feasibility-related features and leverages reward shaping to steer reinforcement learning more effectively. Additionally, we equip NeuOpt with Dynamic Data Augmentation (D2A) for more diverse searches during inference. Extensive experiments on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that our NeuOpt not only significantly outstrips existing (masking-based) L2S solvers, but also showcases superiority over the learning-to-construct (L2C) and learning-to-predict (L2P) solvers. Notably, we offer fresh perspectives on how neural solvers can handle VRP constraints. Our code is available: https://github.com/yining043/NeuOpt.

Related papers

• NavCoT: Boosting LLM-Based Vision-and-Language Navigation via Learning Disentangled Reasoning [101.56342075720588]
  Vision-and-Language Navigation (VLN), as a crucial research problem of Embodied AI, requires an embodied agent to navigate through complex 3D environments following natural language instructions. Recent research has highlighted the promising capacity of large language models (LLMs) in VLN by improving navigational reasoning accuracy and interpretability. This paper introduces a novel strategy called Navigational Chain-of-Thought (NavCoT), where we fulfill parameter-efficient in-domain training to enable self-guided navigational decision.
  arXiv  Detail & Related papers  (2024-03-12T07:27:02Z)
• Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs [63.768739279562105]
  We show that for a particular choice of mask weights that do not depend on the learning targets, this kernel is equivalent to the NTK of the gated ReLU network on the training data. A consequence of this lack of dependence on the targets is that the NTK cannot perform better than the optimal MKL kernel on the training set.
  arXiv  Detail & Related papers  (2023-09-26T17:42:52Z)
• In-Context Operator Learning with Data Prompts for Differential Equation Problems [12.61842281581773]
  This paper introduces a new neural-network-based approach, namely In-Context Operator Networks (ICON) ICON simultaneously learn operators from the prompted data and apply it to new questions during the inference stage, without any weight update. Our numerical results show the neural network's capability as a few-shot operator learner for a diversified type of differential equation problems.
  arXiv  Detail & Related papers  (2023-04-17T05:22:26Z)
• Benign Overfitting for Two-layer ReLU Convolutional Neural Networks [60.19739010031304]
  We establish algorithm-dependent risk bounds for learning two-layer ReLU convolutional neural networks with label-flipping noise. We show that, under mild conditions, the neural network trained by gradient descent can achieve near-zero training loss and Bayes optimal test risk.
  arXiv  Detail & Related papers  (2023-03-07T18:59:38Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  We propose L2Dive to learn specific diving structurals with graph neural networks. We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions.
  arXiv  Detail & Related papers  (2023-01-24T12:01:45Z)
• E2-AEN: End-to-End Incremental Learning with Adaptively Expandable Network [57.87240860624937]
  We propose an end-to-end trainable adaptively expandable network named E2-AEN. It dynamically generates lightweight structures for new tasks without any accuracy drop in previous tasks. E2-AEN reduces cost and can be built upon any feed-forward architectures in an end-to-end manner.
  arXiv  Detail & Related papers  (2022-07-14T09:04:51Z)
• Efficient Neural Neighborhood Search for Pickup and Delivery Problems [33.26295166939733]
  We present an efficient Neural Neighborhood Search (N2S) approach for pickup and delivery problems ( PDPs) In specific, we design a powerful Synthesis Attention that allows the vanilla self-attention to synthesize various types of features regarding a route solution. We also exploit two customized decoders that automatically learn to perform removal and reinsertion of a pickup-delivery node pair to tackle the precedence constraint.
  arXiv  Detail & Related papers  (2022-04-25T02:27:59Z)
• MultiAuto-DeepONet: A Multi-resolution Autoencoder DeepONet for Nonlinear Dimension Reduction, Uncertainty Quantification and Operator Learning of Forward and Inverse Stochastic Problems [12.826754199680474]
  A new data-driven method for operator learning of differential equations(SDE) is proposed in this paper. The central goal is to solve forward and inverse problems more effectively using limited data.
  arXiv  Detail & Related papers  (2022-04-07T03:53:49Z)
• A Study of the Mathematics of Deep Learning [1.14219428942199]
  "Deep Learning"/"Deep Neural Nets" is a technological marvel that is now increasingly deployed at the cutting-edge of artificial intelligence tasks. This thesis takes several steps towards building strong theoretical foundations for these new paradigms of deep-learning.
  arXiv  Detail & Related papers  (2021-04-28T22:05:54Z)
• 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)

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.