{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T08:01:06Z","timestamp":1786089666471,"version":"3.56.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T00:00:00Z","timestamp":1598918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T00:00:00Z","timestamp":1598918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Australian Research Council Discovery Project","award":["DP180101170"],"award-info":[{"award-number":["DP180101170"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["OR Spectrum"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s00291-020-00604-x","type":"journal-article","created":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T18:15:24Z","timestamp":1598984124000},"page":"607-633","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":41,"title":["Generalization of machine learning for problem reduction: a case study on travelling salesman problems"],"prefix":"10.1007","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2911-0070","authenticated-orcid":false,"given":"Yuan","family":"Sun","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Ernst","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaodong","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jake","family":"Weiner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,9,1]]},"reference":[{"issue":"1","key":"604_CR1","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1287\/ijoc.15.1.82.15157","volume":"15","author":"D Applegate","year":"2003","unstructured":"Applegate D, Cook W, Rohe A (2003) Chained Lin\u2013Kernighan for large traveling salesman problems. INFORMS J Comput 15(1):82\u201392","journal-title":"INFORMS J Comput"},{"key":"604_CR2","unstructured":"Applegate D, Bixby R, Chvatal V, Cook W (2006a) Concorde TSP solver"},{"key":"604_CR3","volume-title":"The traveling salesman problem: a computational study","author":"DL Applegate","year":"2006","unstructured":"Applegate DL, Bixby RE, Chvatal V, Cook WJ (2006b) The traveling salesman problem: a computational study. Princeton University Press, Princeton"},{"issue":"1","key":"604_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/opre.1100.0851","volume":"59","author":"B Balasundaram","year":"2011","unstructured":"Balasundaram B, Butenko S, Hicks IV (2011) Clique relaxations in social network analysis: the maximum k-plex problem. Oper Res 59(1):133\u2013142","journal-title":"Oper Res"},{"key":"604_CR5","unstructured":"Bello I, Pham H, Le QV, Norouzi M, Bengio S (2016) Neural combinatorial optimization with reinforcement learning. arXiv preprint. arXiv:1611.09940"},{"key":"604_CR6","unstructured":"Bengio Y, Lodi A, Prouvost A (2018) Machine learning for combinatorial optimization: a methodological tour d\u2019horizon. arXiv preprint. arXiv:1811.06128"},{"key":"604_CR7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.cor.2015.10.014","volume":"68","author":"C Blum","year":"2016","unstructured":"Blum C, Pinacho P, L\u00f3pez-Ib\u00e1\u00f1ez M, Lozano JA (2016) Construct, merge, solve & adapt a new general algorithm for combinatorial optimization. Comput Oper Res 68:75\u201388","journal-title":"Comput Oper Res"},{"key":"604_CR8","doi-asserted-by":"crossref","unstructured":"Boser BE, Guyon IM, Vapnik VN (1992) A training algorithm for optimal margin classifiers. In: Proceedings of the fifth annual workshop on computational learning theory. ACM, pp 144\u2013152","DOI":"10.1145\/130385.130401"},{"key":"604_CR9","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/1961189.1961199","volume":"2","author":"C-C Chang","year":"2011","unstructured":"Chang C-C, Lin C-J (2011) LIBSVM: a library for support vector machines. ACM Trans Intell Syst Technol 2:27:1\u201327:27","journal-title":"ACM Trans Intell Syst Technol"},{"key":"604_CR10","unstructured":"Chen X, Tian Y (2019) Learning to perform local rewriting for combinatorial optimization. Adv Neural Inf Process Syst 6278\u20136289"},{"issue":"3","key":"604_CR11","first-page":"273","volume":"20","author":"C Cortes","year":"1995","unstructured":"Cortes C, Vapnik V (1995) Support-vector networks. Mach Learn 20(3):273\u2013297","journal-title":"Mach Learn"},{"key":"604_CR12","doi-asserted-by":"crossref","unstructured":"Deudon M, Cournut P, Lacoste A, Adulyasak Y, Rousseau L-M (2018) Learning heuristics for the TSP by policy gradient. In: International conference on the integration of constraint programming, artificial intelligence, and operations research. Springer, pp 170\u2013181","DOI":"10.1007\/978-3-319-93031-2_12"},{"key":"604_CR13","unstructured":"Ding J-Y, Zhang C, Shen L, Li S, Wang B, Xu Y, Song L (2019) Accelerating primal solution findings for mixed integer programs based on solution prediction. arXiv preprint. arXiv:1906.09575"},{"key":"604_CR14","doi-asserted-by":"crossref","unstructured":"Dong C, J\u00e4ger G, Richter D, Molitor P (2009) Effective tour searching for tsp by contraction of pseudo backbone edges. In: International conference on algorithmic applications in management. Springer, pp 175\u2013187","DOI":"10.1007\/978-3-642-02158-9_16"},{"issue":"Dec","key":"604_CR15","first-page":"1889","volume":"6","author":"R-E Fan","year":"2005","unstructured":"Fan R-E, Chen P-H, Lin C-J (2005) Working set selection using second order information for training support vector machines. J Mach Learn Res 6(Dec):1889\u20131918","journal-title":"J Mach Learn Res"},{"issue":"Aug","key":"604_CR16","first-page":"1871","volume":"9","author":"R-E Fan","year":"2008","unstructured":"Fan R-E, Chang K-W, Hsieh C-J, Wang X-R, Lin C-J (2008) LIBLINEAR: a library for large linear classification. J Mach Learn Res 9(Aug):1871\u20131874","journal-title":"J Mach Learn Res"},{"key":"604_CR17","doi-asserted-by":"crossref","unstructured":"Fischer T, Merz P (2007) Reducing the size of traveling salesman problem instances by fixing edges. In: European conference on evolutionary computation in combinatorial optimization. Springer, pp 72\u201383","DOI":"10.1007\/978-3-540-71615-0_7"},{"key":"604_CR18","doi-asserted-by":"crossref","unstructured":"Friggstad Z, Gollapudi S, Kollias K, Sarlos T, Swamy C, Tomkins A (2018) Orienteering algorithms for generating travel itineraries. In: Proceedings of the eleventh ACM international conference on web search and data mining. ACM, pp 180\u2013188","DOI":"10.1145\/3159652.3159697"},{"key":"604_CR19","doi-asserted-by":"crossref","unstructured":"Gao J, Chen J, Yin M, Chen R, Wang Y (2018) An exact algorithm for maximum k-plexes in massive graphs. IJCAI 1449\u20131455","DOI":"10.24963\/ijcai.2018\/201"},{"key":"604_CR20","unstructured":"Grassia M, Lauri J, Dutta S, Ajwani D (2019) Learning multi-stage sparsification for maximum clique enumeration. arXiv preprint. arXiv:1910.00517"},{"key":"604_CR21","unstructured":"He H, Daume H III, Eisner JM (2014) Learning to search in branch and bound algorithms. Adv Neural Inf Process Syst 3293\u20133301"},{"issue":"1","key":"604_CR22","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","volume":"126","author":"K Helsgaun","year":"2000","unstructured":"Helsgaun K (2000) An effective implementation of the Lin\u2013Kernighan traveling salesman heuristic. Eur J Oper Res 126(1):106\u2013130","journal-title":"Eur J Oper Res"},{"key":"604_CR23","doi-asserted-by":"crossref","unstructured":"Hougardy S, Schroeder RT (2014) Edge elimination in tsp instances. In: International workshop on graph-theoretic concepts in computer science. Springer, pp 275\u2013286","DOI":"10.1007\/978-3-319-12340-0_23"},{"issue":"1","key":"604_CR24","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/s10732-013-9233-y","volume":"20","author":"G J\u00e4ger","year":"2014","unstructured":"J\u00e4ger G, Dong C, Goldengorin B, Molitor P, Richter D (2014) A backbone based TSP heuristic for large instances. J Heuristics 20(1):107\u2013124","journal-title":"J Heuristics"},{"issue":"1","key":"604_CR25","first-page":"215","volume":"1","author":"DS Johnson","year":"1997","unstructured":"Johnson DS, McGeoch LA (1997) The traveling salesman problem: a case study in local optimization. Local Search Comb Optim 1(1):215\u2013310","journal-title":"Local Search Comb Optim"},{"issue":"4","key":"604_CR26","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0167-6377(83)90048-2","volume":"2","author":"R Jonker","year":"1983","unstructured":"Jonker R, Volgenant T (1983) Transforming asymmetric into symmetric traveling salesman problems. Oper Res Lett 2(4):161\u2013163","journal-title":"Oper Res Lett"},{"issue":"4","key":"604_CR27","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1287\/opre.32.4.837","volume":"32","author":"R Jonker","year":"1984","unstructured":"Jonker R, Volgenant T (1984) Nonoptimal edges for the symmetric traveling salesman problem. Oper Res 32(4):837\u2013846","journal-title":"Oper Res"},{"key":"604_CR28","unstructured":"Khalil E, Dai H, Zhang Y, Dilkina B, Song L (2017) Learning combinatorial optimization algorithms over graphs. Adv Neural Inf Process Syst 6348\u20136358"},{"key":"604_CR29","unstructured":"Kilby P, Slaney J, Walsh T et al (2005) The backbone of the travelling salesperson. IJCAI 175\u2013180"},{"key":"604_CR30","unstructured":"Kool W, van Hoof H, Welling M (2019) Attention, learn to solve routing problems!. International conference on learning representations"},{"key":"604_CR31","doi-asserted-by":"crossref","unstructured":"Lauri J, Dutta S (2019) Fine-grained search space classification for hard enumeration variants of subset problems. In: Proceedings of the thirty-third AAAI conference on artificial intelligence. AAAI, pp 2314\u20132321","DOI":"10.1609\/aaai.v33i01.33012314"},{"key":"604_CR32","unstructured":"Li Z, Chen Q, Koltun V (2018) Combinatorial optimization with graph convolutional networks and guided tree search. Adv Neural Inf Process Syst 539\u2013548"},{"issue":"2","key":"604_CR33","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Lin","year":"1973","unstructured":"Lin S, Kernighan BW (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper Res 21(2):498\u2013516","journal-title":"Oper Res"},{"issue":"Jun","key":"604_CR34","first-page":"627","volume":"9","author":"C-J Lin","year":"2008","unstructured":"Lin C-J, Weng RC, Keerthi SS (2008) Trust region Newton method for logistic regression. J Mach Learn Res 9(Jun):627\u2013650","journal-title":"J Mach Learn Res"},{"issue":"4","key":"604_CR35","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt G (1991) Tsplib\u2014a traveling salesman problem library. ORSA J Comput 3(4):376\u2013384","journal-title":"ORSA J Comput"},{"issue":"4","key":"604_CR36","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1287\/opre.50.4.656.2865","volume":"50","author":"HD Sherali","year":"2002","unstructured":"Sherali HD, Driscoll PJ (2002) On tightening the relaxations of Miller\u2013Tucker\u2013Zemlin formulations for asymmetric traveling salesman problems. Oper Res 50(4):656\u2013669","journal-title":"Oper Res"},{"issue":"2","key":"604_CR37","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10472-011-9230-5","volume":"61","author":"K Smith-Miles","year":"2011","unstructured":"Smith-Miles K, van Hemert J (2011) Discovering the suitability of optimisation algorithms by learning from evolved instances. Ann Math Artif Intell 61(2):87\u2013104","journal-title":"Ann Math Artif Intell"},{"key":"604_CR38","unstructured":"Sun Y, Li X, Ernst A (2019) Using statistical measures and machine learning for graph reduction to solve maximum weight clique problems. IEEE Trans Pattern Anal Mach Intell"},{"key":"604_CR39","unstructured":"Vinyals O, Fortunato M, Jaitly N (2015) Pointer networks. Adv Neural Inf Process Syst 2692\u20132700"},{"issue":"3","key":"604_CR40","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.ejor.2014.09.064","volume":"242","author":"Q Wu","year":"2015","unstructured":"Wu Q, Hao J-K (2015) A review on algorithms for maximum clique problems. Eur J Oper Res 242(3):693\u2013709","journal-title":"Eur J Oper Res"},{"key":"604_CR41","unstructured":"Wu Y, Song W, Cao Z, Zhang J, Lim A (2019) Learning improvement heuristics for solving the travelling salesman problem. arXiv preprint. arXiv:1912.05784"}],"container-title":["OR Spectrum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-020-00604-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00291-020-00604-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-020-00604-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T01:49:15Z","timestamp":1630460955000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00291-020-00604-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,1]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["604"],"URL":"https:\/\/doi.org\/10.1007\/s00291-020-00604-x","relation":{},"ISSN":["0171-6468","1436-6304"],"issn-type":[{"value":"0171-6468","type":"print"},{"value":"1436-6304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,1]]},"assertion":[{"value":"31 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}