Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-06T05:27:37.588Z Has data issue: false hasContentIssue false
  • English
  • Français

Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS

Published online by Cambridge University Press:  18 April 2013

Mathieu Fontaine ,
Samir Loudni  and
Patrice Boizumault
Mathieu Fontaine
Affiliation:
Universitéde Caen Basse-Normandie, CNRS, UMR 6072 GREYC, 14032 Caen, France. [email protected]
Samir Loudni
Affiliation:
Universitéde Caen Basse-Normandie, CNRS, UMR 6072 GREYC, 14032 Caen, France. [email protected]
Patrice Boizumault
Affiliation:
Universitéde Caen Basse-Normandie, CNRS, UMR 6072 GREYC, 14032 Caen, France. [email protected]
Get access

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.

Keywords

Variable neighborhood searchtree decompositionmaximum cardinality searchcost functions netwokconstraint propagation
Type
Research Article
Information
RAIRO - Operations Research , Volume 47 , Issue 2: ConstraintProgramming , April 2013 , pp. 91 - 123
Copyright
© EDP Sciences, ROADEF, SMAI, 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

http://www-sop.inria.fr/coprin/neveu/incop/presentation-incop.html.
Arnborg, S., Corneil, D.G. and Proskurowski, A., Complexity of finding embeddings in a k–tree. SIAM J. Algebraic Discrete Methods 8 (1987) 277–284. Google Scholar
Balas, E. and Xue, J., Weighted and unweighted maximum clique algorithms with upper bounds from fractional colorings. Algorithmica 15 (1996) 397–412. Google Scholar
Bensana, E., Lemaître, M. and Verfaillie, G., Earth observation satellite management. Constraints 4 (1999) 293–299. Google Scholar
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).
C. Boutilier, editor. IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009 (2009).
Cabon, B., de Givry, S., Lobjois, L., Schiex, T. and Warners, J.P., Radio link frequency assignment. Constraints 4 (1999) 79–89. Google Scholar
Cardon, L.R. and Abecasis, G.R., Using haplotype blocks to map human complex trait loci. Trends Genetics 19 (2003) 135–140. Google ScholarPubMed
Cooper, M. C., de Givry, S., Sánchez, M., Schiex, T., Zytnicki, M. and Werner, T., Soft arc consistency revisited. Artif. Intell. 174 (2010) 449–478. Google Scholar
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.
S. de Givry, T. Schiex and G. Verfaillie, Exploiting tree decomposition and soft local consistency in weighted CSP. AAAI Press (2006) 22–27.
Simon. de Givry, Rapport d’habilitation à diriger les recherches. INRA UBIA Toulouse (2011).
Dechter, R. and Pearl, J., Tree clustering for constraint networks. Artif. Intell. 38 (1989) 353–366. Google Scholar
Carlson, C.S. 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. Google Scholar
M. Fontaine, S. Loudni and P. Boizumault, Guiding VNS with tree decomposition. ICTAI. IEEE (2011) 505–512.
Gavri, F., The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16 (1974) 47–56. Google Scholar
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.
Gottlob, G., Miklós, Z. and Schwentick, T., Generalized hypertree decompositions: Np–hardness and tractable variants. J. ACM 56 (2009). Google Scholar
G. Gottlob, R. Pichler and F. Wei, Tractable database design through bounded treewidth, in PODS, edited by Stijn Vansummeren. ACM (2006) 124–133.
Hansen, P., Mladenovic, N. and Perez-Brito, D., Variable neighborhood decomposition search. J. Heuristics 7 (2001) 335–350. Google Scholar
W.D. Harvey and M.L. Ginsberg, Limited discrepancy search, in IJCAI (1). Morgan Kaufmann (1995) 607–615.
Jégou, P., Ndiaye, S. and Terrioux, C., 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. Google Scholar
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.
M. Kitching and F. Bacchus, Exploiting decomposition on constraint problems with high tree–width, in Boutilier [6] 525–531.
Koster, A.M.C.A., Bodlaender, H.L. and van Hoesel, S.P.M., Treewidth: Computational experiments. Electr. Notes Discrete Math. 8 (2001) 54–57. Google Scholar
J. Larrosa and T. Schiex, In the quest of the best form of local consistency for weighted CSP, in IJCAI (2003) 239–244.
Larrosa, J. and Schiex, T., Solving weighted CSP by maintaining arc consistency. Artif. Intell. 159 (2004) 1–26. Google Scholar
Loudni, S. and Boizumault, P., Combining VNS with constraint programming for solving anytime optimization problems. EJOR 191 (2008) 705–735. Google Scholar
Marinescu, R. and Dechter, R., AND/OR branch-and-bound search for combinatorial optimization in graphical models. Artif. Intell. 173 (2009) 1457–1491. Google Scholar
Mladenovic, N. and Hansen, P.. Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097–1100. Google Scholar
B. Neveu, G. Trombettoni and F. Glover, ID Walk: A candidate list strategy with a simple diversification device. in Wallace [45] 423–437.
Papadimitriou, C. and Yannakakis, M., Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43 (1991) 425–440. Google Scholar
J. Pearl, Probabilistic inference in intelligent systems, in Networks of Plausible Inference. Morgan Kaufmann (1998).
L. Perron, P. Shaw and V. Furnon, Propagation guided large neighborhood search, in Wallace [45] 468–481.
Qin, Z.S., Gopalakrishnan, S. and Abecasis, G.R., An efficient comprehensive search algorithm for tagsnp selection using linkage disequilibrium criteria. Bioinformatics 22 (2006) 220–225. Google ScholarPubMed
Rish, I. and Dechter, R., Resolution versus search: Two strategies for sat. J. Autom. Reason. 24 (2000) 225–275. Google Scholar
Robertson, N. and Seymour, P.D., Graph minors. ii. algorithmic aspects of tree–width. J. Algorithms 7 (1986) 309–322. Google Scholar
M. Sánchez, D. Allouche, S. de Givry and T. Schiex, Russian doll search with tree decomposition, in Boutilier [6] 603–608.
Sánchez, M., de Givry, S. and Schiex, T., Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques. Constraints 13 (2008) 130–154. Google Scholar
T. Sandholm, An algorithm for optimal winner determination in combinatorial auctions, in IJCAI’99 (1999) 342–347.
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.
Tarjan, R.E. and Yannakakis, M.. 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. Google Scholar
Terrioux, C. and Jégou, P., Hybrid backtracking bounded by tree–decomposition of constraint networks. Artif. Intell. 146 (2003) 43–75. Google Scholar
H. van Benthem, GRAPH: Generating radiolink frequency assignment problems heuristically. Master Thesis, Delft Univ. Technol, The Netherlands (1995).
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).