Backbone Guided Local Search for Maximum Satisfiability
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1179-1185.
Abstract
Maximum satisfiability (Max-SAT) is more general and more difficult to solve than satisfiability (SAT). In this paper, we first investigate the effectiveness of Walksat, one of the best local search algorithms designed for SAT, on Max-SAT. We show that Walksat is also effective on Max-SAT, while its effectiveness degrades as the problem is more constrained. We then develop a novel method that exploits the backbone information in the local minima from Walksat and applies the backbone information in different ways to improve the performance of the Walksat algorithm. We call our new algorithm backbone guided Walksat (BGWalksat). On large random SAT and Max-SAT problems as well as instances from the SATLIB, BGWalksat significantly improves Walksat's performance.
@inproceedings{ijcai2003p168,
title = {Backbone Guided Local Search for Maximum Satisfiability},
author = {Zhang, Weixiong and Rangan, Ananda and Looks, Moshe},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {1179--1185},
year = {2003},
url = {https://ijcai.org/proceedings/2003/168},
}
TY - CPAPER TI - Backbone Guided Local Search for Maximum Satisfiability AU - Zhang, Weixiong AU - Rangan, Ananda AU - Looks, Moshe T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 1179 EP - 1185 UR - https://ijcai.org/proceedings/2003/168 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
