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

Voir la notice de l'article provenant de la source Numdam

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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :