Refining Constraint Weighting
| Autor: | Christophe Lecoutre, Hugues Wattez, Anastasia Paparrizou, Sébastien Tabary |
|---|---|
| Přispěvatelé: | Centre de Recherche en Informatique de Lens (CRIL), Université d'Artois (UA)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
constraint weighting
Mathematical optimization 021103 operations research Computer science Heuristic Backtracking search heuristics constraint satisfaction 0211 other engineering and technologies 02 engineering and technology Constraint satisfaction Arity Weighting [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Constraint (information theory) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Heuristics Constraint satisfaction problem |
| Zdroj: | 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI) ICTAI 2019: IEEE 31st International Conference on Tools with Artificial Intelligence ICTAI 2019: IEEE 31st International Conference on Tools with Artificial Intelligence, Nov 2019, Portland, United States. ⟨10.1109/ICTAI.2019.00019⟩ ICTAI |
| DOI: | 10.1109/ICTAI.2019.00019⟩ |
| Popis: | International audience; Backtracking search is a complete approach that is traditionally used to solve instances modeled as constraint satisfaction problems. The space explored during search depends dramatically on the order that variables are instantiated. Considering that a perfect variable ordering might result to a backtrack-free search (i.e., finding backdoors, cycle cutsets), finding heuristics for variable ordering has always attracted research interest. For fifteen years, constraint weighting has been shown to be a successful approach for guiding backtrack search. In this paper, we show how the popular generic variable ordering heuristic dom/wdeg can be made more robust by taking finer information at each conflict: the "current" arity of the failing constraint as well as the size of the current domains of the variables involved in that constraint. Our experimental results show the practical interest of this refined variant of constraint weighting. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|