ML Anthology

Learning Short-Term Weights for GSAT

Jeremy Frank
IJCAI 1997 pp. 384-391
/ijcai/1997/frank1997ijcai-learning/

Abstract

We investigate an improvement to GSAT which associates a weight with each clause. We change the objective function so that GSAT moves to assignments maximizing the weight of satisfied clauses, and each clause's weight is changed when GSAT moves to an assignment in which this clause is unsatisfied. We present results showing that this version of GSAT has good performance when clause weights are reduced geometrically throughout the course of a single try. We conclude that clause weights are best interpreted as short-term, context sensitive indicators of how hard different clauses are to satisfy. 1 Introduction Local search procedures are an alternative to complete search algorithms for solving combinatorially expensive search problems. GSAT is a local search algorithm which can often find solutions to satisfiable SAT problems in Conjunctive Normal Form (CNF) quickly [ SLM92 ] . GSAT operates by changing a complete assignment of variables into one in which the maximum possible number of ...

Semantic Scholar

Cite

Text

Frank. "Learning Short-Term Weights for GSAT." International Joint Conference on Artificial Intelligence, 1997.

Markdown

[Frank. "Learning Short-Term Weights for GSAT." International Joint Conference on Artificial Intelligence, 1997.](https://mlanthology.org/ijcai/1997/frank1997ijcai-learning/)

BibTeX

@inproceedings{frank1997ijcai-learning,
  title     = {{Learning Short-Term Weights for GSAT}},
  author    = {Frank, Jeremy},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {1997},
  pages     = {384-391},
  url       = {https://mlanthology.org/ijcai/1997/frank1997ijcai-learning/}
}