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.
|Title of host publication||Proceedings of the International Conference on Tools with Artificial Intelligence|
|Number of pages||10|
|Publication status||Published - 1 Dec 1998|
|Event||Proceedings of the 1998 IEEE 10th International Conference on Tools with Artificial Intelligence - Taipei, China|
Duration: 10 Nov 1998 → 12 Nov 1998
|Conference||Proceedings of the 1998 IEEE 10th International Conference on Tools with Artificial Intelligence|
|Period||10/11/98 → 12/11/98|