Generalization of machine learning for problem reduction: a case study on travelling salesman problems
From MaRDI portal
Publication:2241908
DOI10.1007/S00291-020-00604-XzbMATH Open1480.90215arXiv2005.05847OpenAlexW3102895825MaRDI QIDQ2241908FDOQ2241908
Jake Weiner, Yu-An Sun, Xiaodong Li, Andreas T. Ernst
Publication date: 9 November 2021
Published in: OR Spectrum (Search for Journal in Brave)
Abstract: Combinatorial optimization plays an important role in real-world problem solving. In the big data era, the dimensionality of a combinatorial optimization problem is usually very large, which poses a significant challenge to existing solution methods. In this paper, we examine the generalization capability of a machine learning model for problem reduction on the classic travelling salesman problems (TSP). We demonstrate that our method can greedily remove decision variables from an optimization problem that are predicted not to be part of an optimal solution. More specifically, we investigate our model's capability to generalize on test instances that have not been seen during the training phase. We consider three scenarios where training and test instances are different in terms of: 1) problem characteristics; 2) problem sizes; and 3) problem types. Our experiments show that this machine learning based technique can generalize reasonably well over a wide range of TSP test instances with different characteristics or sizes. While the accuracy of predicting unused variables naturally deteriorates as a test instance is further away from the training set, we observe that even when tested on a different TSP problem variant, the machine learning model still makes useful predictions about which variables can be eliminated without significantly impacting solution quality.
Full work available at URL: https://arxiv.org/abs/2005.05847
machine learningcombinatorial optimizationgeneralization errortravelling salesman problemproblem reduction
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An effective implementation of the Lin-Kernighan traveling salesman heuristic
- TSPLIB—A Traveling Salesman Problem Library
- Support-vector networks
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- A review on algorithms for maximum clique problems
- Chained Lin-Kernighan for large traveling salesman problems
- On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
- Discovering the suitability of optimisation algorithms by learning from evolved instances
- Transforming asymmetric into symmetric traveling salesman problems
- Construct, Merge, Solve \& Adapt A new general algorithm for combinatorial optimization
- Machine learning for combinatorial optimization: a methodological tour d'horizon
- Nonoptimal Edges for the Symmetric Traveling Salesman Problem
- Learning heuristics for the TSP by policy gradient
- Edge Elimination in TSP Instances
Cited In (5)
- Boosting ant colony optimization via solution prediction and machine learning
- One-shot learning for MIPs with SOS1 constraints
- Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem
- Deep policy dynamic programming for vehicle routing problems
- Learning to sparsify travelling salesman problem instances
Uses Software
This page was built for publication: Generalization of machine learning for problem reduction: a case study on travelling salesman problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2241908)
