{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,12]],"date-time":"2026-04-12T12:14:40Z","timestamp":1775996080118,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T00:00:00Z","timestamp":1656460800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T00:00:00Z","timestamp":1656460800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000006","name":"office of naval research","doi-asserted-by":"crossref","award":["N00014-18-1-2099"],"award-info":[{"award-number":["N00014-18-1-2099"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000006","name":"office of naval research","doi-asserted-by":"crossref","award":["N00014-21-1-2243"],"award-info":[{"award-number":["N00014-21-1-2243"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"DOI":"10.1007\/s10107-022-01849-w","type":"journal-article","created":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T15:09:09Z","timestamp":1656515349000},"page":"877-902","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A new integer programming formulation of the graphical traveling salesman problem"],"prefix":"10.1007","volume":"197","author":[{"given":"Robert","family":"Carr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6128-712X","authenticated-orcid":false,"given":"Neil","family":"Simonetti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,29]]},"reference":[{"key":"1849_CR1","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0167-6377(01)00106-7","volume":"30","author":"RD Carr","year":"2002","unstructured":"Carr, R.D., Lancia, G.: Compact vs. exponential-size LP relaxations. Operations Research Letters 30, 57\u201366 (2002)","journal-title":"Operations Research Letters"},{"key":"1849_CR2","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s10107-004-0506-y","volume":"100","author":"RD Carr","year":"2004","unstructured":"Carr, R.D., Vempala, S.: On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems. Mathematical Programming 100, 569\u2013587 (2004)","journal-title":"Mathematical Programming"},{"key":"1849_CR3","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/PL00011426","volume":"90","author":"A Corber\u00e1n","year":"2001","unstructured":"Corber\u00e1n, A., Letchford, A.N., Sanchis, J.M.: A cutting plane algorithm for the general routing problem. Mathematical Programming 90, 291\u2013316 (2001)","journal-title":"Mathematical Programming"},{"key":"1849_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01582008","volume":"33","author":"G Cornu\u00e9jols","year":"1985","unstructured":"Cornu\u00e9jols, G., Fonlupt, J., Naddef, D.: The traveling salesman problem on a graph and some related integer polyhedra. Mathematical Programming 33, 1\u201327 (1985)","journal-title":"Mathematical Programming"},{"key":"1849_CR5","first-page":"393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling salesman problem. Operations Research 2, 393\u2013410 (1954)","journal-title":"Operations Research"},{"key":"1849_CR6","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Mathematical Programming 5, 88\u2013124 (1973)","journal-title":"Mathematical Programming"},{"key":"1849_CR7","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., Kakimura, N., Rothvo\u00df, T., Sanit\u00e0, L.: Set covering with ordered replacement: Additive and multiplicative gaps. In International Conference on Integer Programming and Combinatorial Optimization, Springer, Berlin, Heidelberg. 170-182 (2011)","DOI":"10.1007\/978-3-642-20807-2_14"},{"issue":"3","key":"1849_CR8","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0377-2217(85)90151-1","volume":"21","author":"B Fleischmann","year":"1985","unstructured":"Fleischmann, B.: A cutting plane procedure for the traveling salesman problem on road networks. European Journal of Operational Research 21(3), 307\u2013317 (1985)","journal-title":"European Journal of Operational Research"},{"key":"1849_CR9","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, E.: The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing 5, 704\u2013714 (1976)","journal-title":"SIAM Journal on Computing"},{"key":"1849_CR10","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/BF01585563","volume":"69","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Mathematical Programming 69, 335\u2013349 (1995)","journal-title":"Mathematical Programming"},{"key":"1849_CR11","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01582116","volume":"16","author":"M Gr\u00f6tschel","year":"1979","unstructured":"Gr\u00f6tschel, M., Padberg, M.W.: On the symmetric travelling salesman problem I: inequalities. Mathematical Programming 16, 265\u2013280 (1979)","journal-title":"Mathematical Programming"},{"key":"1849_CR12","doi-asserted-by":"crossref","unstructured":"Guten, G., Punnen, A.P. (eds.): The traveling salesman problem and its variations. Springer, New York (2007)","DOI":"10.1007\/b101971"},{"key":"1849_CR13","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1287\/opre.10.5.647","volume":"10","author":"WW Hardgrave","year":"1962","unstructured":"Hardgrave, W.W., Nemhauser, G.L.: On the relation between the traveling-salesman and the longest-path problems. Operations Research 10, 647\u2013657 (1962)","journal-title":"Operations Research"},{"key":"1849_CR14","unstructured":"Junger, M., Reinelt, G., Rinaldi, G.: The traveling salesman problem. In: Handbooks in Operations Research and Management Science; Volume 7; Network Models (M.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser, eds.), Elsevier, Amsterdam (1995)"},{"key":"1849_CR15","unstructured":"Kolodyazhnyy, S.: Dijkstra Algorithm for Shortest Path, github.com\/SergKolo\/MSUD-CS2050-SPRING-2016\/blob\/master\/input_for_dijkstra.txt (web) Accessed Jun (2018)"},{"key":"1849_CR16","doi-asserted-by":"crossref","unstructured":"Lancia G., Serafini, P.: The Parity Polytope. In: Compact Extended Linear Programming Models. EURO Advanced Tutorials on Operational Research. Springer, Cham (2018)","DOI":"10.1007\/978-3-319-63976-5"},{"issue":"C","key":"1849_CR17","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume":"4","author":"EL Lawler","year":"1993","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science 4(C), 445\u2013522 (1993)","journal-title":"Handbooks in Operations Research and Management Science"},{"key":"1849_CR18","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.ejor.2013.01.044","volume":"228","author":"AN Letchford","year":"2013","unstructured":"Letchford, A.N., Nasiri, S.D., Theis, D.O.: Compact formulations of the steiner TSP and related problems. European Journal of Operations Research 228, 83\u201392 (2013)","journal-title":"European Journal of Operations Research"},{"key":"1849_CR19","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(91)90028-N","volume":"10","author":"RK Martin","year":"1991","unstructured":"Martin, R.K.: Using separation algorithms to generate mixed integer model reformulations. Operations Research Letters 10, 119\u2013128 (1991)","journal-title":"Operations Research Letters"},{"key":"1849_CR20","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1051\/ro\/1981150302331","volume":"15","author":"P Miliotis","year":"1986","unstructured":"Miliotis, P., Laporte, G., Norbert, Y.: Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph. RAIRO-Operations Research 15, 233\u2013239 (1986)","journal-title":"RAIRO-Operations Research"},{"key":"1849_CR21","unstructured":"Naddef, D.: Personal Communication"},{"key":"1849_CR22","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"CStJA Nash-Williams","year":"1961","unstructured":"Nash-Williams, CSt.J.A.: Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society 36, 445\u2013450 (1961)","journal-title":"Journal of the London Mathematical Society"},{"key":"1849_CR23","first-page":"307","volume-title":"The Traveling Salesman Problem","author":"MW Padberg","year":"1985","unstructured":"Padberg, M.W., Gr\u00f6tschel, M.: Polyhedral computations. In: Lawler, E., Lenstra, J., Rinnooy-Kan, A., Shmoys, D. (eds.) The Traveling Salesman Problem, pp. 307\u2013360. Wiley, Chichester (1985)"},{"issue":"3","key":"1849_CR24","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1287\/opre.31.3.507","volume":"31","author":"HD Ratliff","year":"1983","unstructured":"Ratliff, H.D., Rosenthal, A.: Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem. Operations Research 31(3), 507\u2013521 (1983)","journal-title":"Operations Research"},{"key":"1849_CR25","unstructured":"Schrijver, A.: Combinatorial optimization - Polyhedra and efficiency. Springer (2003)"},{"key":"1849_CR26","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1112\/jlms\/s1-36.1.221","volume":"36","author":"WT Tutte","year":"1961","unstructured":"Tutte, W.T.: On the problem of decomposing a graph into $$n$$ connected factors. Journal of the London Mathematical Society 36, 221\u2013230 (1961)","journal-title":"Journal of the London Mathematical Society"},{"key":"1849_CR27","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/0377-2217(86)90217-1","volume":"23","author":"A Volgenant","year":"1986","unstructured":"Volgenant, A., Jonker, R., Kindervater, G.A.O.: A note on finding a shortest complete cycle in an undirected graph. European Journal of Operational Research 23, 82\u201385 (1986)","journal-title":"European Journal of Operational Research"},{"key":"1849_CR28","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences 43, 441\u2013466 (1991)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01849-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01849-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01849-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:21:36Z","timestamp":1675704096000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01849-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,29]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1849"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01849-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,29]]},"assertion":[{"value":"14 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}