EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO Oper. Res.
Volume 40, Number 2, April-June 2006
ROADEF 03
Page(s) 77 - 95
DOI 10.1051/ro:2006018
Published online 12 October 2006

RAIRO Oper. Res. 40 (2006) 77-95
DOI: 10.1051/ro:2006018

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

Yves Caseau

Bouygues e-Lab, 1 avenue Eugène Freyssinet, 78061 St-Quentin en Yvelines Cedex, France;
    e-mail: ycs@caseau.com

(Received December 31, 2005. Published online 12 October 2006.)

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.



© EDP Sciences 2006


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.