Combining constraint Propagation and meta-heuristics for searching a Maximum Weight Hamiltonian Chain
RAIRO - Operations Research (2006)
- Volume: 40, Issue: 2, page 77-95
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topCaseau, Yves. "Combining constraint Propagation and meta-heuristics for searching a Maximum Weight Hamiltonian Chain ." RAIRO - Operations Research 40.2 (2006): 77-95. <http://eudml.org/doc/249744>.
@article{Caseau2006,
abstract = {
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.
},
author = {Caseau, Yves},
journal = {RAIRO - Operations Research},
language = {eng},
month = {10},
number = {2},
pages = {77-95},
publisher = {EDP Sciences},
title = {Combining constraint Propagation and meta-heuristics for searching a Maximum Weight Hamiltonian Chain },
url = {http://eudml.org/doc/249744},
volume = {40},
year = {2006},
}
TY - JOUR
AU - Caseau, Yves
TI - Combining constraint Propagation and meta-heuristics for searching a Maximum Weight Hamiltonian Chain
JO - RAIRO - Operations Research
DA - 2006/10//
PB - EDP Sciences
VL - 40
IS - 2
SP - 77
EP - 95
AB -
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.
LA - eng
UR - http://eudml.org/doc/249744
ER -
References
top- F. Laburthe and Y. Caseau, SALSA: A Language for Search Algorithms, in Proc. of CP'98, edited by M. Maher, J.-F. Puget, Springer. Lect. Notes Comput. Sci.1520 (1998) 310–324.
- Y. Caseau, G. Silverstein and F. Laburthe, Learning Hybrid Algorithms for Vehicle Routing Problems. TPLP1 (2001) 779–806.
- S. Minton, Configurable Solvers: Tailoring General Methods to Specific Applications, in Proc. of CP'97, edited by G. Smolka, Springer. Lect. Notes Comput. Sci.1330 (1997) 372–374.
- Y. Caseau and F. Laburthe, Solving small TSPs with Constraints, in Proc. of the 14th International Conference on Logic Programming. The MIT Press (1997).
- F. Focacci, M. Milano and A. Lodi, Solving TSP with Time Windows with Constraints. ICLP 515–529W (1999).
- Y. Caseau, G. Silverstein and F. Laburthe, A Meta-Heuristic Factory for Vehicle Routing Problems, in Proc. of CP'99, Lect. Notes Comput. Sci.1713 (1999).
- Harvey and M. Ginsberg, Limited Discrepancy Search, in Proc. of the 14th IJCAI. Morgan Kaufmann (1995) 607–615.
- P. Shaw, Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems, in Proc. of CP'98, Lect. Notes Comput. Sci.1520 (1998).
- T. Benoist and B. Rottembourg, Upper Bounds of the Maximal Revenue of an Earth Observation Satellite, in 4OR: Quart. J. Belgian, French and Italian Oper. Res. Soc., Vol. 2, Issue 3, Oct. 2004.
- 2003 ROADEF Challenge: ~vdc/ROADEF/CHALLENGES/2003. URIhttp://www.prism.uvsq.fr/
- E. Taillard, P. Badeau, M. Gendreau, F. Guertin and J.-Y. Potvin, A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows, Transportation Science 31 (1997).
- D. Martin and P. Shmoys, A time-based approach to the Jobshop problem, in Proc. of IPCO'5, edited by M. Queyranne, Lect. Comput. Notes Sci.1084 (1996).
- Y. Caseau and F. Laburthe, Improving Branch and Bound for Jobshop Scheduling with Constraint Propagation. Combin. Comput. Sci.1995 (1995) 129–149.
- D. Applegate and B. Cook. A Computational Study of the Job Shop Scheduling Problem. Oper. Res. Soci. Amer.3 (1991).
- Y. Caseau, F.X. Josset and F. Laburthe, CLAIRE: Combining sets, search and rules to better express algorithms. TPLP2 (2002) 769–805.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.