{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T22:44:54Z","timestamp":1775947494111,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1991,5,1]],"date-time":"1991-05-01T00:00:00Z","timestamp":673056000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1991,5]]},"DOI":"10.1007\/bf01582894","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T04:35:11Z","timestamp":1114662911000},"page":"315-357","source":"Crossref","is-referenced-by-count":72,"title":["An analytical comparison of different formulations of the travelling salesman problem"],"prefix":"10.1007","volume":"52","author":[{"given":"Manfred","family":"Padberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ting-Yi","family":"Sung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"Contributions to the polyhedral approach to vehicle routing","author":"J.R. Araque","year":"1989","unstructured":"J.R. Araque, \u201cContributions to the polyhedral approach to vehicle routing,\u201d Ph.D. Thesis, Department of Applied Mathematics and Statistics, SUNY (Stony Brook, 1989)."},{"key":"CR2","first-page":"51","volume-title":"Modern Applied Mathematics","author":"A. Bachem","year":"1982","unstructured":"A. Bachem and M. Gr\u00f6tschel, \u201cNew aspects of polyhedral theory,\u201d in: B. Korte, ed.,Modern Applied Mathematics (North-Holland, Amsterdam, 1982) pp. 51\u2013106."},{"key":"CR3","volume-title":"Notes for the Cornell University Distinguished Lecturer Series","author":"E. Balas","year":"1987","unstructured":"E. Balas, \u201cNotes for the Cornell University Distinguished Lecturer Series,\u201d GSIA, Carnegie-Mellon University (Pittsburg, PA, 1987)."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1002\/net.3230130405","volume":"13","author":"E. Balas","year":"1983","unstructured":"E. Balas and W. Pulleyblank, \u201cThe perfectly matchable subgraph polytope of a bipartite graph,\u201dNetworks 13 (1983) 495\u2013516.","journal-title":"Networks"},{"key":"CR5","volume-title":"\u201cThe perfectly matchable subgraph polytope of an arbitrary graph,\u201d Management Science Research Report No. MSRR-538","author":"E. Balas","year":"1987","unstructured":"E. Balas and W. Pulleyblank, \u201cThe perfectly matchable subgraph polytope of an arbitrary graph,\u201d Management Science Research Report No. MSRR-538, Carnegie-Mellon University (Pittsburgh, PA, 1987)."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/zamm.19560360308","volume":"36","author":"E. Burger","year":"1956","unstructured":"E. Burger, \u201cUber homogene lineare Ungleichungssysteme,\u201dZeitschrift f\u00fcr Angewandte Mathematik und Mechanik 36 (1956) 135\u2013139.","journal-title":"Zeitschrift f\u00fcr Angewandte Mathematik und Mechanik"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1137\/0605004","volume":"5","author":"A. Claus","year":"1984","unstructured":"A. Claus, \u201cA new formulation for the traveling salesman problem,\u201dSIAM Journal of Algebraic Discrete Methods 5 (1984) 21\u201325.","journal-title":"SIAM Journal of Algebraic Discrete Methods"},{"key":"CR8","first-page":"393","volume":"2","author":"G. Dantzig","year":"1954","unstructured":"G. Dantzig, D. Fulkerson and S. Johnson, \u201cSolution of a large-scale traveling-salesman problem,\u201dOperations Research 2 (1954) 393\u2013410.","journal-title":"Operations Research"},{"key":"CR9","volume-title":"Production scheduling on parallel lines with dependencies","author":"K. Fox","year":"1973","unstructured":"K. Fox, \u201cProduction scheduling on parallel lines with dependencies,\u201d Ph.D. Thesis, Johns Hopkins University (Baltimore, MD, 1973)."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"1018","DOI":"10.1287\/opre.28.4.1018","volume":"28","author":"K. Fox","year":"1980","unstructured":"K. Fox, B. Gavish and S. Graves, \u201cAnn-constraint formulation of the (time-dependent) traveling salesman problem,\u201dOperations Research 28 (1980) 1018\u20131021.","journal-title":"Operations Research"},{"key":"CR11","first-page":"287","volume-title":"Activity Analysis of Production and Allocation","author":"D. Gale","year":"1951","unstructured":"D. Gale, \u201cConvex polyhedral cones and linear inequalities,\u201d in: Tj. Koopmans, ed.,Activity Analysis of Production and Allocation (Wiley, New York, 1951) pp. 287\u2013297."},{"key":"CR12","volume-title":"The Traveling Salesman Problem","author":"R. Garfinkel","year":"1985","unstructured":"R. Garfinkel, \u201cMotivation and modeling,\u201d in: E. Lawler et al., eds.,The Traveling Salesman Problem (Wiley, New York, 1985) Chapter 2."},{"key":"CR13","first-page":"298","volume-title":"Activity Analysis of Production and Allocation","author":"M. Gerstenhaber","year":"1951","unstructured":"M. Gerstenhaber, \u201cTheory of convex polyhedral cones,\u201d in: Tj. Koopmans, ed.,Activity Analysis of Production and Allocation (Wiley, New York, 1951) pp. 298\u2013316."},{"key":"CR14","volume-title":"The Traveling Salesman Problem","author":"M. Gr\u00f6tschel","year":"1985","unstructured":"M. Gr\u00f6tschel and M. Padberg, \u201cPolyhedral theory,\u201d in: E. Lawler et al., eds.,The Traveling Salesman Problem (Wiley, New York, 1985) Chapter 8."},{"key":"CR15","unstructured":"I. Heller, \u201cOn the travelling salesman problem,\u201dProceedings of the Second Symposium on Linear Programming, Washington, D.C., January 29, 1955."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1007\/BF01580250","volume":"6","author":"A. Hoffman","year":"1974","unstructured":"A. Hoffman, \u201cA generalization of max flow\u2014min cut,\u201dMathematical Programming 6 (1974) 352\u2013359.","journal-title":"Mathematical Programming"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02022040","volume":"4","author":"K. Hoffman","year":"1985\/6","unstructured":"K. Hoffman and M. Padberg, \u201cLP-based combinatorial problem solving,\u201dAnnals of Operations Research 4 (1985\/6) 145\u2013194.","journal-title":"Annals of Operations Research"},{"key":"CR18","first-page":"235","volume":"17","author":"E. Johnson","year":"1974","unstructured":"E. Johnson, \u201cOn cut-set integer polyhedra,\u201dCahiers du Centre de Recherche Operationelle 17 (1974) 235\u2013251.","journal-title":"Cahiers du Centre de Recherche Operationelle"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"N. Karmarkar, \u201cA new polynomial-time algorithm for linear programming,\u201dCombinatorica 4 (1984) 373\u2013395.","journal-title":"Combinatorica"},{"key":"CR20","first-page":"191","volume":"20","author":"L.G. Khachiyan","year":"1979","unstructured":"L.G. Khachiyan, \u201cA polynomial algorithm in linear programming,\u201dSoviet Mathematics Doklady 20 (1979) 191\u2013194.","journal-title":"Soviet Mathematics Doklady"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/BF01588263","volume":"17","author":"A. Lehman","year":"1979","unstructured":"A. Lehman, \u201cOn the width\u2014length inequality,\u201dMathematical Programming 17 (1979) 403\u2013417.","journal-title":"Mathematical Programming"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"C. Miller","year":"1960","unstructured":"C. Miller, A. Tucker and R. Zemlin, \u201cInteger programming formulations and traveling salesman problems,\u201dJournal of the Association for Computing Machinery 7 (1960) 326\u2013329.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1002\/nav.3800190410","volume":"19","author":"M. Padberg","year":"1972","unstructured":"M. Padberg, \u201cEquivalent knapsack-type formulations of bounded integer linear programs: an alternative approach,\u201dNaval Research Logistics Quarterly 19 (1972) 699\u2013708.","journal-title":"Naval Research Logistics Quarterly"},{"key":"CR24","volume-title":"An analytic symmetrization of max flow\u2014min cut","author":"M. Padberg","year":"1989","unstructured":"M. Padberg and Ting-Yi Sung, \u201cAn analytic symmetrization of max flow\u2014min cut,\u201d Preprint, Stern School of Business, New York University (New York, 1989)."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1287\/opre.26.1.86","volume":"26","author":"J. Picard","year":"1978","unstructured":"J. Picard and M. Queyranne, \u201cThe time-dependent travelling salesman problem and its application to the tardiness problem in one-machine scheduling,\u201dOperations Research 26 (1978) 86\u2013110.","journal-title":"Operations Research"},{"key":"CR26","volume-title":"Linear Programming","author":"M. Simmonnard","year":"1966","unstructured":"M. Simmonnard,Linear Programming (Prentice-Hall, Englewood Cliffs, NJ, 1966)."},{"key":"CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-46216-0","volume-title":"Convexity and Optimization in Finite Dimensions I","author":"J. Stoer","year":"1970","unstructured":"J. Stoer and C. Witzgall,Convexity and Optimization in Finite Dimensions I (Springer, Berlin, 1970)."},{"key":"CR28","volume-title":"Contributions to the travelling salesman problem and its variants","author":"Ting-Yi Sung","year":"1988","unstructured":"Ting-Yi Sung, \u201cContributions to the travelling salesman problem and its variants,\u201d Ph.D. Thesis, Stern School of Business, New York University (New York, 1988)."},{"key":"CR29","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/BF01292722","volume":"7","author":"H. Weyl","year":"1935","unstructured":"H. Weyl, \u201cElementare Theorie der konvexen Polyeder,\u201dCommentarii Mathematici Helvetici 7 (1935) 290\u2013306. [Translation in: H. Kuhn and A. Tucker, eds.,Contributions to the Theory of Games I (Princeton University Press, Princeton, NJ, 1950) pp. 3\u201318.]","journal-title":"Commentarii Mathematici Helvetici"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF01589102","volume":"45","author":"L. Wolsey","year":"1989","unstructured":"L. Wolsey, \u201cStrong formulations for mixed integer programming: a survey,\u201dMathematical Programming (Series B) 45 (1989) 173\u2013191.","journal-title":"Mathematical Programming (Series B)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01582894.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01582894\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01582894","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T11:15:55Z","timestamp":1556882155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01582894"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,5]]},"references-count":30,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1991,5]]}},"alternative-id":["BF01582894"],"URL":"https:\/\/doi.org\/10.1007\/bf01582894","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,5]]}}}