Explanations for identifying and exploiting structures within combinatorial problems
Hadrien Cambazard; Narendra Jussien
RAIRO - Operations Research (2007)
- Volume: 40, Issue: 4, page 381-401
- ISSN: 0399-0559
Access Full Article
topAbstract
topHow to cite
topReferences
top- D. Achlioptas, L. Kirousis, E. Kranakis, D. Krizanc, M. Molloy and Y. Stamatiou, Random constraint satisfaction: a more accurate picture, in Proceedings CP 1997, Linz, Austria (1997) 121–135.
- J.F. Benders, Partitionning procedures for solving mixed-variables programming problems. Numer. Math.4 (1962) 238–252.
- C. Bessière, A. Chmeiss and L. Saïs, Neighborhood-based variable ordering heuristics for the constraint satisfaction problem, in Proceeding CP'01, Paphos, Cyprus (2001) 565–569. Short paper.
- C. Bessiere and J.C. Regin, MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems, in Proceeding CP'96 (1996) 61–75.
- F. Boussemart, F. Hemery, C. Lecoutre and L. Sais, Boosting systematic search by weighting constraints, in Proceedings ECAI'04 (2004) 482–486.
- B. Cabon, S. de Givry, L. Lobjois, T. Schiex and J.P. Warners, Radio Link Frequency Assignment. Constraints4 (1999) 79–89.
- H. Cambazard, P.-E. Hladik, A.-M. Déplanche, N. Jussien and Y. Trinquet, Decomposition and learning for a real time task allocation problem, in Proceedings CP 2004 (2004) 153–167.
- H. Cambazard and N. Jussien, Integrating Benders decomposition within Constraint Programming, in Proceedings CP 2005 (2005) 752–756. Short paper.
- G. Cleuziou, L. Martin and C. Vrain, Disjunctive learning with a soft-clustering method, in ILP'03:13th International Conference on Inductive Logic Programming, LNCS, September (2003) 75–92.
- A.M. Geoffrion, Generalized Benders Decomposition. J. Optim. Theory Practice10 (1972) 237–260.
- M. Ghoniem, N. Jussien and J.-D. Fekete, VISEXP: visualizing constraint solver dynamics using explanations, in Proceedings FLAIRS'04, Miami, Florida, USA, May (2004) 263–268.
- C.P. Gomes, B.t Selman and N. Crato, Heavy-tailed distributions in combinatorial search, in Proceeding CP 97, Linz, Austria (1997) 121–135.
- R. Haralick and G. Elliot, Increasing tree search efficiency for constraint satisfaction problems. Artificial intelligence14 (1980) 263–313.
- J.N. Hooker and G. Ottosson, Logic-based benders decomposition. Math. Program.96 (2003) 33–60.
- V. Jain and I.E. Grossmann, Algorithms for hybrid MILP/CP models for a class of optimization problems. Informs J. Comput.13 (2001) 258–276.
- N. Jussien, The versatility of using explanations within constraint programming. Habilitation thesis, Université de Nantes, France, also available as RR-03-04 research report at École des Mines de Nantes (2003).
- N. Jussien and V. Barichard, The PaLM system: explanation-based constraint programming, in Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems, a post-conference workshop of CP 2000, Singapore (2000) 118–133.
- N. Jussien, R. Debruyne and P. Boizumault, Maintaining arc-consistency within dynamic backtracking, in Proceedings CP 2000, edited by R. Dechter, Singapore (2000) 249–261.
- N. Jussien and O. Lhomme, Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence139 (2002) 21–45.
- R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman and L. Troyanski, Determining computational complexity for characteristic `phase transitions', in Nature400 (1999) 133–137.
- P. Prosser, MAC-CBJ: maintaining arc-consistency with conflict-directed backjumping. Research report 95/177, Department of Computer Science – University of Strathclyde (2005).
- P. Prosser, K. Stergiou and T. Walsh, Singleton consistencies, in Proceedings CP 2000, edited by R. Dechter, Singapore (2000) 353–368.
- P. Refalo, Impact-based search strategies for constraint programming, in Proceedings CP 2004, Toronto, Canada (2004) 556–571.
- J.-C. Régin, A filtering algorithm for constraints of difference in CSPs, in AAAI 94, Twelth National Conference on Artificial Intelligence, Seattle, Washington (1994) 362–367.
- R. Williams, C. Gomes and B. Selman, On the connections between backdoors and heavy-tails on combinatorial search, in the International Conference on Theory and Applications of Satisfiability Testing (SAT) (2003).
- Ryan Williams, Carla P. Gomes, and Bart Selman. Backdoors to typical case complexity, in Proceedings IJCAI 2003 (2003).