Using Local Search to Speed Up Filtering Algorithms for Some NP-Hard Constraints

download the pdf

publication link

 

Year of publication : 2011

Bibliographic reference:
Ph. GALINIER, A. HERTZ, S. PAROZ, G. PESANT. Using Local Search to Speed Up Filtering Algorithms for Some NP-Hard Constraints. Annals of Operations Research 184: 121-135.

Summary:
This paper proposes to use local search inside filtering algorithms of combinatorial structures for which achieving a desired level of consistency is too computationally expensive. Local search quickly provides supports for many variable-value pairs, thus reducing the effort required to check and potentially filter the rest of them. The idea is demonstrated on the SomeDifferent constraint, a graph coloring substructure. An experimental evaluation confirms its significant computational gain in many cases.

Bibtex: 

@article{DBLP:journals/anor/GalinierHPP11,
  author    = {Philippe Galinier and
               Alain Hertz and
               Sandrine Paroz and
               Gilles Pesant},
  title     = {Using local search to speed up filtering algorithms for
               some NP-hard constraints},
  journal   = {Annals OR},
  volume    = {184},
  number    = {1},
  year      = {2011},
  pages     = {121-135},
  ee        = {http://dx.doi.org/10.1007/s10479-010-0715-0},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

 

 

Member(s) who (co)wrote the paper

| Gilles Pesant || Philippe Galinier || Sandrine Paroz |

 

Project(s) linked to this publication

Filtering Algorithms
Hybrid methods

 

Files linked to the publication