A GRASP for the Minimum Cost SAT Problem

A substantial connection exists between supervised learning from data represented in logic form and the solution of the Minimum Cost Satisfiability Problem (MinCostSAT). Methods based on such connection have been developed and successfully applied in many contexts. The deployment of such methods to large-scale learning problem is often hindered by the computational challenge of solving MinCostSAT, a problem well known to be NP-complete. In this paper, we propose a GRASP-based metaheuristic designed for such problem, that proves successful in leveraging the very distinctive structure of the MinCostSAT problems arising in supervised learning. The algorithm is equipped with an original stopping criterion based on probabilistic assumptions which results very effective for deciding when the search space has been explored enough. Although the proposed solver may approach MinCostSAT of general form, in this paper we limit our analysis to some instances that have been created from artificial supervised learning problems, and show that our method outperforms more general purpose well established solvers.