Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problems

• URL: http://arxiv.org/abs/2309.17089v1
• Date: Fri, 29 Sep 2023 09:36:37 GMT
• Title: Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problems
• Authors: Jonas K. Falkner and Lars Schmidt-Thieme
• Abstract summary: We show that even state-of-the-art neural construction methods are outperformed by simple iterations. We propose to use the ruin recreate principle that alternates between completely destroying a localized part of the solution and then recreating an improved variant.
• Score: 10.832715681422842
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In recent years new deep learning approaches to solve combinatorial optimization problems, in particular NP-hard Vehicle Routing Problems (VRP), have been proposed. The most impactful of these methods are sequential neural construction approaches which are usually trained via reinforcement learning. Due to the high training costs of these models, they usually are trained on limited instance sizes (e.g. serving 100 customers) and later applied to vastly larger instance size (e.g. 2000 customers). By means of a systematic scale-up study we show that even state-of-the-art neural construction methods are outperformed by simple heuristics, failing to generalize to larger problem instances. We propose to use the ruin recreate principle that alternates between completely destroying a localized part of the solution and then recreating an improved variant. In this way, neural construction methods like POMO are never applied to the global problem but just in the reconstruction step, which only involves partial problems much closer in size to their original training instances. In thorough experiments on four datasets of varying distributions and modalities we show that our neural ruin recreate approach outperforms alternative forms of improving construction methods such as sampling and beam search and in several experiments also advanced local search approaches.

Related papers

• Prompt Learning for Generalized Vehicle Routing [17.424910810870273]
  This work investigates an efficient prompt learning approach in Neural optimization for cross-distribution adaptation. The proposed model learns a set of prompts among various distributions and then selects the best-matched one to prompt a pre-trained attention model for each problem instance. It also outperforms existing generalized models on both in-distribution prediction and zero-shot generalization to a diverse set of new tasks.
  arXiv  Detail & Related papers  (2024-05-20T15:42:23Z)
• Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization [15.842155380912002]
  This work proposes a novel Instance-Conditioned Adaptation Model (ICAM) for better large-scale generalization of neural optimization. In particular, we design a powerful yet lightweight instance-conditioned Routing adaptation module for the NCO model. We develop an efficient three-stage reinforcement learning-based training scheme that enables the model to learn cross-scale features without any labeled optimal solution.
  arXiv  Detail & Related papers  (2024-05-03T08:00:19Z)
• ODE Discovery for Longitudinal Heterogeneous Treatment Effects Inference [69.24516189971929]
  In this paper, we introduce a new type of solution in the longitudinal setting: a closed-form ordinary differential equation (ODE) While we still rely on continuous optimization to learn an ODE, the resulting inference machine is no longer a neural network.
  arXiv  Detail & Related papers  (2024-03-16T02:07:45Z)
• Back to Basics: A Simple Recipe for Improving Out-of-Domain Retrieval in Dense Encoders [63.28408887247742]
  We study whether training procedures can be improved to yield better generalization capabilities in the resulting models. We recommend a simple recipe for training dense encoders: Train on MSMARCO with parameter-efficient methods, such as LoRA, and opt for using in-batch negatives unless given well-constructed hard negatives.
  arXiv  Detail & Related papers  (2023-11-16T10:42:58Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  This paper presents a new reinforcement learning approach that is based on entropy. In addition, we design an off-policy-based reinforcement learning technique that maximises the expected return. We show that our model can generalise to various route problems.
  arXiv  Detail & Related papers  (2022-05-31T09:51:48Z)
• Characterizing possible failure modes in physics-informed neural networks [55.83255669840384]
  Recent work in scientific machine learning has developed so-called physics-informed neural network (PINN) models. We demonstrate that, while existing PINN methodologies can learn good models for relatively trivial problems, they can easily fail to learn relevant physical phenomena even for simple PDEs. We show that these possible failure modes are not due to the lack of expressivity in the NN architecture, but that the PINN's setup makes the loss landscape very hard to optimize.
  arXiv  Detail & Related papers  (2021-09-02T16:06:45Z)
• Sample-based Regularization: A Transfer Learning Strategy Toward Better Generalization [8.432864879027724]
  Training a deep neural network with a small amount of data is a challenging problem. One of the practical difficulties that we often face is to collect many samples. By using the source model trained with a large-scale dataset, the target model can alleviate the overfitting originated from the lack of training data.
  arXiv  Detail & Related papers  (2020-07-10T06:02:05Z)
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization [9.176056742068813]
  End-to-end training of neural network solvers for graph optimization problems such as the Travelling Salesperson Problem (TSP) have seen a surge of interest recently. While state-of-the-art learning-driven approaches perform closely to classical solvers when trained on trivially small sizes, they are unable to generalize the learnt policy to larger instances at practical scales. This work presents an end-to-end neural optimization pipeline that unifies several recent papers in order to identify the principled biases, model architectures and learning algorithms that promote generalization to instances larger than those seen in training.
  arXiv  Detail & Related papers  (2020-06-12T10:14:15Z)
• Learning to Stop While Learning to Predict [85.7136203122784]
  Many algorithm-inspired deep models are restricted to a fixed-depth'' for all inputs. Similar to algorithms, the optimal depth of a deep architecture may be different for different input instances. In this paper, we tackle this varying depth problem using a steerable architecture. We show that the learned deep model along with the stopping policy improves the performances on a diverse set of tasks.
  arXiv  Detail & Related papers  (2020-06-09T07:22:01Z)
• Deep Unfolding Network for Image Super-Resolution [159.50726840791697]
  This paper proposes an end-to-end trainable unfolding network which leverages both learning-based methods and model-based methods. The proposed network inherits the flexibility of model-based methods to super-resolve blurry, noisy images for different scale factors via a single model.
  arXiv  Detail & Related papers  (2020-03-23T17:55:42Z)

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.