An Efficient Global-Search Strategy in Discrete Lagrangian Methods for Solving Hard Satisfiability Problems
Abstract
In this paper, we present an efficient global-search strategy in an algorithm based on the theory of discrete Lagrange multipliers for solving difficult SAT instances. These difficult benchmarks generally have many traps and basins that attract local-search trajectories. In contrast to trap-escaping strategies proposed earlier (?; ?) that only focus on traps, we propose a global-search strategy that penalizes a search for visiting points close to points visited before in the trajectory, where penalties are computed based on the Hamming distances between the current and historical points in the trajectory. The new
Cite
Text
Wu and Wah. "An Efficient Global-Search Strategy in Discrete Lagrangian Methods for Solving Hard Satisfiability Problems." AAAI Conference on Artificial Intelligence, 2000.Markdown
[Wu and Wah. "An Efficient Global-Search Strategy in Discrete Lagrangian Methods for Solving Hard Satisfiability Problems." AAAI Conference on Artificial Intelligence, 2000.](https://mlanthology.org/aaai/2000/wu2000aaai-efficient/)BibTeX
@inproceedings{wu2000aaai-efficient,
title = {{An Efficient Global-Search Strategy in Discrete Lagrangian Methods for Solving Hard Satisfiability Problems}},
author = {Wu, Zhe and Wah, Benjamin W.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2000},
pages = {310-315},
url = {https://mlanthology.org/aaai/2000/wu2000aaai-efficient/}
}