Explanation-Based Weighted Degree

被引：14
作者：
Hebrard, Emmanuel [1 ]
Siala, Mohamed [2 ]
机构：
[1] Univ Toulouse, CNRS, LAAS, CNRS, Toulouse, France
[2] Univ Coll Cork, Dept Comp Sci, Insight Ctr Data Analyt, Cork, Ireland
来源：
INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING, CPAIOR 2017 | 2017年 / 10335卷
关键词：
VARIABLE SELECTION; STRATEGIES; SEARCH;
D O I：
10.1007/978-3-319-59776-8_13
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
The weighted degree heuristic is among the state of the art generic variable ordering strategies in constraint programming. However, it was often observed that when using large arity constraints, its efficiency deteriorates significantly since it loses its ability to discriminate variables. A possible answer to this drawback is to weight a conflict set rather than the entire scope of a failed constraint. We implemented this method for three common global constraints (AllDifferent, Linear Inequality and Element) and evaluate it on instances from the MiniZinc Challenge. We observe that even with simple explanations, this method outperforms the standardWeighted Degree heuristic.
引用
收藏
页码：167 / 175
页数：9
相关论文
共 16 条
  • [11] Moskewicz MW, 2001, DES AUT CON, P530, DOI 10.1109/DAC.2001.935565
  • [12] Refalo P, 2004, LECT NOTES COMPUT SC, V3258, P557
  • [13] SCHIEX T, 1993, FIFTH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE, TAI '93, PROCEEDINGS, P48, DOI 10.1109/TAI.1993.633935
  • [14] Silva JPM, 1996, IEEE IC CAD, P220, DOI 10.1109/ICCAD.1996.569607
  • [15] The MiniZinc Challenge 2008-2013
    Stuckey, Peter J.
    Feydy, Thibaut
    Schutt, Andreas
    Tack, Guido
    Fischer, Julien
    [J]. AI MAGAZINE, 2014, 35 (02) : 55 - 60
  • [16] Experimental studies of variable selection strategies based on constraint weights
    Wallace, Richard J.
    Grimes, Diarmuid
    [J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2008, 63 (1-3): : 114 - 129
12