Large Neighborhood Search for robust solutions for Constraint Satisfaction Problems with ordered domains
| Autor: | López, Jheisson, Arbelaez, Alejandro, Climent, Laura |
|---|---|
| Přispěvatelé: | Solnon, Christine |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| Popis: | 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. LIPIcs, Vol. 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022), pages 33:1-33:16 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|