patternMinor
Maximize the number of satisfied disjunctions
Viewed 0 times
numberdisjunctionsthemaximizesatisfied
Problem
I have ~4000 variables that are used in ~5000 logical formulas, where each formula consists only of conjunctions of the (non-negated) variables. I want to find the maximum number of satisfied formulas, given the number of variables that I can set to 1.
Does this problem have a name? Is it equivalent to the MAX-SAT problem? Which algorithm would be applicable to solve it exactly or using heuristics?
Does this problem have a name? Is it equivalent to the MAX-SAT problem? Which algorithm would be applicable to solve it exactly or using heuristics?
Solution
You are addressing a problem of the same type. if you use De Morgan law your problem will become MIN-SAT which is NP-HARD
checkout THE MINIMUM SATISFIABILITY PROBLEM
checkout THE MINIMUM SATISFIABILITY PROBLEM
Context
StackExchange Computer Science Q#84330, answer score: 3
Revisions (0)
No revisions yet.