| Copyright | (c) Masahiro Sakai 2016 |
|---|---|
| License | BSD-style |
| Maintainer | masahiro.sakai@gmail.com |
| Stability | provisional |
| Portability | non-portable |
| Safe Haskell | None |
| Language | Haskell2010 |
ToySolver.Combinatorial.HittingSet.MARCO
Contents
Description
- M. Liffiton and A. Malik, "Enumerating infeasibility: Finding multiple MUSes quickly," in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, C. Gomes and M. Sellmann, Eds. pp. 160-175. http://sun.iwu.edu/~mliffito/publications/cpaior13_liffiton_MARCO.pdf
Problem definition
Main functionality
run :: forall prob. IsProblem prob IO => prob -> Options IO -> IO (Set IntSet, Set IntSet) Source #
Given a problem and an option, it computes maximal interesting sets and minimal uninteresting sets.
Applications: monotone boolean functions
Arguments
| :: IntSet | Set of variables V |
| -> (IntSet -> Bool) | A monotone boolean function f from {0,1}^|V| ≅ P(V) to |
| -> 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.