Large Neighborhood Search for robust solutions for Constraint Satisfaction Problems with ordered domains

Simple item page
dc.contributor.authorLópez, Jheisson
dc.contributor.authorArbelaez, Alejandro
dc.contributor.authorCliment, Laura
dc.contributor.editorSolnon, Christine
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2022-08-03T15:15:23Z
dc.date.available2022-08-03T15:15:23Z
dc.date.issued2022-07-23
dc.date.updated2022-08-03T15:00:22Z
dc.description.abstractOften, real-world Constraint Satisfaction Problems (CSPs) are subject to uncertainty/dynamism not known in advance. Some techniques in the literature offer robust solutions for CSPs. Here, we analyze a previous exact/complete approach from the state-of-the-art that focuses on CSPs with ordered domains and dynamic bounds. However, this approach has low performance in large-scale CSPs. For this reason, in this paper, we present an inexact/incomplete approach that is faster at finding robust solutions for large-scale CSPs. It is useful when the computation time available for finding a solution is limited and/or in situations where a new one must be re-computed online because the dynamism invalidated the original one. Specifically, we present a Large Neighbourhood Search (LNS) algorithm combined with Constraint Programming (CP) and Branch-and-bound (B&B) that searches for robust solutions. We also present a robust-value selection heuristic that guides the search toward more promising branches. We evaluate our approach with large-scale CSPs instances, including the case study of scheduling problems. The evaluation shows a considerable improvement in the robustness of the solutions achieved by our algorithm for large-scale CSPs.en
dc.description.sponsorshipScience Foundation Ireland (18/CRT/6223)en
dc.description.statusPeer revieweden
dc.description.versionPublished Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.articleid33en
dc.identifier.citationLópez, J., Arbelaez, A. and Climent, L. (2022) 'Large Neighborhood Search for robust solutions for Constraint Satisfaction Problems with ordered domains', in Solnon, Christine (ed.) 28th International Conference on Principles and Practice of Constraint Programming (CP 2022), Haifa, Israel, 31 July- 8 September. doi: 10.4230/LIPIcs.CP.2022.33en
dc.identifier.doi10.4230/LIPIcs.CP.2022.33en
dc.identifier.endpage16en
dc.identifier.isbn978-3-95977-240-2
dc.identifier.issn1868-8969
dc.identifier.journaltitleLeibniz International Proceedings in Informatics (LIPIcs)en
dc.identifier.startpage1en
dc.identifier.urihttps://hdl.handle.net/10468/13451
dc.identifier.volume235en
dc.language.isoenen
dc.publisherSchloss Dagstuhl - Leibniz-Zentrum fur Informatiken
dc.relation.urihttps://drops.dagstuhl.de/opus/volltexte/2022/16662
dc.rights© 2022, the Authors. This is an open access publication, made available under the CC BY 4.0 International license.en
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subjectConstraint Programmingen
dc.subjectLarge Neighbourhood Searchen
dc.subjectRobust solutionsen
dc.titleLarge Neighborhood Search for robust solutions for Constraint Satisfaction Problems with ordered domainsen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LIPIcs-CP-2022-33.pdf
Size:
1007.6 KB
Format:
Adobe Portable Document Format
Description:
Published 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
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items