Tree decomposition introduced by Robertson and Seymour aims to decompose a problem into clusters constituting an acyclic graph. There are works exploiting tree decomposition for complete search methods. In this paper, we show how tree decomposition can be used to efficiently guide local search methods that use large neighborhoods like VNS. We propose DGVNS (Decomposition Guided VNS) which uses the graph of clusters in order to build neighborhood structures enabling better diversification and intensification. Second, we introduce tightness dependent tree decomposition which allows to take advantage of both the structure of the problem and the constraints tightness. Third, experiments performed on random instances (GRAPH) and real life instances (CELAR, SPOT5 and tagSNP) show the appropriateness and the efficiency of our approach. Moreover, we study and discuss the influence of the width of the tree decomposition on our approach and the relevance of removing clusters with very few proper variables from the tree decomposition.
Mots-clés : variable neighborhood search, tree decomposition, maximum cardinality search, cost functions netwok, constraint propagation
@article{RO_2013__47_2_91_0,
author = {Fontaine, Mathieu and Loudni, Samir and Boizumault, Patrice},
title = {Exploiting {Tree} {Decomposition} for {Guiding} {Neighborhoods} {Exploration} for {VNS}},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {91--123},
publisher = {EDP-Sciences},
volume = {47},
number = {2},
year = {2013},
doi = {10.1051/ro/2013030},
mrnumber = {3055154},
zbl = {1267.68211},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2013030/}
}
TY - JOUR AU - Fontaine, Mathieu AU - Loudni, Samir AU - Boizumault, Patrice TI - Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2013 SP - 91 EP - 123 VL - 47 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2013030/ DO - 10.1051/ro/2013030 LA - en ID - RO_2013__47_2_91_0 ER -
%0 Journal Article %A Fontaine, Mathieu %A Loudni, Samir %A Boizumault, Patrice %T Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS %J RAIRO - Operations Research - Recherche Opérationnelle %D 2013 %P 91-123 %V 47 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2013030/ %R 10.1051/ro/2013030 %G en %F RO_2013__47_2_91_0
Fontaine, Mathieu; Loudni, Samir; Boizumault, Patrice. Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS. RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 2, pp. 91-123. doi : 10.1051/ro/2013030. http://www.numdam.org/articles/10.1051/ro/2013030/
[1] http://www-sop.inria.fr/coprin/neveu/incop/presentation-incop.html.
[2] , and , Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods 8 (1987) 277-284. | MR | Zbl
[3] and , Weighted and unweighted maximum clique algorithms with upper bounds from fractional colorings. Algorithmica 15 (1996) 397-412. | MR | Zbl
[4] , and , Earth observation satellite management. Constraints 4 (1999) 293-299. | Zbl
[5] , , , and , Exact and approximate methods for the daily management of an earth observation satellite, in Proc. of the 4th International Symposium on Space Mission Operations and Ground Data Systems (SpaceOps-9-) (1996).
[6] , editor. IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009 (2009).
[7] , , , and , Radio link frequency assignment. Constraints 4 (1999) 79-89. | Zbl
[8] and , Using haplotype blocks to map human complex trait loci. Trends Genetics 19 (2003) 135-140.
[9] , , , , and , Soft arc consistency revisited. Artif. Intell. 174 (2010) 449-478. | MR | Zbl
[10] , , and , Existential arc consistency: Getting closer to full arc consistency in weighted CSPs. IJCAI (2005) 84-89.
[11] , and , Exploiting tree decomposition and soft local consistency in weighted CSP. AAAI Press (2006) 22-27.
[12] Simon. de Givry, Rapport d'habilitation à diriger les recherches. INRA UBIA Toulouse (2011).
[13] and , Tree clustering for constraint networks. Artif. Intell. 38 (1989) 353-366. | MR | Zbl
[14] et al. Selecting a maximally informative set of single-nucleotide polymorphisms for association analyses using linkage disequilibrium. Am. J. Hum. Genet. 74 (2004) 106-120.
[15] , and , Guiding VNS with tree decomposition. ICTAI. IEEE (2011) 505-512.
[16] , The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16 (1974) 47-56. | MR | Zbl
[17] , and , Size and treewidth bounds for conjunctive queries, in edited by Jan Paredaens and Jianwen Su. PODS ACM (2009) 45-54. | Zbl
[18] , and , Generalized hypertree decompositions: Np-hardness and tractable variants. J. ACM 56 (2009). | MR
[19] , and , Tractable database design through bounded treewidth, in PODS, edited by Stijn Vansummeren. ACM (2006) 124-133.
[20] , and , Variable neighborhood decomposition search. J. Heuristics 7 (2001) 335-350. | Zbl
[21] and , Limited discrepancy search, in IJCAI (1). Morgan Kaufmann (1995) 607-615.
[22] , and , Computing and exploiting tree-decompositions for solving constraint networks, in CP, edited by Peter van Beek. Springer. Lect. Notes Comput. Sci. 3709 (2005) 777-781.
[23] , and , Strategies and heuristics for exploiting tree-decompositions of constraint networks, in Inference methods based on graphical structures of knowledge (WIGSK'06) (2006) 13-18.
[24] and , Exploiting decomposition on constraint problems with high tree-width, in Boutilier [6] 525-531.
[25] , and , Treewidth: Computational experiments. Electr. Notes Discrete Math. 8 (2001) 54-57. | MR | Zbl
[26] and , In the quest of the best form of local consistency for weighted CSP, in IJCAI (2003) 239-244.
[27] and , Solving weighted CSP by maintaining arc consistency. Artif. Intell. 159 (2004) 1-26. | MR | Zbl
[28] and , Combining VNS with constraint programming for solving anytime optimization problems. EJOR 191 (2008) 705-735. | Zbl
[29] and , AND/OR branch-and-bound search for combinatorial optimization in graphical models. Artif. Intell. 173 (2009) 1457-1491. | MR | Zbl
[30] and . Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097-1100. | MR | Zbl
[31] , and , ID Walk: A candidate list strategy with a simple diversification device. in Wallace [45] 423-437. | Zbl
[32] and , Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43 (1991) 425-440. | MR | Zbl
[33] , Probabilistic inference in intelligent systems, in Networks of Plausible Inference. Morgan Kaufmann (1998). | MR
[34] , and , Propagation guided large neighborhood search, in Wallace [45] 468-481. | Zbl
[35] , and , An efficient comprehensive search algorithm for tagsnp selection using linkage disequilibrium criteria. Bioinformatics 22 (2006) 220-225.
[36] and , Resolution versus search: Two strategies for sat. J. Autom. Reason. 24 (2000) 225-275. | MR | Zbl
[37] and , Graph minors. ii. algorithmic aspects of tree-width. J. Algorithms 7 (1986) 309-322. | MR | Zbl
[38] , , and , Russian doll search with tree decomposition, in Boutilier [6] 603-608.
[39] , and , Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques. Constraints 13 (2008) 130-154. | MR | Zbl
[40] , An algorithm for optimal winner determination in combinatorial auctions, in IJCAI'99 (1999) 342-347. | Zbl
[41] , Using constraint programming and local search methods to solve vehicle routing problems, in CP, edited by M.J. Maher and J.-F. Puget. Springer. Lect. Notes Comput. Sci. 1520 (1998) 417-431.
[42] and . Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13 (1984) 566-579. | MR | Zbl
[43] and , Hybrid backtracking bounded by tree-decomposition of constraint networks. Artif. Intell. 146 (2003) 43-75. | MR | Zbl
[44] , GRAPH: Generating radiolink frequency assignment problems heuristically. Master Thesis, Delft Univ. Technol, The Netherlands (1995).
[45] , editor. Principles and Practice of Constraint Programming - CP 2004, 10th International Conference, CP 2004, Toronto, Canada, September 27 - October 1, 2004, Proceedings. Springer. Lect. Notes Comput. Sci. 3258 (2004).
Cité par Sources :
