Skip to Main content Skip to Navigation
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, Automatique 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

https://hal.inria.fr/hal-00810146
Contributor : Mathieu Fontaine <>
Submitted on : Friday, April 26, 2013 - 11:11:18 AM
Last modification on : Thursday, February 7, 2019 - 5:47:23 PM
Long-term archiving on: : Saturday, July 27, 2013 - 2:30:10 AM

File

jfpc2012_submission_10.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00810146, version 1

Citation

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⟩

Share

Metrics

Record views

238

Files downloads

132