2026-07-21T14:17:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16662 2024-03-06T10:57:59Z ddc:004 open_access

Large Neighborhood Search for Robust Solutions for Constraint Satisfaction Problems with Ordered Domains López, Jheisson Arbelaez, Alejandro Climent, Laura Constraint Programming Large Neighbourhood Search Robust Solutions Often, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jheisson López and Alejandro Arbelaez and Laura Climent 2022 Is Part Of LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2022.33 urn:nbn:de:0030-drops-166625 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.33 eng https://creativecommons.org/licenses/by/4.0/legalcode