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

Loading...
Thumbnail Image
Files
LIPIcs-CP-2022-33.pdf(1007.6 KB)
Published Version
Date
2022-07-23
Authors
López, Jheisson
Arbelaez, Alejandro
Climent, Laura
Journal Title
Journal ISSN
Volume Title
Publisher
Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
Research Projects
Organizational Units
Journal Issue
Abstract
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.
Description
Keywords
Constraint Programming , Large Neighbourhood Search , Robust solutions
Citation
Ló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.33