Disco - Novo - GoGo: Integrating Local Search and Complete Search with Restarts

Meinolf Sellmann, Carlos Ansotegui

A hybrid algorithm is devised to boost the performance of complete search on under-constrained problems. We suggest to use random variable selection in combination with restarts, augmented by a coarse-grained local search algorithm that learns favorable value heuristics over the course of several restarts. Numerical results show that this method can speed-up complete search by orders of magnitude.

Subjects: 15. Problem Solving; 15.2 Constraint Satisfaction

Submitted: May 13, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.