Modelling and Solving the Precedence-Constrained Minimum-Cost Arborescence Problem with Waiting-Times

• Autorzy: Dell'Amico Mauro , Jamal Jafar , Montemanni Roberto

Identyfikatory

DOI

10.15439/2023F6191

• Języki publikacji: EN

Abstrakty

EN

A polynomial-size mixed integer linear programming model for the Precedence-Constrained Minimum-Cost Arborescence Problem with Waiting-Times was recently proposed in the literature, that uses a smaller number of variables and constraints compared to previously proposed polynomial-size models. In this work, we extend this model with constraint programming constructs to further enhance its performance. An extensive computational study support that modern constraint programming solvers is the best tool available at solving the models proposed. Several improvements to state-of-the-art results are finally reported.

Słowa kluczowe

EN

combinatorial optimization; arborescence; precedence; constraint

PL

optymalizacja kombinatoryczna; arborescencja; ograniczenie; pierwszeństwo

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 421--430
• Opis fizyczny: Bibliogr 31 poz., il., tab., wykr.

Twórcy

autor

Dell'Amico Mauro

• Department of Sciences and Methods for Engineering University of Modena and Reggio Emilia Via Amendola 2, 42122 Reggio Emilia, Italy

• https://orcid.org/0000-0002-3283-6131

autor

Jamal Jafar

• Department of Sciences and Methods for Engineering University of Modena and Reggio Emilia Via Amendola 2, 42122 Reggio Emilia, Italy

• https://orcid.org/0009-0003-9368-1094

autor

Montemanni Roberto

• Department of Sciences and Methods for Engineering University of Modena and Reggio Emilia Via Amendola 2, 42122 Reggio Emilia, Italy

Bibliografia

