Using local search to speed up filtering algorithms for some NP-hard constraints

Philippe Galinier (), Alain Hertz (), Sandrine Paroz () and Gilles Pesant ()

Annals of Operations Research, 2011, vol. 184, issue 1, 135 pages

Abstract: 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. Copyright Springer Science+Business Media, LLC 2011

Keywords: Constraint programming; Local search; Graph coloring (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-010-0715-0 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:184:y:2011:i:1:p:121-135:10.1007/s10479-010-0715-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-010-0715-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().