On combining variable ordering heuristics for constraint satisfaction problems

Hongbo Li (), Guozhong Feng and Minghao Yin ()
Additional contact information
Hongbo Li: Northeast Normal University
Guozhong Feng: Northeast Normal University
Minghao Yin: Northeast Normal University

Journal of Heuristics, 2020, vol. 26, issue 4, No 1, 453-474

Abstract: Abstract Variable ordering heuristics play a central role in solving constraint satisfaction problems. Combining two variable ordering heuristics may generate a more efficient heuristic, such as dom/deg. In this paper, we propose a novel method for combining two variable ordering heuristics, namely Pearson-Correlation-Coefficient-based Combination (PCCC). While the existing combination strategies always combine participant heuristics, PCCC checks whether the participant heuristics are suitable for combination before combining them in the context of search. If they should be combined, it combines the heuristic scores to select a variable to branch on, otherwise, it randomly selects one of the participant heuristics to make the decision. The experiments on various benchmark problems show that PCCC can be used to combine different pairs of heuristics, and it is more robust than the participant heuristics and some classical combining strategies.

Keywords: Constraint satisfaction problem; Variable ordering heuristic; Activity-based search; Dom/wdeg; Impact-based search (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-019-09434-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:26:y:2020:i:4:d:10.1007_s10732-019-09434-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-019-09434-9

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().