Generalization of machine learning for problem reduction: a case study on travelling salesman problems

Yuan Sun (), Andreas Ernst (), Xiaodong Li () and Jake Weiner ()
Additional contact information
Yuan Sun: School of Science, RMIT University
Andreas Ernst: Monash University
Xiaodong Li: School of Science, RMIT University
Jake Weiner: School of Science, RMIT University

OR Spectrum: Quantitative Approaches in Management, 2021, vol. 43, issue 3, No 2, 607-633

Abstract: 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. Since 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.

Keywords: Combinatorial optimization; Machine learning; Generalization error; Problem reduction; Travelling salesman problem (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-020-00604-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:43:y:2021:i:3:d:10.1007_s00291-020-00604-x

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-020-00604-x

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().