Lagrangian reconstruction of GENET

Kenneth M.F. Choi, Jimmy H.M. Lee, Peter J. Stuckey

Research output: Contribution to journalArticleResearchpeer-review

13 Citations (Scopus)

Abstract

GENET is a heuristic repair algorithm which demonstrates impressive efficiency in solving some large-scale and hard instances of constraint satisfaction problems (CSPs). In this paper, we draw a surprising connection between GENET and discrete Lagrange multiplier methods. Based on the work of Wah and Shang, we propose a discrete Lagrangian-based search scheme LSDL, defining a class of search algorithms for solving CSPs. We show how GENET can be reconstructed from LSDL. The dual viewpoint of GENET as a heuristic repair method and a discrete 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 the original GENET implementation, and has competitive performance with other local search solvers DLM, WalkSAT, and WSAT(OIP), on a set of difficult benchmark problems. Second, our improved variant, which combines techniques from heuristic repair and discrete Lagrangian methods, is always more efficient than the reconstructed GENET, and can better it by an order of magnitude.

Original languageEnglish
Pages (from-to)1-39
Number of pages39
JournalArtificial Intelligence
Volume123
Issue number1-2
DOIs
Publication statusPublished - 1 Jan 2000
Externally publishedYes

Cite this