• 1. J. Edmonds, “Optimum branchings,” Journal of Research of the National Bureau of Standards, vol. B 71, no. 4, pp. 233–240, 1967.
• 2. Y. J. Chu and T. Liu, “On the shortest arborescence of a directed graph,” Scientia Sinica, vol. 14, pp. 1396–1400, 1965.
• 3. H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,” Combinatorica, vol. 6, no. 2, pp. 109–122, 1986.
• 4. M. Fischetti and D. Vigo, “A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem,” Networks: An International Journal, vol. 29, no. 1, pp. 55–67, 1997.
• 5. L. Gouveia and M. J. Lopes, “The capacitated minimum spanning tree problem: On improved multistar constraints,” European Journal of Operational Research, vol. 160, no. 1, pp. 47–62, 2005.
• 6. G. Fertin, J. Fradin, and G. Jean, “Algorithmic aspects of the maximum colorful arborescence problem,” in Theory and Applications of Models of Computation. TAMC 2017. Springer, 2017, pp. 216–230.
• 7. N. Guttmann-Beck and R. Hassin, “On two restricted ancestors tree problems,” Information processing letters, vol. 110, no. 14-15, pp. 570–575, 2010.
• 8. S. C. Brailsford, C. N. Potts, and B. M. Smith, “Constraint satisfaction problems: Algorithms and applications,” European journal of operational research, vol. 119, no. 3, pp. 557–581, 1999.
• 9. F. Rossi, P. Van Beek, and T. Walsh, “Constraint programming,” Foundations of Artificial Intelligence, vol. 3, pp. 181–211, 2008.
• 10. H. Öztop, “A constraint programming model for the open vehicle routing problem with heterogeneous vehicle fleet,” in Towards Industry 5.0: Selected Papers from ISPR2022, October 6–8, 2022, Antalya. Springer, 2023, pp. 345–356.
• 11. G. Kasapidis, S. Dauzère-Pérèz, D. Paraskevopoulos, P. Repoussis, and C. Tarantilis, “On the multi-resource flexible job-shop scheduling problem with arbitrary precedence graphs,” Production and Operations Management, 2023.
• 12. E. Kirac, R. Gedik, and F. Oztanriseven, “Solving the team orienteering problem with time windows and mandatory visits using a constraint programming approach,” International Journal of Operational Research, vol. 46, no. 1, pp. 20–42, 2023.
• 13. D. Kizilay, Z. A. Çil, H. Öztop, and İ. Bağcı, “A novel mathematical model for mixed-blocking permutation flow shop scheduling problem with batch delivery,” in Towards Industry 5.0: Selected Papers from ISPR2022, October 6–8, 2022, Antalya. Springer, 2023, pp. 453–461.
• 14. R. Montemanni and M. DellAmico, “Solving the parallel drone scheduling traveling salesman problem via constraint programming,” Algorithms, vol. 16, no. 1, p. 40, 2023.
• 15. X. Chou, M. Dell’Amico, J. Jamal, and R. Montemanni, “Precedence-constrained arborescences,” European Journal of Operational Research, vol. 307, no. 2, pp. 575–589, 2022.
• 16. M. Dell’Amico, J. Jamal, and R. Montemanni, “A mixed integer linear program for a precedence-constrained minimum-cost arborescence problem,” In Proc. The 8th International Conference on Industrial Engineering and Applications (Europe), pp. 216–221, 2021.
• 17. M. DellAmico, J. Jamal, and R. Montemanni, “Compact models for the precedence-constrained minimum-cost arborescence problem,” in Advances in Intelligent Traffic and Transportation Systems. IOS Press, 2023, pp. 112–126.
• 18. M. Dell’Amico, J. Jamal, and R. Montemanni, “Compact models for the precedence-constrained minimum-cost arborescence problem with waiting-times,” Annals of Operations Research. Submitted, 2023.
• 19. N. Kamiyama, “Arborescence problems in directed graphs: Theorems and algorithms,” Interdisciplinary information sciences, vol. 20, no. 1, pp. 51–70, 2014.
• 20. Google, “Google OR-Tools,” 2015, [last accessed 7-March-2023]. [Online]. Available: https://developers.google.com/optimization
• 21. L. Perron, “CP-SAT over CBC for MIP, is it worthwhile?” 2020, [last accessed 7-March-2023]. [Online]. Available: https://or.stackexchange. com/questions/4119/cp-sat-over-cbc-for-mip-is-it-worthwhile
• 22. R. Montemanni, G. H. Carraretto, U. J. Mele, and L. M. Gambardella, “A constraint programming model for the b-coloring problem,” International Conference on Industrial Engineering and Applications, to appear, 2023.
• 23. R. Montemanni and M. Dell’Amico, “Solving the parallel drone scheduling traveling salesman problem via constraint programming,” Algorithms, vol. 16, no. 1, p. 40, 2023.
• 24. G. Reinelt, “TSPLIB–A travelling salesman problem library,” ORSA journal on computing, vol. 3, no. 4, pp. 376–384, 1991.
• 25. R. Montemanni, D. H. Smith, and L. M. Gambardella, “A heuristic manipulation technique for the sequential ordering problem,” Computers & Operations Research, vol. 35, no. 12, pp. 3931–3944, 2008.
• 26. R. Montemanni, D. H. Smith, A. E. Rizzoli, and L. M. Gambardella, “Sequential ordering problems for crane scheduling in port terminals,” International Journal of Simulation and Process Modelling, vol. 5, no. 4, pp. 348–361, 2009.
• 27. G. Shobaki and J. Jamal, “An exact algorithm for the sequential ordeing problem and its application to switching energy minimization in compilers,” Computational Optimizations and Applications, vol. 61, no. 2, pp. 343–372, 2015.
• 28. N. Ascheuer, N. Jünger, and G. Reinelt, “A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints,” Computational Optimization and Applications, vol. 17, no. 1, pp. 61–84, 2000.
• 29. V. Papapanagiotou, J. Jamal, R. Montemanni, G. Shobaki, and L. M. Gambardella, “A comparison of two exact algorithms for the sequential ordering problem,” in IEEE Conference on Systems Process and Control (ICSPC), 2015.
• 30. J. Jamal, G. Shobaki, V. Papapanagiotou, L. M. Gambardella, and R. Montemanni, “Solving the sequential ordering problem using branch and bound,” in IEEE Symposium Series on Computational Intelligence (SSCI), 2017.
• 31. IBM, “IBM CPLEX Optimizer,” 1988, [last accessed 7-March-2023]. [Online]. Available: https://www.ibm.com/de-de/analytics/cplex-optimizer

Uwagi

1. Thematic Tracks Regular Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).