Identifying and Exploiting Problem Structures Using Explanation-Based Constraint Programming
作者： Hadrien Cambazard , Narendra Jussien
DOI: 10.1007/11493853_9
关键词: Constraint programming 、 Graph 、 Constraint satisfaction dual problem 、 Constraint satisfaction problem 、 Theoretical computer science 、 Computer science 、 Relaxation (approximation) 、 Structure (mathematical logic) 、 Speedup 、 Constraint satisfaction 、 Artificial intelligence 、 Combinatorial optimization 、 Constrained optimization
摘要: Recent work have exhibited specific structure among combinatorial problem instances that could be used to speed up search or help users understand the dynamic and static intimate of being solved. Several Operations Research approaches apply decomposition relaxation strategies upon such a identified within given problem. The next step is design algorithms adaptatively integrate kind information during search. We claim in this paper, inspired by previous on impact-based for constraint programming, using an explanation-based solver may lead collect invaluable instance. define several impact graphs generic guiding techniques identify hidden structures instances. Finally, we discuss how dedicated OR solving (such as Benders decomposition) adapted programming when relationships between variables are exhibited.
springer.com
emn.fr
grenoble-inp.fr
archives-ouvertes.fr 参考文章(26)
Narendra Jussien, The versatility of using explanations within constraint programming Université de Nantes. ,(2003)
Narendra Jussien, Jean-Daniel Fekete, Mohammad Ghoniem, VISEXP: Visualizing Constraint Solver Dynamics Using Explanations. the florida ai research society. pp. 263- 268 ,(2004)
Christophe Lecoutre, Fred Hemery, Lakhdar Sais, Frédéric Boussemart, Boosting systematic search by weighting constraints european conference on artificial intelligence. pp. 146- 150 ,(2004)
Narendra Jussien, Vincent Barichard, The PaLM system: explanation-based constraint programming ,(2000)
B. Cabon, S. de Givry, L. Lobjois, T. Schiex, J.P. Warners, Radio Link Frequency Assignment Constraints - An International Journal. ,vol. 4, pp. 79- 89 ,(1999) , 10.1023/A:1009812409930
Guillaume Cleuziou, Lionel Martin, Christel Vrain, Disjunctive Learning with a Soft-Clustering Method inductive logic programming. pp. 75- 92 ,(2003) , 10.1007/978-3-540-39917-9_7
Hadrien Cambazard, Narendra Jussien, Integrating Benders Decomposition Within Constraint Programming Principles and Practice of Constraint Programming - CP 2005. pp. 752- 756 ,(2005) , 10.1007/11564751_58
Philippe Refalo, Impact-based search strategies for constraint programming principles and practice of constraint programming. pp. 557- 571 ,(2004) , 10.1007/978-3-540-30201-8_41
J.N. Hooker, G. Ottosson, Logic-based Benders decomposition Mathematical Programming. ,vol. 96, pp. 33- 60 ,(2003) , 10.1007/S10107-003-0375-9
Hadrien Cambazard, Pierre-Emmanuel Hladik, Anne-Marie Déplanche, Narendra Jussien, Yvon Trinquet, Decomposition and learning for a hard real time task allocation problem principles and practice of constraint programming. ,vol. 3258, pp. 153- 167 ,(2004) , 10.1007/978-3-540-30201-8_14