License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2022.33
URN: urn:nbn:de:0030-drops-166625
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16662/
Go to the corresponding LIPIcs Volume Portal

López, Jheisson ; Arbelaez, Alejandro ; Climent, Laura

Large Neighborhood Search for Robust Solutions for Constraint Satisfaction Problems with Ordered Domains

pdf-format:
LIPIcs-CP-2022-33.pdf (1.0 MB)

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.

BibTeX - Entry

@InProceedings{lopez_et_al:LIPIcs.CP.2022.33,
  author =	{L\'{o}pez, Jheisson and Arbelaez, Alejandro and Climent, Laura},
  title =	{{Large Neighborhood Search for Robust Solutions for Constraint Satisfaction Problems with Ordered Domains}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16662},
  URN =		{urn:nbn:de:0030-drops-166625},
  doi =		{10.4230/LIPIcs.CP.2022.33},
  annote =	{Keywords: Constraint Programming, Large Neighbourhood Search, Robust Solutions}
}

Keywords: Constraint Programming, Large Neighbourhood Search, Robust Solutions
Collection: 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Issue Date: 2022
Date of publication: 23.07.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI