Modeling robustness in CSPs as weighted CSPs
Loading...
Files
Accepted Version
Date
2013
Authors
Climent, Laura
Wallace, Richard J.
Salido, Miguel A.
Barber, Federico
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Published Version
Abstract
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.
Description
Keywords
Robustness , Uncertainty , Dynamic CSPs
Citation
Climent, L., Wallace, R. J., Salido, M. A. and Barber, F. (2013) 'Modeling robustness in CSPs as weighted CSPs', in Gomes, C. and Sellmann, M. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2013. Lecture Notes in Computer Science, 7874, pp. 44-60. Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-38171-3_4
Link to publisher’s version
Copyright
© 2013, Springer-Verlag Berlin Heidelberg. This is a post-peer-review, pre-copyedit version of a paper published in Lecture Notes in Computer Science. The final authenticated version is available online at: https://doi.org/10.1007/978-3-642-38171-3_4