Algorithms and Experiments on Finding Minimal Models

Paolo Liberatore

Technical Report, Dipartimento di Informatica e Sistemistica, Università di Roma ''La Sapienza''

In this paper we consider the problem of finding minimal models of a set of propositional clauses. This problem has many applications: for instance, finding minimal-length plans, minimal diagnosis, and solving many other minimization and maximization problems. We have adapted the Davis-Putnam algorithm (that finds generic models of a set of clauses) in order to find minimal models. Experiments have been performed to determine which heuristics can be useful, and to decide in which cases the problem is hard and in which cases it is easy. A comparison with a local search algorithm is also shown.

 title = {Algorithms and Experiments on Finding Minimal Models},
 year = {1999},
 author = {Liberatore, Paolo},
 institution = {Dipartimento di Informatica e Sistemistica,
 Universit\'a di Roma ''La Sapienza''},
 number = {09--99},
HTTP download.
FTP download.