Heuristics for hard ASP programs
Wolfgang Faber, Nicola Leone, Francesco Ricca · 2005
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 2-hard 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. 1