Heuristics Based on Unit Propagation for Satisfiability Problems

Li, Chu-Min; Anbulagan

Heuristics Based on Unit Propagation for Satisfiability Problems

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 366-370.

Abstract

The paper studies new unit propagation based heuristics for Davis-Putnam-Loveland (DPL) procedure. These are the novel combinations of unit propagation and the usual "Maximum Occurrences in clauses of Minimum Size" heuristics. Based on the experimental evaluations of different alternatives a new simple unit propagation based heuristic is put forward. This compares favorably with the heuristics employed in the current state-of-the-art DPL implementations (C-SAT, Tableau, POSIT).

Chu-Min Li, and Anbulagan. 1997. Heuristics Based on Unit Propagation for Satisfiability Problems. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97. IJCAI, 366–370. https://ijcai.org/proceedings/1997/54

@inproceedings{ijcai1997p54,
  title     = {Heuristics Based on Unit Propagation for Satisfiability Problems},
  author    = {Li, Chu-Min and Anbulagan},
  booktitle = {Proceedings of the Fifteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-97}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Martha E. Pollack},
  pages     = {366--370},
  year      = {1997},
  note      = {Constraint Satisfaction},
  url       = {https://ijcai.org/proceedings/1997/54},
}

TY  - CPAPER
TI  - Heuristics Based on Unit Propagation for Satisfiability Problems
AU  - Li, Chu-Min
AU  - Anbulagan
T2  - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1997
SP  - 366
EP  - 370
UR  - https://ijcai.org/proceedings/1997/54
ER  -