{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T03:50:11Z","timestamp":1777002611470,"version":"3.51.4"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T00:00:00Z","timestamp":1748822400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T00:00:00Z","timestamp":1748822400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100025012","name":"Universit\u00e9 Paris Dauphine-PSL","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100025012","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>This paper deals with a variant of the Traveling Salesman Problem (TSP), called the Multiple Steiner TSP with Order Constraints (MSTSPOC). Consider an undirected graph with nonnegative weights on the edges, and a set of salesmen such that with each salesman is associated a set of ordered terminals. The MSTSPOC consists in finding a minimum-weight subgraph containing for each salesman a tour going in order through its terminals. We study the polytope associated with the Integer Linear Programming (ILP) formulation proposed in Borne et\u00a0al. (2013). We characterize when the basic inequalities define facets. We also describe new valid inequalities along with necessary conditions and sufficient conditions for these inequalities to be facet-defining. Further families of valid inequalities, coming from closely related problems, are also discussed. The theoretical results presented in this paper are computationally tested in a companion paper (Taktak 2024).<\/jats:p>","DOI":"10.1007\/s10878-025-01288-1","type":"journal-article","created":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T13:13:11Z","timestamp":1748869991000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The multiple steiner TSP with cyclic order on terminals: valid inequalities and polyhedra"],"prefix":"10.1007","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1079-1892","authenticated-orcid":false,"given":"A. Ridha","family":"Mahjoub","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raouia","family":"Taktak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eduardo","family":"Uchoa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,2]]},"reference":[{"issue":"4","key":"1288_CR1","doi-asserted-by":"publisher","first-page":"1396","DOI":"10.1111\/itor.12592","volume":"26","author":"E \u00c1lvarez-Miranda","year":"2019","unstructured":"\u00c1lvarez-Miranda E, Sinnl M (2019) A note on computational aspects of the Steiner travelling salesman problem. Int Trans Oper Res 26(4):1396\u20131401","journal-title":"Int Trans Oper Res"},{"key":"1288_CR2","volume-title":"The Traveling Salesman Problem: a computational study","author":"DL Applegate","year":"2007","unstructured":"Applegate DL, Bixby RE, Chvatal V, Cook WJ (2007) The Traveling Salesman Problem: a computational study. Princeton University Press"},{"key":"1288_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1023\/A:1008779125567","volume":"17","author":"N Ascheuer","year":"2000","unstructured":"Ascheuer N, J\u00fcnger M, Reinelt G (2000) A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Comput Optim Appl 17:61\u201384","journal-title":"Comput Optim Appl"},{"issue":"2","key":"1288_CR4","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1287\/moor.25.2.243.12223","volume":"25","author":"M Ba\u00efou","year":"2000","unstructured":"Ba\u00efou M, Barahona F, Mahjoub AR (2000) Separation of partition inequalities. Math Oper Res 25(2):243\u2013254","journal-title":"Math Oper Res"},{"key":"1288_CR5","unstructured":"Ba\u00efou M, Barahona F, Mahjoub AR (2011) Partition inequalities: Separation, extensions and network design. In Progress Combinatorial Optimization (Ed.) Wiley-ISTE pp. 1\u201339"},{"key":"1288_CR6","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF01585767","volume":"68","author":"E Balas","year":"1995","unstructured":"Balas E, Fischetti M, Pulleyblank WR (1995) The precedence-constrained asymmetric traveling salesman polytope. Math Program 68:241\u2013265","journal-title":"Math Program"},{"issue":"1\u20133","key":"1288_CR7","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0012-365X(94)00255-H","volume":"147","author":"F Barahona","year":"1995","unstructured":"Barahona F, Mahjoub AR (1995) On two-connected subgraph polytopes. Discret Math 147(1\u20133):19\u201334","journal-title":"Discret Math"},{"issue":"3","key":"1288_CR8","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","volume":"34","author":"T Bektas","year":"2006","unstructured":"Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3):209\u2013219","journal-title":"Omega"},{"issue":"1","key":"1288_CR9","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/s10479-011-1024-y","volume":"207","author":"E Benavent","year":"2013","unstructured":"Benavent E, Mart\u00ednez A (2013) Multi-depot multiple TSP: a polyhedral study and computational results. Ann Oper Res 207(1):7\u201325","journal-title":"Ann Oper Res"},{"issue":"1","key":"1288_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1002\/net.20310","volume":"55","author":"F Bendali","year":"2010","unstructured":"Bendali F, Diarrassouba I, Mahjoub AR, Didi Biha M, Mailfert J (2010) A branch-and-cut algorithm for the k-edge connected subgraph problem. Networks 55(1):13\u201332","journal-title":"Networks"},{"issue":"4","key":"1288_CR11","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1002\/net.22125","volume":"80","author":"R Bernardino","year":"2022","unstructured":"Bernardino R, Gouveia L, Paias A, Santos D (2022) The multi-depot family traveling salesman problem and clustered variants: Mathematical formulations and branch- &-cut based methods. Networks 80(4):502\u2013571","journal-title":"Networks"},{"key":"1288_CR12","doi-asserted-by":"crossref","unstructured":"Borne S, Gabrel V, Mahjoub AR, Taktak R (2011) Multilayer survivable optical network design. In: International Network Optimization Conference (INOC), pp. 170\u2013175. Springer","DOI":"10.1007\/978-3-642-21527-8_22"},{"key":"1288_CR13","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/j.endm.2013.05.129","volume":"41","author":"S Borne","year":"2013","unstructured":"Borne S, Mahjoub AR, Taktak R (2013) A branch-and-cut algorithm for the multiple Steiner TSP with order constraints. Electron Notes Discr Math 41:487\u2013494","journal-title":"Electron Notes Discr Math"},{"key":"1288_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2021.100369","volume":"40","author":"O Cheikhrouhou","year":"2021","unstructured":"Cheikhrouhou O, Khoufi I (2021) A comprehensive survey on the multiple traveling salesman problem: Applications, approaches and taxonomy. Comput Sci Rev 40:100369","journal-title":"Comput Sci Rev"},{"issue":"1","key":"1288_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0167-6377(89)90029-1","volume":"8","author":"S Chopra","year":"1989","unstructured":"Chopra S (1989) On the spanning tree polyhedron. Oper Res Lett 8(1):25\u201329","journal-title":"Oper Res Lett"},{"issue":"1\u20133","key":"1288_CR16","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01582573","volume":"64","author":"S Chopra","year":"1994","unstructured":"Chopra S, Rao MR (1994) The Steiner tree problem I: Formulations, compositions and extension of facets. Math Program 64(1\u20133):209\u2013229","journal-title":"Math Program"},{"issue":"1\u20133","key":"1288_CR17","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF01582574","volume":"64","author":"S Chopra","year":"1994","unstructured":"Chopra S, Rao MR (1994) The Steiner tree problem II: properties and classes of facet. Math Program 64(1\u20133):231\u2013246","journal-title":"Math Program"},{"issue":"4","key":"1288_CR18","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal V (1973) Edmonds polytopes and a hierarchy of combinatorial problems. Discret Math 4(4):305\u2013337","journal-title":"Discret Math"},{"issue":"13","key":"1288_CR19","doi-asserted-by":"publisher","first-page":"3014","DOI":"10.3390\/math11133014","volume":"11","author":"JA Cornejo-Acosta","year":"2023","unstructured":"Cornejo-Acosta JA, Garc\u00eda-D\u00edaz J, P\u00e9rez-Sansalvador JC, Segura C (2023) Compact integer programs for depot-free multiple traveling salesperson problems. Mathematics 11(13):3014","journal-title":"Mathematics"},{"key":"1288_CR20","unstructured":"D\u2019Angelo G (2018) The Steiner multi cycle problem with applications to a collaborative truckload problem. In: 17th International Symposium on Experimental Algorithms (SEA 2018), 103:26"},{"issue":"5","key":"1288_CR21","doi-asserted-by":"publisher","first-page":"949","DOI":"10.1287\/opre.1070.0387","volume":"55","author":"E Duchenne","year":"2007","unstructured":"Duchenne E, Laporte G, Semet F (2007) The undirected m-peripatetic salesman problem: polyhedral results and new algorithms. Oper Res 55(5):949\u2013965","journal-title":"Oper Res"},{"issue":"3","key":"1288_CR22","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1016\/j.ejor.2012.07.022","volume":"223","author":"E Duchenne","year":"2012","unstructured":"Duchenne E, Laporte G, Semet F (2012) The undirected m-capacitated peripatetic salesman problem. Eur J Oper Res 223(3):637\u2013643","journal-title":"Eur J Oper Res"},{"key":"1288_CR23","first-page":"125","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Maximum matching and a polyhedron with 0,1-vertices. J Res Nat Bur Std (B) 69:125\u2013130","journal-title":"J Res Nat Bur Std (B)"},{"issue":"23","key":"1288_CR24","doi-asserted-by":"publisher","first-page":"17957","DOI":"10.1007\/s00500-020-05043-y","volume":"24","author":"V Gabrel","year":"2020","unstructured":"Gabrel V, Mahjoub AR, Taktak R, Uchoa E (2020) The multiple Steiner TSP with order constraints: complexity and optimization algorithms. Soft Comput 24(23):17957\u201317968","journal-title":"Soft Comput"},{"issue":"2","key":"1288_CR25","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1002\/net.20122","volume":"48","author":"L Gouveia","year":"2006","unstructured":"Gouveia L, Pesneau P (2006) On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks 48(2):77\u201389","journal-title":"Networks"},{"issue":"4","key":"1288_CR26","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1002\/net.21765","volume":"71","author":"L Gouveia","year":"2018","unstructured":"Gouveia L, Pesneau P, Ruthmair M, Santos D (2018) Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem. Networks 71(4):451\u2013465","journal-title":"Networks"},{"key":"1288_CR27","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BFb0120887","volume":"12","author":"M Gr\u00f6tschel","year":"1980","unstructured":"Gr\u00f6tschel M (1980) On the symmetric travelling salesman problem: solution of a 120-city problem. Math Program Study 12:61\u201377","journal-title":"Math Program Study"},{"issue":"4","key":"1288_CR28","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1137\/0403043","volume":"3","author":"M Gr\u00f6tschel","year":"1990","unstructured":"Gr\u00f6tschel M, Monma CL (1990) Integer polyhedra arising from certain network design problems with connectivity constraints. SIAM J Discret Math 3(4):502\u2013523","journal-title":"SIAM J Discret Math"},{"issue":"1","key":"1288_CR29","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01582116","volume":"16","author":"M Gr\u00f6tschel","year":"1979","unstructured":"Gr\u00f6tschel M, Padberg MW (1979) On the symmetric travelling salesman problem I: inequalities. Math Program 16(1):265\u2013280","journal-title":"Math Program"},{"issue":"2","key":"1288_CR30","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/S0895480102419445","volume":"18","author":"D Huygens","year":"2004","unstructured":"Huygens D, Mahjoub AR, Pesneau P (2004) Two edge-disjoint hop-constrained paths and polyhedra. SIAM J Discret Math 18(2):287\u2013312","journal-title":"SIAM J Discret Math"},{"issue":"6","key":"1288_CR31","doi-asserted-by":"publisher","first-page":"1307","DOI":"10.1111\/itor.12419","volume":"24","author":"R Interian","year":"2017","unstructured":"Interian R, Ribeiro CC (2017) A grasp heuristic using path-relinking and restarts for the Steiner traveling salesman problem. Int Trans Oper Res 24(6):1307\u20131323","journal-title":"Int Trans Oper Res"},{"issue":"2","key":"1288_CR32","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1016\/j.ejor.2023.01.039","volume":"309","author":"D Khachai","year":"2023","unstructured":"Khachai D, Sadykov R, Battaia O, Khachay M (2023) Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm. Eur J Oper Res 309(2):488\u2013505","journal-title":"Eur J Oper Res"},{"issue":"1","key":"1288_CR33","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.ejor.2013.01.044","volume":"228","author":"AN Letchford","year":"2013","unstructured":"Letchford AN, Nasiri SD, Theis DO (2013) Compact formulations of the Steiner traveling salesman problem and related problems. Eur J Oper Res 228(1):83\u201392","journal-title":"Eur J Oper Res"},{"key":"1288_CR34","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2020.06.022","volume":"835","author":"CN Lintzmayer","year":"2020","unstructured":"Lintzmayer CN, Miyazawa FK, Moura PF, Xavier EC (2020) Randomized approximation scheme for Steiner multi cycle in the Euclidean plane. Theoret Comput Sci 835:134\u2013155","journal-title":"Theoret Comput Sci"},{"key":"1288_CR35","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1007\/s10878-021-00720-6","volume":"41","author":"H Liu","year":"2021","unstructured":"Liu H, Zhang H, Xu Y (2021) The m-Steiner traveling salesman problem with online edge blockages. J Comb Optim 41:844\u2013860","journal-title":"J Comb Optim"},{"issue":"1\u20133","key":"1288_CR36","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF01582572","volume":"64","author":"AR Mahjoub","year":"1994","unstructured":"Mahjoub AR (1994) Two edge connected spanning subgraphs and polyhedra. Math Program 64(1\u20133):199\u2013208","journal-title":"Math Program"},{"issue":"3","key":"1288_CR37","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1051\/ro:2008022","volume":"42","author":"AR Mahjoub","year":"2008","unstructured":"Mahjoub AR, Pesneau P (2008) On the Steiner 2-edge connected subgraph polytope. RAIRO - Oper Res 42(3):259\u2013283","journal-title":"RAIRO - Oper Res"},{"key":"1288_CR38","doi-asserted-by":"crossref","unstructured":"Mahjoub AR, Taktak R, Uchoa E (2019) A layered compact formulation for the multiple Steiner TSP with order constraints. In: 6th International Conference on Control, Decision and Information Technologies (CoDIT), pp. 1462\u20131467. IEEE","DOI":"10.1109\/CoDIT.2019.8820661"},{"issue":"1","key":"1288_CR39","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"s1\u201336","author":"CSJA Nash-Williams","year":"1961","unstructured":"Nash-Williams CSJA (1961) Edge-disjoint spanning trees of finite graphs. J Lond Math Soc s1\u201336(1):445\u2013450","journal-title":"J Lond Math Soc"},{"issue":"2","key":"1288_CR40","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1016\/j.ejor.2019.04.047","volume":"278","author":"J Rodr\u00edguez-Pereira","year":"2019","unstructured":"Rodr\u00edguez-Pereira J, Fern\u00e1ndez E, Laporte G, Benavent E, Mart\u00ednez-Sykora A (2019) The Steiner travelling salesman problem problem and its extensions. Eur J Oper Res 278(2):615\u2013628","journal-title":"Eur J Oper Res"},{"issue":"1","key":"1288_CR41","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.orl.2004.03.007","volume":"33","author":"SC Sarin","year":"2005","unstructured":"Sarin SC, Sherali HD, Bhootra A (2005) New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints. Oper Res Lett 33(1):62\u201370","journal-title":"Oper Res Lett"},{"key":"1288_CR42","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.cor.2014.05.014","volume":"51","author":"SC Sarin","year":"2014","unstructured":"Sarin SC, Sherali HD, Judd JD, Tsai PFJ (2014) Multiple asymmetric traveling salesmen problem with and without precedence constraints: Performance comparison of alternative formulations. Comput Oper Res 51:64\u201389","journal-title":"Comput Oper Res"},{"key":"1288_CR43","volume-title":"Design of survivable networks. Lectures Notes in Mathematics 1531","author":"M Stoer","year":"1992","unstructured":"Stoer M (1992) Design of survivable networks. Lectures Notes in Mathematics 1531. Springer-Verlag"},{"key":"1288_CR44","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.cor.2015.12.014","volume":"70","author":"K Sundar","year":"2016","unstructured":"Sundar K, Rathinam S (2016) Generalized multiple depot multiple traveling salesmen problem-polyhedral study and exact algorithm. Comput Oper Res 70:39\u201355","journal-title":"Comput Oper Res"},{"key":"1288_CR45","first-page":"487","volume":"41","author":"R Taktak","year":"2024","unstructured":"Taktak R (2024) A branch-and-cut algorithm for the multiple Steiner TSP with order constraints. Ann Oper Res 41:487\u2013494","journal-title":"Ann Oper Res"},{"key":"1288_CR46","doi-asserted-by":"crossref","unstructured":"Taktak R, Uchoa E (2020) On the multiple Steiner traveling salesman problem with order constraints. In: Lecture Notes in Computer Science 12176, M. Ba\u00efou, B. Gendron, O. G\u00fcnl\u00fck, A.R. Mahjoub (Eds), International Symposium on Combinatorial Optimization (ISCO), pp. 66\u201377. Springer","DOI":"10.1007\/978-3-030-53262-8_6"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01288-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01288-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01288-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T17:25:17Z","timestamp":1757179517000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01288-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,2]]},"references-count":46,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["1288"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01288-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,2]]},"assertion":[{"value":"19 March 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2025","order":2,"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"}}],"article-number":"89"}}