A Lagrangian reconstruction of GENET (Q1589464)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A Lagrangian reconstruction of GENET |
scientific article |
Statements
A Lagrangian reconstruction of GENET (English)
0 references
12 December 2000
0 references
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.
0 references
constraint satisfaction problems
0 references
local search
0 references
discrete Lagrangian method
0 references
0 references
0 references
0 references