A Machine Learning System to Improve the Performance of ASP Solving Based on Encoding Selection

Abstract

Answer set programming(ASP) has long been used for modeling and solving hard search problems. Experience shows that the performance of ASP tools on different ASP encodings of the same problem may vary greatly from instance to instance and it is rarely the case that one encoding outperforms all others. Running an ASP grounder/solver on one encoding for a specific instance may take forever, while selecting another encoding for this instance may yield a solution in a fraction of a second. In this paper, we describe asystem and its implementation that given a grounder/solver, a set of encodings of a problem, and a training set of instances, automatically generates additional encodings, selects some that promise good performance, and builds for each selected encoding its performance model. The model predictsfor any instance the execution time that the grounder/solver will take to process the instance under the corresponding encoding. These performance models are then used to improvesolving efficiency: whenever a new instance arrives, the system selects the encoding predicted to perform the best on the instance and invokes the solver. We present building blocksof the system, illustrate its use, and discuss some performance results.

Authors

Liu Liu (liu.liu@uky.edu)
Miroslaw Truszczynski (mirek@uky.edu)
Yuliya Lierler (ylierler@unomaha.edu)


Software and data

Download