Skip to Main content Skip to Navigation
New interface
Conference papers

Exploitation de la décomposition arborescente pour guider la recherche VNS

Mathieu Fontaine 1 Samir Loudni 1 Patrice Boizumault 1 
1 Equipe CODAG - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image et Instrumentation de Caen
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 the exploration of local search methods that use large neighborhoods like VNS. We introduce tightness dependant tree decomposition which allows to take advantage of both the structure of the problem and the constraints tightness. Experiments performed on random instances (GRAPH) and real life instances (CELAR and SPOT5) show the appropriateness and the efficiency of our approach.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Mathieu Fontaine Connect in order to contact the contributor
Submitted on : Friday, April 26, 2013 - 11:11:18 AM
Last modification on : Saturday, June 25, 2022 - 9:47:18 AM
Long-term archiving on: : Saturday, July 27, 2013 - 2:30:10 AM


Files produced by the author(s)


  • HAL Id : hal-00810146, version 1


Mathieu Fontaine, Samir Loudni, Patrice Boizumault. Exploitation de la décomposition arborescente pour guider la recherche VNS. JFPC 2012, May 2012, toulouse, France. ⟨hal-00810146⟩



Record views


Files downloads