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.2023.9
URN: urn:nbn:de:0030-drops-190461
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19046/
Go to the corresponding LIPIcs Volume Portal

Audemard, Gilles ; Lecoutre, Christophe ; Prud'homme, Charles

Guiding Backtrack Search by Tracking Variables During Constraint Propagation

pdf-format:
LIPIcs-CP-2023-9.pdf (1 MB)

Abstract

It is well-known that variable ordering heuristics play a central role in solving efficiently Constraint Satisfaction Problem (CSP) instances. From the early 80’s, and during more than two decades, the dynamic variable ordering heuristic selecting the variable with the smallest domain was clearly prevailing. Then, from the mid 2000’s, some adaptive heuristics have been introduced: their principle is to collect some useful information during the search process in order to take better informed decisions. Among those adaptive heuristics, wdeg/dom (and its variants) remains particularly robust. In this paper, we introduce an original heuristic based on the midway processing of failing executions of constraint propagation: this heuristic called pick/dom tracks the variables that are directly involved in the process of constraint propagation, when ending with a conflict. The robustness of this new heuristic is demonstrated from a large experimentation conducted with the constraint solver ACE. Interestingly enough, one can observe some complementary between the early, midway and late forms of processing of conflicts.

BibTeX - Entry

@InProceedings{audemard_et_al:LIPIcs.CP.2023.9,
  author =	{Audemard, Gilles and Lecoutre, Christophe and Prud'homme, Charles},
  title =	{{Guiding Backtrack Search by Tracking Variables During Constraint Propagation}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19046},
  URN =		{urn:nbn:de:0030-drops-190461},
  doi =		{10.4230/LIPIcs.CP.2023.9},
  annote =	{Keywords: Variable Ordering Heuristics, Variable Weighting}
}

Keywords: Variable Ordering Heuristics, Variable Weighting
Collection: 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Issue Date: 2023
Date of publication: 22.09.2023

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