Generalization of machine learning for problem reduction: a case study on travelling salesman problems
- PDF / 1,996,338 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 174 Views
Generalization of machine learning for problem reduction: a case study on travelling salesman problems Yuan Sun1 · Andreas Ernst2 · Xiaodong Li1 · Jake Weiner1 Received: 31 March 2020 / Accepted: 17 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
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 * Yuan Sun [email protected] Andreas Ernst [email protected] Xiaodong Li [email protected] Jake Weiner [email protected] 1
School of Science, RMIT University, Melbourne, VIC 3001, Australia
2
School of Mathematical Sciences, Monash University, Clayton, VIC 3800, Australia
13
Vol.:(0123456789)
Y. Sun et al.
1 Introduction In the big data era, we are often confronted with optimization problems with thousands or even millions of decision variables, e.g. social network analysis (Balasundaram et al. 2011; Gao et al. 2018). The large problem size poses significant challenges to existing solution algorithms, especially to generic Mixed Integer Programming (MIP) solvers such as CPLEX, which typically has difficulty in optimally solving or even finding good solutions for such large-scale optimization problems in a reasonable computational time. Moreover, in many practical applications, e.g. trip planning (Friggstad et al. 2018), we need to provide a high-quality solution to users within a few seconds. This is hard to achieve especially when the problem size is very large, which necessitates the use of an effective problem reduction technique that can significantly prune the search space but still capture an optimal (or ne
Data Loading...
