Local search with constraint propagation and conflict-based heuristics

Search algorithms for solving csp (Constraint Satisfaction Problems) usually fall into one of two main families: local search algorithms and systematic algorithms. Both families have their advantages. Designing hybrid approaches seems promising since those advantages may be combined into a single ap...

Full description

Saved in:
Bibliographic Details
Published in:Artificial intelligence 2002-07, Vol.139 (1), p.21-45
Main Authors: Jussien, Narendra, Lhomme, Olivier
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Computer Science
Conflict-based search
Constraint satisfaction
Hybrid search algorithm
Local search
Operations Research
Repair methods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Search algorithms for solving csp (Constraint Satisfaction Problems) usually fall into one of two main families: local search algorithms and systematic algorithms. Both families have their advantages. Designing hybrid approaches seems promising since those advantages may be combined into a single approach. In this paper, we present a new hybrid technique. It performs a local search over partial assignments instead of complete assignments, and uses filtering techniques and conflict-based techniques to efficiently guide the search. This new technique benefits from both classical approaches: a priori pruning of the search space from filtering-based search and possible repair of early mistakes from local search. We focus on a specific version of this technique: tabu decision-repair. Experiments done on open-shop scheduling problems show that our approach competes well with the best highly specialized algorithms.
ISSN:0004-3702
1872-7921
DOI:10.1016/S0004-3702(02)00221-7