{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T23:30:46Z","timestamp":1620775846977},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-47867-1_8","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T18:47:17Z","timestamp":1179946037000},"page":"93-108","source":"Crossref","is-referenced-by-count":3,"title":["Polynomial-Time Separation of Simple Comb Inequalities"],"prefix":"10.1007","author":[{"given":"Adam N.","family":"Letchford","sequence":"first","affiliation":[]},{"given":"Andrea","family":"Lodi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,5,21]]},"reference":[{"key":"8_CR1","series-title":"Technical Report","volume-title":"Finding cuts in the TSP (a preliminary report)","author":"D. Applegate","year":"1995","unstructured":"D. Applegate, R.E. Bixby, V. Chv\u00e1tal & W. Cook (1995) Finding cuts in the TSP (a preliminary report). Technical Report 95-05, DIMACS, Rutgers University, New Brunswick, NJ."},{"key":"8_CR2","first-page":"221","volume":"74","author":"A. Caprara","year":"1996","unstructured":"A. Caprara & M. Fischetti (1996) 0,1\/2-Chv\u00e1tal-Gomory cuts. Math. Program. 74, 221\u2013235.","journal-title":"Math. Program"},{"key":"8_CR3","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s101079900107","volume":"87","author":"A. Caprara","year":"2000","unstructured":"A. Caprara, M. Fischetti & A.N. Letchford (2000) On the separation of maximally violated mod-k cuts. Math. Program. 87, 37\u201356.","journal-title":"Math. Program."},{"key":"8_CR4","unstructured":"A. Caprara & A.N. Letchford (2001) On the separation of split cuts and related inequalities. To appear in Math. Program."},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.22.2.257","volume":"22","author":"R. Carr","year":"1997","unstructured":"R. Carr (1997) Separating clique trees and bipartition inequalities having a fixed number of handles and teeth in polynomial time. Math. Oper. Res. 22, 257\u2013265.","journal-title":"Math. Oper. Res."},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01580109","volume":"5","author":"V. Chv\u00e1tal","year":"1973","unstructured":"V. Chv\u00e1tal (1973) Edmonds polytopes and weakly Hamiltonian graphs. Math. Program. 5, 29\u201340.","journal-title":"Math. Program."},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1287\/opre.2.4.393","volume":"2","author":"G.B. Dantzig","year":"1954","unstructured":"G.B. Dantzig, D.R. Fulkerson & S.M. Johnson (1954) Solution of a large-scale traveling salesman problem. Oper. Res. 2, 393\u2013410.","journal-title":"Oper. Res."},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds (1965) Maximum matching and a polyhedron with 0-1 vertices. J. Res. Nat. Bur. Standards 69B, 125\u2013130.","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1287\/moor.24.1.130","volume":"24","author":"L. Fleischer","year":"1999","unstructured":"L. Fleischer & \u00c9. Tardos (1999) Separating maximally violated comb inequalities in planar graphs. Math. Oper. Res. 24, 130\u2013148.","journal-title":"Math. Oper. Res."},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01585700","volume":"53","author":"J. Fonlupt","year":"1992","unstructured":"J. Fonlupt & D. Naddef (1992) The traveling salesman problem in graphs with excluded minors. Math. Program. 53, 147\u2013172.","journal-title":"Math. Program."},{"key":"8_CR11","first-page":"335","volume":"69","author":"M.X. Goemans","year":"1995","unstructured":"M.X. Goemans (1995) Worst-case comparison of valid inequalities for the TSP. Math. Program. 69, 335\u2013349.","journal-title":"Math. Program."},{"key":"8_CR12","first-page":"921","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"A.V. Goldberg & R.E. Tarjan (1988) A new approach to the maximum flow problem. J. of the A.C.M. 35, 921\u2013940.","journal-title":"J. of the A.C.M."},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF02239975","volume":"39","author":"M. Gr\u00f6tschel","year":"1987","unstructured":"M. Gr\u00f6tschel & O. Holland (1987) A cutting plane algorithm for minimum perfect 2-matching. Computing 39, 327\u2013344.","journal-title":"Computing"},{"key":"8_CR14","doi-asserted-by":"publisher","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz & A.J. Schrijver (1988) Geometric Algorithms and Combinatorial Optimization. Wiley: New York.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01582116","volume":"16","author":"M. Gr\u00f6tschel","year":"1979","unstructured":"M. Gr\u00f6tschel & M.W. Padberg (1979) On the symmetric traveling salesman problem I: inequalities. Math. Program. 16, 265\u2013280.","journal-title":"Math. Program."},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01582117","volume":"16","author":"M. Gr\u00f6tschel","year":"1979","unstructured":"M. Gr\u00f6tschel & M.W. Padberg (1979) On the symmetric traveling salesman problem II: lifting theorems and facets. Math. Program. 16, 281\u2013302.","journal-title":"Math. Program."},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/0095-8956(89)90052-X","volume":"46","author":"M. Gr\u00f6tschel","year":"1989","unstructured":"M. Gr\u00f6tschel & K. Truemper (1989) Decomposition and optimization over cycles in binary matroids. J. Comb. Th. (B) 46, 306\u2013337.","journal-title":"J. Comb. Th. (B)"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0020-0190(96)00079-8","volume":"59","author":"M.R. Hensinger","year":"1996","unstructured":"M.R. Hensinger & D.P. Williamson (1996) On the number of small cuts in a graph. Inf. Proc. Lett. 59, 41\u201344.","journal-title":"Inf. Proc. Lett."},{"key":"8_CR19","series-title":"Handbooks in Operations Research and Management Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/S0927-0507(05)80121-5","volume-title":"Network Models","author":"M. J\u00fcnger","year":"1995","unstructured":"M. J\u00fcnger, G. Reinelt, G. Rinaldi (1995) The traveling salesman problem. In M. Ball, T. Magnanti, C. Monma & G. Nemhauser (eds.). Network Models, Handbooks in Operations Research and Management Science, 7, Elsevier Publisher B.V., Amsterdam, 225\u2013330."},{"key":"8_CR20","first-page":"199","volume-title":"Annotated Bibliographies in Combinatorial Optimization","author":"M. J\u00fcnger","year":"1997","unstructured":"M. J\u00fcnger, G. Reinelt & G. Rinaldi (1997) The traveling salesman problem. In M. Dell\u2019Amico, F. Maffioli & S. Martello (eds.) Annotated Bibliographies in Combinatorial Optimization. Chichester, Wiley, 199\u2013221."},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1287\/moor.25.3.443.12213","volume":"25","author":"A.N. Letchford","year":"2000","unstructured":"A.N. Letchford (2000) Separating a superclass of comb inequalities in planar graphs. Math. Oper. Res. 25, 443\u2013454.","journal-title":"Math. Oper. Res."},{"key":"8_CR22","unstructured":"D. Naddef (2001) Polyhedral theory and branch-and-cut algorithms for the symmetric TSP. In G. Gutin & A. Punnen (eds.), The Traveling Salesman Problem and its Variations. Kluwer Academic Publishers, 2002 (to appear)."},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF01586945","volume":"51","author":"D. Naddef","year":"1991","unstructured":"D. Naddef & G. Rinaldi (1991) The symmetric traveling salesman polytope and its graphical relaxation: composition of valid inequalities. Math. Program. 51, 359\u2013400.","journal-title":"Math. Program."},{"key":"8_CR24","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01581259","volume":"58","author":"D. Naddef","year":"1993","unstructured":"D. Naddef & G. Rinaldi (1993) The graphical relaxation: a new framework for the symmetric traveling salesman polytope. Math. Program. 58, 53\u201388.","journal-title":"Math. Program"},{"key":"8_CR25","unstructured":"D. Naddef & S. Thienel (1998) Efficient separation routines for the symmetric traveling salesman problem I: general tools and comb separation. Working paper, LMC-IMAG, Grenoble."},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1137\/S0895480194271323","volume":"10","author":"H. Nagamochi","year":"1997","unstructured":"H. Nagamochi, K. Nishimura and T. Ibaraki (1997) Computing all small cuts in undirected networks. SIAM Disc. Math. 10, 469\u2013481.","journal-title":"SIAM Disc. Math."},{"key":"8_CR27","volume-title":"Integer and Combinatorial Optimization","author":"G.L. Nemhauser","year":"1988","unstructured":"G.L. Nemhauser and L.A. Wolsey (1988) Integer and Combinatorial Optimization. New York: Wiley."},{"key":"8_CR28","volume-title":"The Traveling Salesman Problem","author":"M.W. Padberg","year":"1985","unstructured":"M.W. Padberg & M. Gr\u00f6tschel (1985) Polyhedral computations. In E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan & D.B. Schmoys (Eds.) The Traveling Salesman Problem. John Wiley & Sons, Chichester."},{"key":"8_CR29","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"M.W. Padberg","year":"1982","unstructured":"M.W. Padberg & M.R. Rao (1982) Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7, 67\u201380.","journal-title":"Math. Oper. Res."},{"key":"8_CR30","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01580861","volume":"47","author":"M.W. Padberg","year":"1990","unstructured":"M.W. Padberg & G. Rinaldi (1990) Facet identification for the symmetric traveling salesman polytope. Math. Program. 47, 219\u2013257.","journal-title":"Math. Program."},{"key":"8_CR31","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M.W. Padberg","year":"1991","unstructured":"M.W. Padberg & G. Rinaldi (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33, 60\u2013100.","journal-title":"SIAM Rev."}],"container-title":["Integer Programming and Combinatorial Optimization","Lecture Notes in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-47867-1_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T21:32:22Z","timestamp":1550352742000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"references-count":31,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-47867-1_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"published":{"date-parts":[[2002]]}}}