Lagrangian reconstruction of a class of local search methods

K. M.F. Choi, J. H.M. Lee, P. J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

4 Citations (Scopus)

Abstract

Heuristic repair algorithms, a class of local search methods, demonstrate impressive efficiency in solving some large-scale and hard instances of constraint satisfaction problems (CSP's). In this paper, we draw a surprising connection between heuristic repair techniques and the discrete Lagrange multiplier methods by transforming CSP's into zero-one constrained optimization problems. A Lagrangian-based search scheme LSDL is proposed. We show how GENET, a representative heuristic repair algorithm, can be reconstructed from LSDL. The dual viewpoint of GENET as heuristic repair method and Lagrange multiplier method allows us to investigate variants of GENET from both perspectives. Benchmarking results confirm that first our reconstructed GENET has the same fast convergence behavior as other GENET implementations reported in the literature, competing favourably with other state-of-the-art methods on a set of hard graph colouring problems. Second, our best variant, which combines techniques from heuristic repair and Lagrangian methods, is always more efficient than the reconstructed GENET, and can better it by an order of magnitude.

Original languageEnglish
Title of host publicationProceedings of the International Conference on Tools with Artificial Intelligence
Pages166-175
Number of pages10
Publication statusPublished - 1 Dec 1998
Externally publishedYes
EventProceedings of the 1998 IEEE 10th International Conference on Tools with Artificial Intelligence - Taipei, China
Duration: 10 Nov 199812 Nov 1998

Conference

ConferenceProceedings of the 1998 IEEE 10th International Conference on Tools with Artificial Intelligence
CityTaipei, China
Period10/11/9812/11/98

Cite this