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

Abstract

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

How to cite

top

Fontaine, 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. [1] http://www-sop.inria.fr/coprin/neveu/incop/presentation-incop.html. 
  2. [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. [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. [4] E. Bensana, M. Lemaître and G. Verfaillie, Earth observation satellite management. Constraints4 (1999) 293–299. Zbl0963.90507
  5. [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. [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. [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. [8] L.R. Cardon and G.R. Abecasis, Using haplotype blocks to map human complex trait loci. Trends Genetics19 (2003) 135–140. 
  9. [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. [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. [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. [12] Simon. de Givry, Rapport d’habilitation à diriger les recherches. INRA UBIA Toulouse (2011). 
  13. [13] R. Dechter and J. Pearl, Tree clustering for constraint networks. Artif. Intell.38 (1989) 353–366. Zbl0665.68084MR988482
  14. [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. [15] M. Fontaine, S. Loudni and P. Boizumault, Guiding VNS with tree decomposition. ICTAI. IEEE (2011) 505–512. 
  16. [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. [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. [18] G. Gottlob, Z. Miklós and T. Schwentick, Generalized hypertree decompositions: Np–hardness and tractable variants. J. ACM 56 (2009). Zbl1325.68097MR2572931
  19. [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. [20] P. Hansen, N. Mladenovic and D. Perez-Brito, Variable neighborhood decomposition search. J. Heuristics7 (2001) 335–350. Zbl1041.68623
  21. [21] W.D. Harvey and M.L. Ginsberg, Limited discrepancy search, in IJCAI (1). Morgan Kaufmann (1995) 607–615. 
  22. [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. [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. [24] M. Kitching and F. Bacchus, Exploiting decomposition on constraint problems with high tree–width, in Boutilier [6] 525–531. 
  25. [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. [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. [27] J. Larrosa and T. Schiex, Solving weighted CSP by maintaining arc consistency. Artif. Intell.159 (2004) 1–26. Zbl1086.68592MR2102539
  28. [28] S. Loudni and P. Boizumault, Combining VNS with constraint programming for solving anytime optimization problems. EJOR191 (2008) 705–735. Zbl1160.90661
  29. [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. [30] N. Mladenovic and P. Hansen. Variable neighborhood search. Comput. Oper. Res.24 (1997) 1097–1100. Zbl0889.90119MR1471346
  31. [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. [32] C. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes. J. Comput. Syst. Sci.43 (1991) 425–440. Zbl0765.68036MR1135471
  33. [33] J. Pearl, Probabilistic inference in intelligent systems, in Networks of Plausible Inference. Morgan Kaufmann (1998). Zbl0746.68089MR965765
  34. [34] L. Perron, P. Shaw and V. Furnon, Propagation guided large neighborhood search, in Wallace [45] 468–481. Zbl1152.68572
  35. [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. [36] I. Rish and R. Dechter, Resolution versus search: Two strategies for sat. J. Autom. Reason.24 (2000) 225–275. Zbl0967.68147MR1750264
  37. [37] N. Robertson and P.D. Seymour, Graph minors. ii. algorithmic aspects of tree–width. J. Algorithms 7 (1986) 309–322. Zbl0611.05017MR855559
  38. [38] M. Sánchez, D. Allouche, S. de Givry and T. Schiex, Russian doll search with tree decomposition, in Boutilier [6] 603–608. 
  39. [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. [40] T. Sandholm, An algorithm for optimal winner determination in combinatorial auctions, in IJCAI’99 (1999) 342–347. Zbl0984.68039
  41. [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. [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. [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. [44] H. van Benthem, GRAPH: Generating radiolink frequency assignment problems heuristically. Master Thesis, Delft Univ. Technol, The Netherlands (1995). 
  45. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.