Conflict Generalisation in ASP: Learning Correct and Effective Non-Ground Constraints
This addresses a neglected issue in state-of-the-art answer set solvers for improving solving efficiency, though it appears incremental as it combines existing techniques.
The paper tackles the problem of generalizing learned nogoods in answer set programming to speed up solving future instances, demonstrating that adding learned non-ground constraints yields significant performance benefits with low computational cost in test cases.
Generalising and re-using knowledge learned while solving one problem instance has been neglected by state-of-the-art answer set solvers. We suggest a new approach that generalises learned nogoods for re-use to speed-up the solving of future problem instances. Our solution combines well-known ASP solving techniques with deductive logic-based machine learning. Solving performance can be improved by adding learned non-ground constraints to the original program. We demonstrate the effects of our method by means of realistic examples, showing that our approach requires low computational cost to learn constraints that yield significant performance benefits in our test cases. These benefits can be seen with ground-and-solve systems as well as lazy-grounding systems. However, ground-and-solve systems suffer from additional grounding overheads, induced by the additional constraints in some cases. By means of conflict minimization, non-minimal learned constraints can be reduced. This can result in significant reductions of grounding and solving efforts, as our experiments show. (Under consideration for acceptance in TPLP.)