Modeling robustness in CSPs as weighted CSPs

Simple item page
dc.contributor.authorCliment, Lauraen
dc.contributor.authorWallace, Richard J.en
dc.contributor.authorSalido, Miguel A.en
dc.contributor.authorBarber, Federicoen
dc.contributor.funderMinisterio de Ciencia, Tecnología e Innovaciónen
dc.date.accessioned2025-01-08T13:02:39Z
dc.date.available2025-01-08T13:02:39Z
dc.date.issued2013en
dc.description.abstractMany 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.en
dc.description.sponsorshipMinisterio de Ciencia, Tecnología e Innovación (TIN2010-20976-C02-01; FPU program fellowship)en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationCliment, 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_4en
dc.identifier.doihttps://doi.org/10.1007/978-3-642-38171-3_4en
dc.identifier.eissn1611-3349en
dc.identifier.endpage60en
dc.identifier.isbn9783642381706en
dc.identifier.isbn9783642381713en
dc.identifier.issn0302-9743en
dc.identifier.journaltitleLecture Notes in Computer Scienceen
dc.identifier.startpage44en
dc.identifier.urihttps://hdl.handle.net/10468/16792
dc.identifier.volume7874en
dc.language.isoenen
dc.publisherSpringeren
dc.relation.ispartofLecture Notes in Computer Scienceen
dc.relation.ispartofCPAIOR 2013, May 18-22, 2013, Yorktown Heights, NYen
dc.relation.ispartofGomes, C. and Sellmann, M. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problemsen
dc.rights© 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_4en
dc.subjectRobustnessen
dc.subjectUncertaintyen
dc.subjectDynamic CSPsen
dc.titleModeling robustness in CSPs as weighted CSPsen
dc.typeConference itemen
dc.typeBook chapteren
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
pre-print.pdf
Size:
200.61 KB
Format:
Adobe Portable Document Format
Description:
Accepted Version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Insight Centre for Data Analytics - Conference Items