Abstract
Recent work have exhibited specific structure among combinatorial problem instances that could be used to speed up search or to help users understand the dynamic and static intimate structure of the problem being solved. Several Operations Research approaches apply decomposition or relaxation strategies upon such a structure identified within a given problem. The next step is to design algorithms that adaptatively integrate that kind of information during search. We claim in this paper, inspired by previous work on impact-based search strategies for constraint programming, that using an explanation-based constraint solver may lead to collect invaluable information on the intimate dynamic and static structure of a problem instance. We define several impact graphs to be used to design generic search guiding techniques and to identify hidden structures of instances. Finally, we discuss how dedicated OR solving strategies (such as Benders decomposition) could be adapted to constraint programming when specific relationships between variables are exhibited.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Achlioptas, D., Kirousis, L., Kranakis, E., Krizanc, D., Molloy, M., Stamatiou, Y.: Random constraint satisfaction: a more accurate picture. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 121–135. Springer, Heidelberg (1997)
Benders, J.F.: Partitionning procedures for solving mixed-variables programming problems. Numerische Mathematik 4, 238–252 (1962)
Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: Proceedings ECAI 2004, pp. 482–486 (2004)
Cambazard, H., Hladik, P.-E., Déplanche, A.-M., Jussien, N., Trinquet, Y.: Decomposition and learning for a real time task allocation problem. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 153–167. Springer, Heidelberg (2004)
Cleuziou, G., Martin, L., Vrain, C.: Disjunctive learning with a soft-clustering method. In: Horváth, T., Yamamoto, A. (eds.) ILP 2003. LNCS (LNAI), vol. 2835, pp. 75–92. Springer, Heidelberg (2003)
Ghoniem, M., Jussien, N., Fekete, J.-D.: VISEXP: visualizing constraint solver dynamics using explanations. In: Proceedings FLAIRS 2004, Miami, Florida, USA (May 2004)
Gomes, C.P., Selman, B., Crato, N.: Heavy-tailed distributions in combinatorial search. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 121–135. Springer, Heidelberg (1997)
Haralick, R., Elliot, G.: Increasing tree search efficiency for constraint satisfaction problems. Artificial intelligence 14(9), 263–313 (1980)
Hooker, J.N., Ottosson, G.: Logic-based benders decomposition. Mathematical Programming 96, 33–60 (2003)
Jain, V., Grossmann, I.E.: Algorithms for hybrid milp/cp models for a class of optimization problems. INFORMS Journal on Computing 13, 258–276 (2001)
Jussien, N.: The versatility of using explanations within constraint programming. Habilitation thesis, Université de Nantes, France (2003); also available as RR-03-04 research report at École des Mines de Nantes
Jussien, N., Barichard, V.: The PaLM system: explanation-based constraint programming. In: Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems, a post-conference workshop of CP 2000, pp. 118–133 (2000)
Jussien, N., Debruyne, R., Boizumault, P.: Maintaining arc-consistency within dynamic backtracking. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 249–261. Springer, Heidelberg (2000)
Jussien, N., Lhomme, O.: Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence 139(1), 21–45 (2002)
Prosser, P., Stergiou, K., Walsh, T.: Singleton consistencies. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 353–368. Springer, Heidelberg (2000)
Refalo, P.: Impact-based search strategies for constraint programming. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 557–571. Springer, Heidelberg (2004)
Williams, R., Gomes, C., Selman, B.: On the connections between backdoors and heavy-tails on combinatorial search. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919. Springer, Heidelberg (2004)
Williams, R., Gomes, C.P., Selman, B.: Backdoors to typical case complexity. In: Proceedings IJCAI 2003 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cambazard, H., Jussien, N. (2005). Identifying and Exploiting Problem Structures Using Explanation-Based Constraint Programming. In: Barták, R., Milano, M. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2005. Lecture Notes in Computer Science, vol 3524. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11493853_9
Download citation
DOI: https://doi.org/10.1007/11493853_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26152-0
Online ISBN: 978-3-540-32264-1
eBook Packages: Computer ScienceComputer Science (R0)