Publication details
Iterative Forward Search: Combining Local Search with Maintaining Arc Consistency and a Conflict-based Statistics
| Authors | |
|---|---|
| Year of publication | 2004 |
| Type | Article in Proceedings |
| Conference | Local Search Techniques in Constraint Satisfaction |
| MU Faculty or unit | |
| Citation | |
| Web | http://www.fi.muni.cz/~hanka/publ/lscs04.pdf |
| Keywords | search algorithms; constraint satisfaction; timetabling |
| Description | The paper presents an iterative forward search framework for solving constraint satisfaction and optimization problems. This framework combines ideas of local search, namely improving a solution by local steps, with principles of depth-first search, in particular extending a partial feasible assignment towards a solution. Within this framework, we also propose and study a conflict-based statistics and explanationbased arc consistency maintenance. To show the versatility of the proposed framework, the dynamic backtracking algorithm with maintaining arc consistency is presented as a special instance of the iterative forward search framework. The presented techniques are compared on random constraint satisfaction problems and a real-life lecture timetabling problem. |