MaxSAT Problem(s)

SAT

MaxSAT Problem(s)

  • MaxSAT:
    • All clauses are soft
    • Maximize number of satisfied soft clauses
    • Minimize number of unsatisfied soft clauses
  • Partial MaxSAT:
    • Hard clauses must be satisfied
    • Minimize number of unsatisfied soft clauses
  • Weighted MaxSAT
    • Weights associated with (soft) clauses
    • Minimize sum of weights of unsatisfied clauses
  • Weighted Partial MaxSAT
    • Weights associated with soft clauses
    • Hard clauses must be satisfied
    • Minimize sum of weights of unsatisfied soft clauses


MaxSAT for Optimization Problems, Joao Marques-Silva