ToySolver.Combinatorial.HittingSet.DAA

"Dualize and Advance" algorithm for enumerating maximal interesting sets and minimal non-interesting sets.

• [GMKT1997] D. Gunopulos, H. Mannila, R. Khardon, and H. Toivonen, Data mining, hypergraph transversals, and machine learning (extended abstract), in Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ser. PODS '97. 1997, pp. 209-216. http://almaden.ibm.com/cs/projects/iis/hdb/Publications/papers/pods97_trans.pdf
• [BaileyStuckey2015] J. Bailey and P. Stuckey, Discovery of minimal unsatisfiable subsets of constraints using hitting set dualization," in Practical Aspects of Declarative Languages, pp. 174-186, 2005. http://ww2.cs.mu.oz.au/~pjs/papers/padl05.pdf

Problem definition

module ToySolver.Combinatorial.HittingSet.InterestingSets

Main functionality

run :: forall prob m. IsProblem prob m => prob -> Options m -> m (Set IntSet, Set IntSet)

Given a problem and an option, it computes maximal interesting sets and minimal uninteresting sets.

Applications: minimal hitting sets

generateCNFAndDNF

Arguments

:: IntSet

Set of variables V

-> (IntSet -> Bool)

A monotone boolean function f from {0,1}^|V| ≅ P(V) to Bool

-> Set IntSet

Subset C' of prime implicates C of f

-> Set IntSet

Subset D' of prime implicants D of f

-> (Set IntSet, Set IntSet)

Compute the irredundant CNF representation and DNF representation.

Let f be a monotone boolean function over set of variables S. This function returns C and D where ∧_{I∈C} ∨_{i∈I} x_i and ∨_{I∈D} ∧_{i∈I} x_i are the irredundant CNF representation f and DNF representation of f respectively.