Combining constraint propagation and meta-heuristics for searching a maximum weight hamiltonian chain
RAIRO - Operations Research - Recherche Opérationnelle, Volume 40 (2006) no. 2, pp. 77-95.

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},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {2},
     year = {2006},
     doi = {10.1051/ro:2006018},
     mrnumber = {2272681},
     language = {en},
     url = {http://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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, Volume 40 (2006) no. 2, pp. 77-95. doi : 10.1051/ro:2006018. http://archive.numdam.org/articles/10.1051/ro:2006018/

[1] 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.

[2] Y. Caseau, G. Silverstein and F. Laburthe, Learning Hybrid Algorithms for Vehicle Routing Problems. TPLP 1 (2001) 779-806. | Zbl

[3] 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.

[4] Y. Caseau and F. Laburthe, Solving small TSPs with Constraints, in Proc. of the 14th International Conference on Logic Programming. The MIT Press (1997).

[5] F. Focacci, M. Milano and A. Lodi, Solving TSP with Time Windows with Constraints. ICLP 515-529W (1999).

[6] 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).

[7] Harvey and M. Ginsberg, Limited Discrepancy Search, in Proc. of the 14th IJCAI. Morgan Kaufmann (1995) 607-615.

[8] 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).

[9] 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. | MR

[10] 2003 ROADEF Challenge: http://www.prism.uvsq.fr/vdc/ROADEF/CHALLENGES/2003.

[11] 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). | Zbl

[12] 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).

[13] Y. Caseau and F. Laburthe, Improving Branch and Bound for Jobshop Scheduling with Constraint Propagation. Combin. Comput. Sci. 1995 (1995) 129-149.

[14] D. Applegate and B. Cook. A Computational Study of the Job Shop Scheduling Problem. Oper. Res. Soci. Amer. 3 (1991). | Zbl

[15] Y. Caseau, F.X. Josset and F. Laburthe, CLAIRE: Combining sets, search and rules to better express algorithms. TPLP 2 (2002) 769-805. | Zbl

Cited by Sources: