{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T01:36:22Z","timestamp":1781487382514,"version":"3.54.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T00:00:00Z","timestamp":1679875200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T00:00:00Z","timestamp":1679875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004769","name":"Universit\u00e0 degli Studi di Pavia","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004769","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper introduces a computational method for generating metric Travelling Salesman Problem (TSP) instances having a large integrality gap. The method is based on the solution of an integer programming problem, called IH-OPT, that takes as input a fractional solution of the Subtour Elimination Problem (SEP) on a TSP instance and computes a TSP instance having an integrality gap larger than or equal to the integrality gap of the first instance. The decision variables of IH-OPT are the entries of the TSP cost matrix, and the constraints are defined by the intersection of the metric cone with an exponential number of inequalities, one for each possible TSP tour. Given the very large number of constraints, we have implemented a branch-and-cut algorithm for solving IH-OPT. Then, by sampling cost vectors over the metric polytope and by solving the corresponding SEP, we can generate random fractional vertices of the SEP polytope. If we solve the IH-OPT problem for every sampled vertex using our branch-and-cut algorithm, we can select the generated TSP instance (i.e., cost vector), yielding the longest runtime for Concorde, the state-of-the-art TSP solver. Our computational results show that our method is very effective in producing challenging instances. As a by-product, we release the , a library of 41 small metric TSP instances which have a large integrality gap and are challenging in terms of runtime for Concorde.<\/jats:p>","DOI":"10.1007\/s12532-023-00235-7","type":"journal-article","created":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T16:04:42Z","timestamp":1679933082000},"page":"389-416","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["On the generation of metric TSP instances with a large integrality gap by branch-and-cut"],"prefix":"10.1007","volume":"15","author":[{"given":"Eleonora","family":"Vercesi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefano","family":"Gualandi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca Maria","family":"Gambardella","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,3,27]]},"reference":[{"key":"235_CR1","doi-asserted-by":"crossref","unstructured":"Applegate, D., Bixby, R., Cook, W., Chv\u00e1tal, V.: On the solution of traveling salesman problems (1998)","DOI":"10.4171\/dms\/1-3\/62"},{"key":"235_CR2","unstructured":"Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The traveling salesman problem: a computational study. Princeton university press (2006)"},{"issue":"4","key":"235_CR3","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1287\/moor.1080.0337","volume":"33","author":"G Benoit","year":"2008","unstructured":"Benoit, G., Boyd, S.: Finding the exact integrality gap for small traveling salesman problems. Math. Oper. Res. 33(4), 921\u2013931 (2008)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"235_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M Bern","year":"1989","unstructured":"Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32(4), 171\u2013176 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"235_CR5","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1145\/1008731.1008733","volume":"51","author":"D Bertsimas","year":"2004","unstructured":"Bertsimas, D., Vempala, S.: Solving convex programs by random walks. J. ACM (JACM) 51(4), 540\u2013556 (2004)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"235_CR6","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.disopt.2011.05.002","volume":"8","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Carr, R.: Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discret. Optim. 8(4), 525\u2013539 (2011)","journal-title":"Discret. Optim."},{"key":"235_CR7","first-page":"33","volume":"23","author":"S Boyd","year":"2010","unstructured":"Boyd, S., Elliott-Magwood, P.: Structure of the extreme points of the subtour elimination polytope of the STSP (combinatorial optimization and discrete algorithms). RIMS Kokyuroku Bessatsu 23, 33\u201347 (2010)","journal-title":"RIMS Kokyuroku Bessatsu"},{"key":"235_CR8","doi-asserted-by":"crossref","unstructured":"Boyd, S., Sitters, R., van\u00a0der Ster, S., Stougie, L.: TSP on cubic and subcubic graphs. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 65\u201377. Springer (2011)","DOI":"10.1007\/978-3-642-20807-2_6"},{"issue":"4","key":"235_CR9","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. J. Oper. Res. Soc. Am. 2(4), 393\u2013410 (1954)","journal-title":"J. Oper. Res. Soc. Am."},{"issue":"3","key":"235_CR10","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0020-0190(94)00071-9","volume":"51","author":"VG Deineko","year":"1994","unstructured":"Deineko, V.G., Van Dal, R., Rote, G.: The convex-hull-and-line traveling salesman problem: a solvable case. Inf. Process. Lett. 51(3), 141\u2013148 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"235_CR11","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1002\/net.3230240103","volume":"24","author":"M Fischetti","year":"1994","unstructured":"Fischetti, M., Hamacher, H.W., J\u00f8rnsten, K., Maffioli, F.: Weighted k-cardinality trees: complexity and polyhedral structure. Networks 24(1), 11\u201321 (1994)","journal-title":"Networks"},{"issue":"1","key":"235_CR12","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s12532-015-0096-0","volume":"8","author":"M Fischetti","year":"2016","unstructured":"Fischetti, M., Lodi, A., Monaci, M., Salvagnin, D., Tramontani, A.: Improving branch-and-cut performance by random sampling. Math. Program. Comput. 8(1), 113\u2013132 (2016)","journal-title":"Math. Program. Comput."},{"key":"235_CR13","doi-asserted-by":"publisher","unstructured":"Font-Clos, F.: Fontclos\/hitandrun: initial release (2021). https:\/\/doi.org\/10.5281\/zenodo.4906246","DOI":"10.5281\/zenodo.4906246"},{"issue":"2","key":"235_CR14","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e0sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"issue":"1","key":"235_CR15","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01589097","volume":"45","author":"M Gr\u00f6tschel","year":"1989","unstructured":"Gr\u00f6tschel, M., Wakabayashi, Y.: A cutting plane algorithm for a clustering problem. Math. Program. 45(1), 59\u201396 (1989)","journal-title":"Math. Program."},{"issue":"1","key":"235_CR16","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.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106\u2013130 (2000)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"235_CR17","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s12532-009-0004-6","volume":"1","author":"K Helsgaun","year":"2009","unstructured":"Helsgaun, K.: General k-opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput. 1(2), 119\u2013163 (2009)","journal-title":"Math. Program. Comput."},{"issue":"8","key":"235_CR18","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.orl.2014.08.009","volume":"42","author":"S Hougardy","year":"2014","unstructured":"Hougardy, S.: On the integrality ratio of the subtour LP for Euclidean TSP. Oper. Res. Lett. 42(8), 495\u2013499 (2014). https:\/\/doi.org\/10.1016\/j.orl.2014.08.009","journal-title":"Oper. Res. Lett."},{"key":"235_CR19","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s12532-020-00184-5","volume":"13","author":"S Hougardy","year":"2020","unstructured":"Hougardy, S., Zhong, X.: Hard to solve instances of the Euclidean traveling salesman problem. Math. Program. Comput. 13, 51\u201374 (2020)","journal-title":"Math. Program. Comput."},{"key":"235_CR20","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: The Traveling Salesman Problem and Its Variations, pp. 369\u2013443. Springer (2007)","DOI":"10.1007\/0-306-48213-4_9"},{"issue":"1\u20133","key":"235_CR21","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0012-365X(94)00091-V","volume":"151","author":"M Laurent","year":"1996","unstructured":"Laurent, M.: Graphic vertices of the metric polytope. Discret. Math. 151(1\u20133), 131\u2013153 (1996)","journal-title":"Discret. Math."},{"issue":"2","key":"235_CR22","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, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498\u2013516 (1973)","journal-title":"Oper. Res."},{"key":"235_CR23","doi-asserted-by":"crossref","unstructured":"Lodi, A., Tramontani, A.: Performance variability in mixed-integer programming. In: Theory Driven by Influential Applications, pp. 1\u201312. INFORMS (2013)","DOI":"10.1287\/educ.2013.0112"},{"issue":"3","key":"235_CR24","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s101070050099","volume":"86","author":"L Lov\u00e1sz","year":"1999","unstructured":"Lov\u00e1sz, L.: Math. Program. 86(3), 443\u2013461 (1999)","journal-title":"Math. Program."},{"issue":"4","key":"235_CR25","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM (JACM) 7(4), 326\u2013329 (1960)","journal-title":"J. ACM (JACM)"},{"key":"235_CR26","first-page":"65","volume":"1","author":"JE Mitchell","year":"2002","unstructured":"Mitchell, J.E.: Branch-and-cut algorithms for combinatorial optimization problems. Handb. Appl. Optim. 1, 65\u201377 (2002)","journal-title":"Handb. Appl. Optim."},{"key":"235_CR27","doi-asserted-by":"crossref","unstructured":"Orman, A., Williams, H.P.: A survey of different integer programming formulations of the travelling salesman problem. In: Optimisation, Econometric and Financial Analysis, pp. 91\u2013104. Springer (2007)","DOI":"10.1007\/3-540-36626-1_5"},{"issue":"1","key":"235_CR28","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01580861","volume":"47","author":"M Padberg","year":"1990","unstructured":"Padberg, M., Rinaldi, G.: Facet identification for the symmetric traveling salesman polytope. Math. Program. 47(1), 219\u2013257 (1990)","journal-title":"Math. Program."},{"issue":"1","key":"235_CR29","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M Padberg","year":"1991","unstructured":"Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1), 60\u2013100 (1991)","journal-title":"SIAM Rev."},{"issue":"4","key":"235_CR30","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt, G.: TSPLIB - A Traveling Salesman Problem Library. INFORMS J. Comput. 3(4), 376\u2013384 (1991). https:\/\/doi.org\/10.1287\/ijoc.3.4.376","journal-title":"INFORMS J. Comput."},{"issue":"4","key":"235_CR31","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt, G.: TSPLIB-A traveling salesman problem library. ORSA J. Comput. 3(4), 376\u2013384 (1991)","journal-title":"ORSA J. Comput."},{"issue":"2","key":"235_CR32","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF01100688","volume":"5","author":"HE Romeijn","year":"1994","unstructured":"Romeijn, H.E., Smith, R.L.: Simulated annealing for constrained global optimization. J. Glob. Optim. 5(2), 101\u2013126 (1994)","journal-title":"J. Glob. Optim."},{"issue":"2","key":"235_CR33","first-page":"68","volume":"38","author":"JH Rubinstein","year":"2001","unstructured":"Rubinstein, J.H., Thomas, D.A., Wormald, N.C.: A polynomial algorithm for a constrained traveling salesman problem. Netw. Int. J. 38(2), 68\u201375 (2001)","journal-title":"Netw. Int. J."},{"issue":"6","key":"235_CR34","doi-asserted-by":"publisher","first-page":"1296","DOI":"10.1287\/opre.32.6.1296","volume":"32","author":"RL Smith","year":"1984","unstructured":"Smith, R.L.: Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32(6), 1296\u20131308 (1984)","journal-title":"Oper. Res."},{"key":"235_CR35","unstructured":"Williamson, D.P.: Analysis of the Held-Karp heuristic for the traveling salesman problem. Master\u2019s thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science (1990)"},{"key":"235_CR36","doi-asserted-by":"crossref","unstructured":"Wolsey, L.A.: Heuristic analysis, linear programming and branch and bound. In: Combinatorial Optimization II, pp. 121\u2013134. Springer (1980)","DOI":"10.1007\/BFb0120913"},{"key":"235_CR37","doi-asserted-by":"crossref","unstructured":"Zabinsky, Z.B., Smith, R.L., Gass, S., Fu, M.: Hit-and-run methods. Encycl. Oper. Res. Manage. Sci. 721\u2013729 (2013)","DOI":"10.1007\/978-1-4419-1153-7_1145"},{"key":"235_CR38","unstructured":"Zhong, X.: Lower bounds on the integraliy ratio of the subtour LP for the traveling salesman problem. (2021) arXiv preprint arXiv:2102.04765"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-023-00235-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-023-00235-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-023-00235-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T12:35:01Z","timestamp":1684931701000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-023-00235-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,27]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["235"],"URL":"https:\/\/doi.org\/10.1007\/s12532-023-00235-7","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,27]]},"assertion":[{"value":"2 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}