Learning to Speed up Search

Contents

Recently, we have seen some promising developments in using machine learning techniques to speed up search methods. For example, Boyan and Moore introduced the STAGE algorithm to learn how to reach good start-ing states for local search methods. Also, Dietterich et al. have proposed a range of reinforcement learning methods to discover heuristics for solv-ing job shop scheduling problems. Despite these promising developments, these techniques have not been incorporated in the latest combinatorial solvers, such as SAT and CSP engines. On the other hand, techniques ~th a machine learning flavor but not based on traditional machine learning techniques, such as clause learning and clause weighing, have been shown to be of direct practical use. We will survey the special challenges that need to be overcome when one tries to use machine learning techniques to speed up state-of-the-art combinatorial search methods.