Heuristics for Hard ASP Programs

Faber, Wolfgang; Leone, Nicola; Ricca, Francesco

Heuristics for Hard ASP Programs

Wolfgang Faber, Nicola Leone, Francesco Ricca

Download BibTeX Cite

Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 1562-1562.

Abstract

We define a new heuristic hDS for ASP, and implement it in the (disjunctive) ASP system DLV. The new heuristic improves the evaluation of ΣP 2 /ΠP 2hard ASP programs while maintaining the benign behaviour of the well-assessed heuristic of DLV on NP problems. We experiment with the new heuristic on QBFs. hDS significantly outperforms the heuristic of DLV on hard 2QBF problems. We compare also the DLV system (with the new heuristic hDS ) to three prominent QBF solvers. The results of the comparison, performed on instances used in the last QBF competition, indicate that ASP systems can be faster than QBF systems on ΣP 2 /ΠP 2 -hard problems.

Wolfgang Faber, Nicola Leone, and Francesco Ricca. 2005. Heuristics for Hard ASP Programs. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05. IJCAI, 1562–1562. https://ijcai.org/proceedings/2005/341

@inproceedings{ijcai2005p341,
  title     = {Heuristics for Hard ASP Programs},
  author    = {Faber, Wolfgang and Leone, Nicola and Ricca, Francesco},
  booktitle = {Proceedings of the Nineteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-05}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {1562--1562},
  year      = {2005},
  url       = {https://ijcai.org/proceedings/2005/341},
}

TY  - CPAPER
TI  - Heuristics for Hard ASP Programs
AU  - Faber, Wolfgang
AU  - Leone, Nicola
AU  - Ricca, Francesco
T2  - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2005
SP  - 1562
EP  - 1562
UR  - https://ijcai.org/proceedings/2005/341
ER  -