zbMATH — the first resource for mathematics

Modeling robustness in CSPs as weighted CSPs. (English) Zbl 1382.68220
Gomes, Carla (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 10th international conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38170-6/pbk). Lecture Notes in Computer Science 7874, 44-60 (2013).
Summary: Many real life problems come from uncertain and dynamic environments, where the initial constraints and/or domains may undergo changes. Thus, a solution found for the problem may become invalid later. Hence, searching for robust solutions for constraint satisfaction problems (CSPs) becomes an important goal. In some cases, no knowledge about the uncertain and dynamic environment exits or it is hard to obtain it. In this paper, we consider CSPs with discrete and ordered domains where only limited assumptions are made commensurate with the structure of these problems. In this context, we model a CSP as a weighted CSP (WCSP) by assigning weights to each valid constraint tuple based on its distance from the edge of the space of valid tuples. This distance is estimated by a new concept introduced in this paper: coverings. Thus, the best solution for the modeled WCSP can be considered as a robust solution for the original CSP according to our assumptions.
For the entire collection see [Zbl 1263.68017].
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI