Technical Report CIS-2002-02

TR#:CIS-2002-02
Class:CIS
Title: Speedup Learning for Repair-based Search by Identifying Redundant Steps
Authors: Shaul MArkovitch, Asaf Shatil
PDFCIS-2002-02.pdf
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 \emph{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; 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2002/CIS/CIS-2002-02), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 2002
To the main CS technical reports page

Computer science department, Technion