Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS
RAIRO - Operations Research - Recherche Opérationnelle, Volume 47 (2013) no. 2, pp. 91-123.

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.

DOI: 10.1051/ro/2013030
Classification: 68T20
Keywords: 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://archive.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://archive.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://archive.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, Volume 47 (2013) no. 2, pp. 91-123. doi : 10.1051/ro/2013030. http://archive.numdam.org/articles/10.1051/ro/2013030/

[1] http://www-sop.inria.fr/coprin/neveu/incop/presentation-incop.html.

[2] S. Arnborg, D.G. Corneil and A. Proskurowski, Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods 8 (1987) 277-284. | MR | Zbl

[3] E. Balas and J. Xue, Weighted and unweighted maximum clique algorithms with upper bounds from fractional colorings. Algorithmica 15 (1996) 397-412. | MR | Zbl

[4] E. Bensana, M. Lemaître and G. Verfaillie, Earth observation satellite management. Constraints 4 (1999) 293-299. | Zbl

[5] E. Bensana, G. Verfaillie, J.C. Agnèse, N. Bataille and D. Blumstein, 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] C. Boutilier, editor. IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009 (2009).

[7] B. Cabon, S. De Givry, L. Lobjois, T. Schiex and J.P. Warners, Radio link frequency assignment. Constraints 4 (1999) 79-89. | Zbl

[8] L.R. Cardon and G.R. Abecasis, Using haplotype blocks to map human complex trait loci. Trends Genetics 19 (2003) 135-140.

[9] M. C. Cooper, S. De Givry, M. Sánchez, T. Schiex, M. Zytnicki and T. Werner, Soft arc consistency revisited. Artif. Intell. 174 (2010) 449-478. | MR | Zbl

[10] S. De Givry, F. Heras, M. Zytnicki and J. Larrosa, Existential arc consistency: Getting closer to full arc consistency in weighted CSPs. IJCAI (2005) 84-89.

[11] S. De Givry, T. Schiex and G. Verfaillie, 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] R. Dechter and J. Pearl, Tree clustering for constraint networks. Artif. Intell. 38 (1989) 353-366. | MR | Zbl

[14] C.S. Carlson 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] M. Fontaine, S. Loudni and P. Boizumault, Guiding VNS with tree decomposition. ICTAI. IEEE (2011) 505-512.

[16] F. Gavri, The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16 (1974) 47-56. | MR | Zbl

[17] G. Gottlob, S.T. Lee and G. Valiant, Size and treewidth bounds for conjunctive queries, in edited by Jan Paredaens and Jianwen Su. PODS ACM (2009) 45-54. | Zbl

[18] G. Gottlob, Z. Miklós and T. Schwentick, Generalized hypertree decompositions: Np-hardness and tractable variants. J. ACM 56 (2009). | MR

[19] G. Gottlob, R. Pichler and F. Wei, Tractable database design through bounded treewidth, in PODS, edited by Stijn Vansummeren. ACM (2006) 124-133.

[20] P. Hansen, N. Mladenovic and D. Perez-Brito, Variable neighborhood decomposition search. J. Heuristics 7 (2001) 335-350. | Zbl

[21] W.D. Harvey and M.L. Ginsberg, Limited discrepancy search, in IJCAI (1). Morgan Kaufmann (1995) 607-615.

[22] P. Jégou, S. Ndiaye and C. Terrioux, 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] Ph. Jégou, S. Ndiaye and C. Terrioux, 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] M. Kitching and F. Bacchus, Exploiting decomposition on constraint problems with high tree-width, in Boutilier [6] 525-531.

[25] A.M.C.A. Koster, H.L. Bodlaender and S.P.M. Van Hoesel, Treewidth: Computational experiments. Electr. Notes Discrete Math. 8 (2001) 54-57. | MR | Zbl

[26] J. Larrosa and T. Schiex, In the quest of the best form of local consistency for weighted CSP, in IJCAI (2003) 239-244.

[27] J. Larrosa and T. Schiex, Solving weighted CSP by maintaining arc consistency. Artif. Intell. 159 (2004) 1-26. | MR | Zbl

[28] S. Loudni and P. Boizumault, Combining VNS with constraint programming for solving anytime optimization problems. EJOR 191 (2008) 705-735. | Zbl

[29] R. Marinescu and R. Dechter, AND/OR branch-and-bound search for combinatorial optimization in graphical models. Artif. Intell. 173 (2009) 1457-1491. | MR | Zbl

[30] N. Mladenovic and P. Hansen. Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097-1100. | MR | Zbl

[31] B. Neveu, G. Trombettoni and F. Glover, ID Walk: A candidate list strategy with a simple diversification device. in Wallace [45] 423-437. | Zbl

[32] C. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43 (1991) 425-440. | MR | Zbl

[33] J. Pearl, Probabilistic inference in intelligent systems, in Networks of Plausible Inference. Morgan Kaufmann (1998). | MR

[34] L. Perron, P. Shaw and V. Furnon, Propagation guided large neighborhood search, in Wallace [45] 468-481. | Zbl

[35] Z.S. Qin, S. Gopalakrishnan and G.R. Abecasis, An efficient comprehensive search algorithm for tagsnp selection using linkage disequilibrium criteria. Bioinformatics 22 (2006) 220-225.

[36] I. Rish and R. Dechter, Resolution versus search: Two strategies for sat. J. Autom. Reason. 24 (2000) 225-275. | MR | Zbl

[37] N. Robertson and P.D. Seymour, Graph minors. ii. algorithmic aspects of tree-width. J. Algorithms 7 (1986) 309-322. | MR | Zbl

[38] M. Sánchez, D. Allouche, S. De Givry and T. Schiex, Russian doll search with tree decomposition, in Boutilier [6] 603-608.

[39] M. Sánchez, S. De Givry and T. Schiex, Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques. Constraints 13 (2008) 130-154. | MR | Zbl

[40] T. Sandholm, An algorithm for optimal winner determination in combinatorial auctions, in IJCAI'99 (1999) 342-347. | Zbl

[41] P. Shaw, 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] R.E. Tarjan and M. Yannakakis. 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] C. Terrioux and P. Jégou, Hybrid backtracking bounded by tree-decomposition of constraint networks. Artif. Intell. 146 (2003) 43-75. | MR | Zbl

[44] H. Van Benthem, GRAPH: Generating radiolink frequency assignment problems heuristically. Master Thesis, Delft Univ. Technol, The Netherlands (1995).

[45] M. Wallace, 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).

Cited by Sources: