1 Search Results for "López, Jheisson"


Document
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}
}
  • Refine by Author
  • 1 Arbelaez, Alejandro
  • 1 Climent, Laura
  • 1 López, Jheisson

  • Refine by Classification
  • 1 Computing methodologies → Artificial intelligence

  • Refine by Keyword
  • 1 Constraint Programming
  • 1 Large Neighbourhood Search
  • 1 Robust Solutions

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail