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)


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
Number of pages10
Publication statusPublished - 1 Dec 1998
Externally publishedYes
EventInternational Conference on Tools with Artificial Intelligence 1998 - Taipei, China
Duration: 10 Nov 199812 Nov 1998
Conference number: 10th


ConferenceInternational Conference on Tools with Artificial Intelligence 1998
CityTaipei, China

Cite this