# Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS

Mathieu Fontaine; Samir Loudni; Patrice Boizumault

RAIRO - Operations Research - Recherche Opérationnelle (2013)

- Volume: 47, Issue: 2, page 91-123
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topFontaine, Mathieu, Loudni, Samir, and Boizumault, Patrice. "Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS." RAIRO - Operations Research - Recherche Opérationnelle 47.2 (2013): 91-123. <http://eudml.org/doc/275098>.

@article{Fontaine2013,

abstract = {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.},

author = {Fontaine, Mathieu, Loudni, Samir, Boizumault, Patrice},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {variable neighborhood search; tree decomposition; maximum cardinality search; cost functions netwok; constraint propagation},

language = {eng},

number = {2},

pages = {91-123},

publisher = {EDP-Sciences},

title = {Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS},

url = {http://eudml.org/doc/275098},

volume = {47},

year = {2013},

}

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

PB - EDP-Sciences

VL - 47

IS - 2

SP - 91

EP - 123

AB - 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.

LA - eng

KW - variable neighborhood search; tree decomposition; maximum cardinality search; cost functions netwok; constraint propagation

UR - http://eudml.org/doc/275098

ER -

## References

top- [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 Methods8 (1987) 277–284. Zbl0611.05022MR881187
- [3] E. Balas and J. Xue, Weighted and unweighted maximum clique algorithms with upper bounds from fractional colorings. Algorithmica15 (1996) 397–412. Zbl0846.68078MR1379149
- [4] E. Bensana, M. Lemaître and G. Verfaillie, Earth observation satellite management. Constraints4 (1999) 293–299. Zbl0963.90507
- [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. Constraints4 (1999) 79–89. Zbl1020.94500
- [8] L.R. Cardon and G.R. Abecasis, Using haplotype blocks to map human complex trait loci. Trends Genetics19 (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. Zbl1213.68580MR2642294
- [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. Zbl0665.68084MR988482
- [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. B16 (1974) 47–56. Zbl0266.05101MR332541
- [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. Zbl1281.68097
- [18] G. Gottlob, Z. Miklós and T. Schwentick, Generalized hypertree decompositions: Np–hardness and tractable variants. J. ACM 56 (2009). Zbl1325.68097MR2572931
- [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. Heuristics7 (2001) 335–350. Zbl1041.68623
- [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. Zbl1186.68328MR2154596
- [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. Zbl1086.68592MR2102539
- [28] S. Loudni and P. Boizumault, Combining VNS with constraint programming for solving anytime optimization problems. EJOR191 (2008) 705–735. Zbl1160.90661
- [29] R. Marinescu and R. Dechter, AND/OR branch-and-bound search for combinatorial optimization in graphical models. Artif. Intell.173 (2009) 1457–1491. Zbl1185.68648MR2724369
- [30] N. Mladenovic and P. Hansen. Variable neighborhood search. Comput. Oper. Res.24 (1997) 1097–1100. Zbl0889.90119MR1471346
- [31] B. Neveu, G. Trombettoni and F. Glover, ID Walk: A candidate list strategy with a simple diversification device. in Wallace [45] 423–437. Zbl1152.68568
- [32] C. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes. J. Comput. Syst. Sci.43 (1991) 425–440. Zbl0765.68036MR1135471
- [33] J. Pearl, Probabilistic inference in intelligent systems, in Networks of Plausible Inference. Morgan Kaufmann (1998). Zbl0746.68089MR965765
- [34] L. Perron, P. Shaw and V. Furnon, Propagation guided large neighborhood search, in Wallace [45] 468–481. Zbl1152.68572
- [35] Z.S. Qin, S. Gopalakrishnan and G.R. Abecasis, An efficient comprehensive search algorithm for tagsnp selection using linkage disequilibrium criteria. Bioinformatics22 (2006) 220–225.
- [36] I. Rish and R. Dechter, Resolution versus search: Two strategies for sat. J. Autom. Reason.24 (2000) 225–275. Zbl0967.68147MR1750264
- [37] N. Robertson and P.D. Seymour, Graph minors. ii. algorithmic aspects of tree–width. J. Algorithms 7 (1986) 309–322. Zbl0611.05017MR855559
- [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. Constraints13 (2008) 130–154. Zbl1144.92324MR2398980
- [40] T. Sandholm, An algorithm for optimal winner determination in combinatorial auctions, in IJCAI’99 (1999) 342–347. Zbl0984.68039
- [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. Zbl0545.68062MR749707
- [43] C. Terrioux and P. Jégou, Hybrid backtracking bounded by tree–decomposition of constraint networks. Artif. Intell.146 (2003) 43–75. Zbl1082.68803MR1980789
- [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).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.