Solving Non-Boolean Satisfiability Problems with Stochastic Local Search
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 282-289.
Abstract
Much excitement has been generated by the recent success of stochastic local search procedures at finding satisfying assignments to large formulas. Many of the problems on which these methods have been effective are non-Boolean in that they are most naturally formulated in terms of variables with domain sizes greater than two. To tackle such a problem with a Boolean procedure the problem is first reformulated as an equivalent Boolean problem. This paper introduces and studies the alternative of extending a Boolean stochastic local search procedure to operate directly on non-Boolean problems. It then compares the non-Boolean representation to three Boolean representations and presents experimental evidence that the non-Boolean method is often superior for problems with large domain sizes.
@inproceedings{ijcai2001p40,
title = {Solving Non-Boolean Satisfiability Problems with Stochastic Local Search},
author = {Frisch, Alan M. and Peugniez, Timothy J.},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {282--289},
year = {2001},
url = {https://ijcai.org/proceedings/2001/40},
}
TY - CPAPER TI - Solving Non-Boolean Satisfiability Problems with Stochastic Local Search AU - Frisch, Alan M. AU - Peugniez, Timothy J. T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 282 EP - 289 UR - https://ijcai.org/proceedings/2001/40 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
