Logic decisions under constraints

摘要

A fundamental issue in the decision process and automated reasoning is how to efficiently obtain logic decisions under constraints. Logic Constraints Catisfaction problems are in general NP-hard and a general deterministic polynomial time algorithm is not known. The present paper illustrates two different approaches: the first based on Constrained Heuristic Search and the second based on Integer and Linear Programming. Both algorithms compare favourable with the best known techniques to solve decisions problems under logic constraints. Complexity of the algorithms and results of significant tests are reported.