This paper presents the approach that we developed to solve the ROADEF 2003 challenge problem. This work is part of a research program whose aim is to study the benefits and the computer-aided generation of hybrid solutions that mix constraint programming and meta-heuristics, such as large neighborhood search (LNS). This paper focuses on three contributions that were obtained during this project: an improved method for propagating hamiltonian chain constraints, a fresh look at limited discrepancy search and the introduction of randomization and de-randomization within our combination algebra. This algebra is made of terms that represent optimization algorithms, following the approach of SALSA [1], which can be generated or tuned automatically using a learning meta-strategy [2]. In this paper, the hybrid combination that is investigated mixes constraint propagation, a special form of limited discrepancy search and large neighborhood search.
@article{RO_2006__40_2_77_0,
author = {Caseau, Yves},
title = {Combining constraint propagation and meta-heuristics for searching a maximum weight hamiltonian chain},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {77--95},
year = {2006},
publisher = {EDP-Sciences},
volume = {40},
number = {2},
doi = {10.1051/ro:2006018},
mrnumber = {2272681},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2006018/}
}
TY - JOUR AU - Caseau, Yves TI - Combining constraint propagation and meta-heuristics for searching a maximum weight hamiltonian chain JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2006 SP - 77 EP - 95 VL - 40 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2006018/ DO - 10.1051/ro:2006018 LA - en ID - RO_2006__40_2_77_0 ER -
%0 Journal Article %A Caseau, Yves %T Combining constraint propagation and meta-heuristics for searching a maximum weight hamiltonian chain %J RAIRO - Operations Research - Recherche Opérationnelle %D 2006 %P 77-95 %V 40 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2006018/ %R 10.1051/ro:2006018 %G en %F RO_2006__40_2_77_0
Caseau, Yves. Combining constraint propagation and meta-heuristics for searching a maximum weight hamiltonian chain. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 2, pp. 77-95. doi: 10.1051/ro:2006018
Cité par Sources :