{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T12:50:10Z","timestamp":1782391810515,"version":"3.54.5"},"reference-count":50,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,12,27]],"date-time":"2023-12-27T00:00:00Z","timestamp":1703635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The minimum-cost arborescence problem is a well-studied problem. Polynomial-time algorithms for solving it exist. Recently, a new variation of the problem called the Precedence-Constrained Minimum-Cost Arborescence Problem with Waiting Times was presented and proven to be NP-hard. In this work, we propose new polynomial-size models for the problem that are considerably smaller in size compared to those previously proposed. We experimentally evaluate and compare each new model in terms of computation time and quality of the solutions. Several improvements to the best-known upper and lower bounds of optimal solution costs emerge from the study.<\/jats:p>","DOI":"10.3390\/a17010012","type":"journal-article","created":{"date-parts":[[2023,12,27]],"date-time":"2023-12-27T10:23:54Z","timestamp":1703672634000},"page":"12","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Compact Models to Solve the Precedence-Constrained Minimum-Cost Arborescence Problem with Waiting Times"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3283-6131","authenticated-orcid":false,"given":"Mauro","family":"Dell\u2019Amico","sequence":"first","affiliation":[{"name":"Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, Via Amendola 2, 42122 Reggio Emilia, RE, Italy"},{"name":"Interdepartmental Center En&Tech, University of Modena and Reggio Emilia, Capannone 19 Tecnopolo, Piazza Europa 1, 42122 Reggio Emilia, RE, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9368-1094","authenticated-orcid":false,"given":"Jafar","family":"Jamal","sequence":"additional","affiliation":[{"name":"Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, Via Amendola 2, 42122 Reggio Emilia, RE, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0229-0465","authenticated-orcid":false,"given":"Roberto","family":"Montemanni","sequence":"additional","affiliation":[{"name":"Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, Via Amendola 2, 42122 Reggio Emilia, RE, Italy"},{"name":"Interdepartmental Center En&Tech, University of Modena and Reggio Emilia, Capannone 19 Tecnopolo, Piazza Europa 1, 42122 Reggio Emilia, RE, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2023,12,27]]},"reference":[{"key":"ref_1","first-page":"1396","article-title":"On the shortest arborescence of a directed graph","volume":"14","author":"Chu","year":"1965","journal-title":"Sci. Sin."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","article-title":"Optimum branchings","volume":"71","author":"Edmonds","year":"1967","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","article-title":"Efficient algorithms for finding minimum spanning trees in undirected and directed graphs","volume":"6","author":"Gabow","year":"1986","journal-title":"Combinatorica"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"105107","DOI":"10.1016\/j.cor.2020.105107","article-title":"A tabu search algorithm for the probabilistic orienteering problem","volume":"126","author":"Chou","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_5","unstructured":"Bock, F. (1971). An algorithm to construct a minimum directed spanning tree in a directed network. Dev. Oper. Res., 29\u201344."},{"key":"ref_6","first-page":"55","article-title":"A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem","volume":"29","author":"Fischetti","year":"1997","journal-title":"Netw. Int. J."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2374","DOI":"10.1111\/itor.12857","article-title":"Branch-and-cut algorithms for the p-arborescence star problem","volume":"29","author":"Pereira","year":"2021","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.cor.2018.10.004","article-title":"The p-arborescence star problem: Formulations and exact solution approaches","volume":"102","author":"Morais","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1287\/opre.13.3.462","article-title":"Optimum distribution of switching centers in a communication network and some related graph theoretic problems","volume":"13","author":"Hakimi","year":"1965","journal-title":"Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1016\/j.ipl.2010.05.002","article-title":"On two restricted ancestors tree problems","volume":"110","author":"Hassin","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1002\/net.22009","article-title":"A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs","volume":"78","author":"Carrabs","year":"2021","journal-title":"Networks"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","article-title":"On the shortest spanning subtree of a graph and the traveling salesman problem","volume":"7","author":"Kruskal","year":"1956","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.ejor.2003.10.021","article-title":"The capacitated minimum spanning tree problem: On improved multistar constraints","volume":"160","author":"Gouveia","year":"2005","journal-title":"Eur. J. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1664","DOI":"10.1287\/moor.2021.1184","article-title":"A Randomly Weighted Minimum Arborescence with a Random Cost Constraint","volume":"47","author":"Frieze","year":"2021","journal-title":"Math. Oper. Res."},{"key":"ref_15","unstructured":"Fertin, G., Fradin, J., and Jean, G. (2017). Theory and Applications of Models of Computation, Springer. TAMC 2017."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1137\/0205044","article-title":"Augmentation problems","volume":"5","author":"Eswaran","year":"1976","journal-title":"SIAM J. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Li, J., Liu, X., and Lichen, J. (2017, January 13\u201316). The constrained arborescence augmentation problem in digraphs. Proceedings of the 2017 3rd IEEE International Conference on Computer and Communications (ICCC), Chengdu, China.","DOI":"10.1109\/CompComm.2017.8322734"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0377-2217(03)00071-7","article-title":"Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs","volume":"156","author":"Kawatra","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/978-3-642-20662-7_10","article-title":"On minimum changeover cost arborescences","volume":"6630","author":"Galbiati","year":"2011","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1227","DOI":"10.1016\/j.ipl.2009.09.004","article-title":"A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph","volume":"109","author":"Fujishige","year":"2009","journal-title":"Inf. Process. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(91)90002-2","article-title":"Edge-disjoint in- and out-branchings in tournaments and related path problems","volume":"51","year":"1991","journal-title":"J. Comb. Theory\u2014Ser. B"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1460","DOI":"10.1109\/TMC.2006.154","article-title":"On the construction of a strongly connected broadcast arborescence with bounded transmission delay","volume":"5","author":"Li","year":"2006","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s10479-018-2895-y","article-title":"Minimum spanning tree with conflicting edge pairs: A branch-and-cut approach","volume":"298","author":"Carrabs","year":"2021","journal-title":"Ann. Oper. Res."},{"key":"ref_24","unstructured":"Darmann, A., Pferschy, U., and Schauer, J. (2009). Algorithmic Decision Theory, Springer."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1111\/itor.12690","article-title":"Two dependency constrained spanning tree problems","volume":"27","author":"Viana","year":"2020","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0377-2217(88)90333-5","article-title":"An inexact algorithm for the sequential ordering problem","volume":"37","author":"Escudero","year":"1988","journal-title":"Eur. J. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1016\/S0377-2217(01)00227-2","article-title":"An efficient genetic algorithm for the traveling salesman problem with precedence constraints","volume":"140","author":"Moon","year":"2002","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF01585767","article-title":"The precedence-constrained asymmetric traveling salesman polytope","volume":"68","author":"Balas","year":"1995","journal-title":"Math. Program."},{"key":"ref_29","unstructured":"Hern\u00e1dv\u00f6lgyi, I. (2004). Operations Research Proceedings 2003, Springer."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF02085641","article-title":"A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships","volume":"50","author":"Escudero","year":"1994","journal-title":"Ann. Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1287\/ijoc.12.3.237.12636","article-title":"An ant colony system hybridized with a new local search for the sequential ordering problem","volume":"12","author":"Gambardella","year":"2000","journal-title":"INFORMS J. Comput."},{"key":"ref_32","unstructured":"Karan, M., and Skorin-Kapov, N. (2011, January 23\u201327). A branch and bound algorithm for the sequential ordering problem. Proceedings of the MIPRO, 2011 Proceedings of the 34th International Convention, Opatija, Croatia."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1137\/0803002","article-title":"A cutting plane approach to the sequential ordering problem (with applications to job scheduling in manufacturing)","volume":"3","author":"Ascheuer","year":"1993","journal-title":"SIAM J. Optim."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1023\/A:1008779125567","article-title":"A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints","volume":"17","author":"Ascheuer","year":"2000","journal-title":"Comput. Optim. Appl."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Montemanni, R., Smith, D.H., and Gambardella, L.M. (2007, January 1\u20135). Ant colony systems for large sequential ordering problems. Proceedings of the IEEE Swarm Intelligence Symposium (SIS), Honolulu, HI, USA.","DOI":"10.1109\/SIS.2007.368027"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1287\/inte.22.3.100","article-title":"Precedence constrained routing and helicopter scheduling: Heuristic design","volume":"22","author":"Pulleyblank","year":"1992","journal-title":"Interfaces"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Dell\u2019Amico, M., Jamal, J., and Montemanni, R. (2021, January 8\u201311). A mixed integer linear program for a precedence-constrained minimum-cost arborescence problem. Proceedings of the 8th International Conference on Industrial Engineering and Applications (Europe), Online.","DOI":"10.1145\/3463858.3463868"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1016\/j.ejor.2022.10.014","article-title":"Precedence-Constrained Arborescences","volume":"307","author":"Chou","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1137\/S0097539704371353","article-title":"The rectilinear Steiner arborescence problem is NP-complete","volume":"35","author":"Shi","year":"2005","journal-title":"SIAM J. Comput."},{"key":"ref_40","first-page":"145","article-title":"Multicommodity network flows: A survey, Part I: Applications and Formulations","volume":"15","author":"Wang","year":"2018","journal-title":"Int. J. Oper. Res."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0167-6377(03)00093-2","article-title":"On the nearest neighbor rule for the traveling salesman problem","volume":"32","author":"Hurkensa","year":"2004","journal-title":"Oper. Res. Lett."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Dell\u2019Amico, M., Jamal, J., and Montemanni, R. (2022, January 25\u201327). Compact Models for the Precedence-Constrained Minimum-Cost Arborescence Problem. Proceedings of the 2022 The 6th International Conference on Intelligent Traffic and Transportation (ICITT), Paris, France.","DOI":"10.3233\/ATDE230015"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","article-title":"Algorithm 97: Shortest Path","volume":"5","author":"Floyd","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_44","unstructured":"Google (2023, November 20). Google OR-Tools. Available online: https:\/\/developers.google.com\/optimization."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Montemanni, R., and Dell\u2019Amico, M. (2023). Solving the Parallel Drone Scheduling Traveling Salesman Problem via Constraint Programming. Algorithms, 16.","DOI":"10.3390\/a16010040"},{"key":"ref_46","unstructured":"IBM (2023, November 20). IBM CPLEX Optimizer. Available online: https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio\/cplex-optimizer."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"TSPLIB\u2013A travelling salesman problem library","volume":"3","author":"Reinelt","year":"1991","journal-title":"ORSA J. Comput."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1504\/IJSPM.2009.032597","article-title":"Sequential ordering problems for crane scheduling in port terminals","volume":"5","author":"Montemanni","year":"2009","journal-title":"Int. J. Simul. Process Model."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s10589-015-9725-9","article-title":"An exact algorithm for the sequential ordeing problem and its application to switching energy minimization in compilers","volume":"61","author":"Shobaki","year":"2015","journal-title":"Comput. Optim. Appl."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1109\/4235.585893","article-title":"No Free Lunch Theorems for Optimization","volume":"1","author":"Wolpert","year":"1997","journal-title":"IEEE Trans. Evol. Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/1\/12\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:42:51Z","timestamp":1760132571000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/1\/12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,27]]},"references-count":50,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,1]]}},"alternative-id":["a17010012"],"URL":"https:\/\/doi.org\/10.3390\/a17010012","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,27]]}}}