MaxSAT

MaxSAT is the optimization counterpart of the Boolean satisfiability problem. In a MaxSAT problem, the input is a Boolean formula in conjunctive normal form (CNF) that is partitioned into hard and soft clauses. Hard clauses must be satisfied by any feasible assignment, while soft clauses may be violated. The objective is to find an assignment that satisfies all hard clauses and maximizes the number of satisfied soft clauses, or, in the weighted variant, maximizes the total weight of satisfied soft clauses.

There are several standard variants. Partial MaxSAT requires all hard clauses to be satisfied and seeks to maximize the count of soft clauses satisfied (unweighted). Weighted MaxSAT assigns a weight to each soft clause and aims to maximize the sum of weights of the satisfied soft clauses; this generalizes Partial MaxSAT and can model trade-offs among clauses. Related forms include the more general pseudo-Boolean MaxSAT, which allows linear inequalities over Boolean variables to serve as soft constraints.

Solution approaches primarily rely on SAT solving techniques. Exact MaxSAT solvers often translate the problem into a sequence of SAT problems or use relaxation variables to represent clause violations. Core-guided approaches iteratively identify unsatisfiable cores and relax them to improve the objective. Other methods treat MaxSAT as a pseudo-Boolean optimization problem and use dedicated solvers or reductions to weighted Max-SAT instances. The optimization nature makes MaxSAT NP-hard in general, with decision variants posing NP-complete questions such as whether there exists an assignment that satisfies at least a given threshold of soft clauses.

MaxSAT has broad applications in hardware and software verification, test-case generation, planning, scheduling, and resource allocation, where one seeks to satisfy as many constraints as possible while respecting hard requirements.