DROPS

Document

DOI: 10.4230/LIPIcs.CP.2022.33

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

Authors: Jheisson López, Alejandro Arbelaez, and Laura Climent

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

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.

Cite as

Jheisson López, Alejandro Arbelaez, and Laura Climent. Large Neighborhood Search for Robust Solutions for Constraint Satisfaction Problems with Ordered Domains. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CP.2022.33},
  URN =		{urn:nbn:de:0030-drops-166625},
  doi =		{10.4230/LIPIcs.CP.2022.33},
  annote =	{Keywords: Constraint Programming, Large Neighbourhood Search, Robust Solutions}
}

Search Results

Documents authored by López, Jheisson

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

Abstract

Cite as

Thanks for your feedback!

Could not send message