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 条

[1] Bayardo Jr R. J., 1997, P 14 NAT C ART INT 9, P203
[2] Boussemart F, 2004, FRONT ARTIF INTEL AP, V110, P146
[3] Conflict Ordering Search for Scheduling Problems
Gay, Steven
Hartert, Renaud
Lecoutre, Christophe
Schaus, Pierre
[J]. PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2015, 2015, 9255 : 140 - 148
[4] Grimes D, 2007, LECT NOTES COMPUT SC, V4741, P831
[5] Haralick R.M., 1979, Proceedings of the 6th International Joint Conference on Artificial Intelligence, P356
[6] Hebrard E., 2008, P 3 INT CSP SOLV COM, P31
[7] Reasoning from last conflict(s) in constraint programming
Lecoutre, Christophe
Sais, Lakhdar
Tabary, Sebastien
Vidal, Vincent
[J]. ARTIFICIAL INTELLIGENCE, 2009, 173 (18) : 1592 - 1614
[8] Lopez-Ortiz A., 2003, P 18 INT JOINT C ART, P245
[9] GRASP: A search algorithm for propositional satisfiability
Marques-Silva, JP
Sakallah, KA
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1999, 48 (05) : 506 - 521
[10] Michel Laurent, 2012, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Proceedings 9th International Conference, CPAIOR 2012, P228, DOI 10.1007/978-3-642-29828-8_15

← 1 2 →