Home | Publications | CS Home

Speedup Learning for Repair-based Search by Identifying Redundant Steps


Shaul Markovitch and Asaf Shatil. Speedup Learning for Repair-based Search by Identifying Redundant Steps. Journal of Machine Learning Research, 4: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.


Keywords: Speedup Learning, Scheduling
Secondary Keywords:
Online version:
Bibtex entry:
 @article{Markovitch:2003:SLR,
  Author = {Shaul Markovitch and Asaf Shatil},
  Title = {Speedup Learning for Repair-based Search by Identifying Redundant Steps},
  Year = {2003},
  Journal = {Journal of Machine Learning Research},
  Volume = {4},
  Pages = {649--682},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Markovitch-Shatil-jmlr2003.pdf},
  Keywords = {Speedup Learning, Scheduling},
  Secondary-keywords = {Local Search, Decision Trees},
  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.
  }

  }