Volume 47, Number 2, April-June 2013Constraint Programming
|Page(s)||91 - 123|
|Published online||18 April 2013|
Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS
Universitéde Caen Basse-Normandie, CNRS, UMR 6072
Received: 28 January 2013
Accepted: 11 February 2013
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.
Mathematics Subject Classification: 68T20
Key words: Variable neighborhood search / tree decomposition / maximum cardinality search / cost functions netwok / constraint propagation
© EDP Sciences, ROADEF, SMAI, 2013
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.