2026-07-23T15:49:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19071 2024-03-06T11:03:26Z ddc:004 open_access

Constraint Programming with External Worst-Case Traversal Time Analysis Talbot, Pierre Hu, Tingting Navet, Nicolas Constraint programming external function multi-objective optimization network analysis worst-case traversal time analysis abstract interpretation The allocation of software functions to processors under compute capacity and network links constraints is an important optimization problem in the field of embedded distributed systems. We present a hybrid approach to solve the allocation problem combining a constraint solver and a worst-case traversal time (WCTT) analysis that verifies the network timing constraints. The WCTT analysis is implemented as an industrial black-box program, which makes a tight integration with constraint solving challenging. We contribute to a new multi-objective constraint solving algorithm for integrating external under-approximating functions, such as the WCTT analysis, with constraint solving, and prove its correctness. We apply this new algorithm to the allocation problem in the context of automotive service-oriented architectures based on Ethernet networks, and provide a new dataset of realistic instances to evaluate our approach. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Talbot and Tingting Hu and Nicolas Navet 2023 Is Part Of LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2023.34 urn:nbn:de:0030-drops-190713 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.34 eng https://creativecommons.org/licenses/by/4.0/legalcode