G-2008-02
Using Local Search to Speed Up Filtering Algorithms for Some NP-Hard Constraints
, , et référence BibTeX
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.
Paru en janvier 2008 , 18 pages
Axe de recherche
Publications
jan. 2011
Using local search to speed up filtering algorithms for some NP-Hard constraints
, , et
Annals of Operations Research, 184(1), 121–135, 2011
référence BibTeX
jan. 2008
Using local search to speed up filtering algorithms for some NP-hard constraints
, , et
Springer Berlin / Heidelberg, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, 5015, 298–302, 2008
référence BibTeX