## Speedup Learning for Repair-based Search by Identifying Redundant Steps

**
Shaul Markovitch, Asaf Shatil**; 4(Sep):649-682, 2003.

### Abstract

Repair-based search algorithms start with an initial solution and attempt to improve it by iteratively applying repair operators. Such algorithms can often handle large-scale problems that may be difficult for systematic search algorithms. Nevertheless, the computational cost of solving such problems is still very high. We observed that many of the repair steps applied by such algorithms are redundant in the sense that they do not eventually contribute to finding a solution. Such redundant steps are particularly harmful in repair-based search, where each step carries high cost due to the very high branching factor typically associated with it.

Accurately identifying and avoiding such redundant steps would
result in faster local search without harming the algorithm's
problem-solving ability. In this paper we propose a speedup
learning methodology for attaining this goal. It consists of the
following steps: defining the concept of a *redundant step*;
acquiring this concept during off-line learning by analyzing
solution paths for training problems, tagging all the steps along
the paths according to the redundancy definition and using an
induction algorithm to infer a classifier based on the tagged
examples; and using the acquired classifier to filter out redundant
steps while solving unseen problems.

Our algorithm was empirically tested on instances of real-world employee timetabling problems (ETP). The problem solver to be improved is based on one of the best methods for solving some large ETP instances. Our results show a significant improvement in speed for test problems that are similar to the given example problems.