Combining constraint Propagation and meta-heuristics for searching a Maximum Weight Hamiltonian Chain

Yves Caseau

RAIRO - Operations Research (2006)

  • Volume: 40, Issue: 2, page 77-95
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Caseau, 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
  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. TPLP1 (2001) 779–806.  
  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.  
  10. 2003 ROADEF Challenge: ~vdc/ROADEF/CHALLENGES/2003.  URIhttp://www.prism.uvsq.fr/
  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).  
  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).  
  15. Y. Caseau, F.X. Josset and F. Laburthe, CLAIRE: Combining sets, search and rules to better express algorithms. TPLP2 (2002) 769–805.  

NotesEmbed ?

top

You must be logged in to post comments.