License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.34
URN: urn:nbn:de:0030-drops-190713
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19071/
Talbot, Pierre ;
Hu, Tingting ;
Navet, Nicolas
Constraint Programming with External Worst-Case Traversal Time Analysis
Abstract
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.
BibTeX - Entry
@InProceedings{talbot_et_al:LIPIcs.CP.2023.34,
author = {Talbot, Pierre and Hu, Tingting and Navet, Nicolas},
title = {{Constraint Programming with External Worst-Case Traversal Time Analysis}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {34:1--34:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-300-3},
ISSN = {1868-8969},
year = {2023},
volume = {280},
editor = {Yap, Roland H. C.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19071},
URN = {urn:nbn:de:0030-drops-190713},
doi = {10.4230/LIPIcs.CP.2023.34},
annote = {Keywords: Constraint programming, external function, multi-objective optimization, network analysis, worst-case traversal time analysis, abstract interpretation}
}
