Concept · 1 paper · updated 2026-11-15
Maximum satisfiability (MaxSAT)
Find a Boolean assignment that meets every hard clause and minimises the total weight of broken soft clauses. Covers core-guided solving: relax the clauses of each unsatisfiable core and raise a lower bound. Variants: unweighted and weighted partial MaxSAT (MSU1, WMSU1) and Weighted Boolean Optimization, which also accepts pseudo-Boolean constraints. One source so far.
max-satcombinatorial-optimizationsat-solving
Markdown5 min read
AI-compiled overview, updated 2026-11-15, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.
Overview
Maximum satisfiability asks for truth values of Boolean variables that make every hard clause true and, among those, minimise the weight of the soft clauses that are false. Weighted partial MaxSAT is the form with both hard and weighted soft clauses 0903.0843 §2.1. Pseudo-Boolean optimization (PBO) asks a similar question with linear constraints over integer coefficients 0903.0843 §2.2. The 2009 paper shows that each side can be rewritten in the other's form 0903.0843 §2.3.
The invariant that all variants share: a solution is an assignment that satisfies all hard constraints, and its cost is the total weight of violated soft constraints. The variants differ in how they search for the optimum and in what kind of constraint they accept.
Only one paper card supports this page so far. Every variant below comes from that card, and the reported numbers are the authors' own, on a single 2009 benchmark of 243 instances 0903.0843 tab. 1.
Variants
Core-guided (unsatisfiability-based) MaxSAT: MSU1
The solver calls a SAT solver on the current formula. When the formula is unsatisfiable, it reads off a core, which is a subset of clauses that cannot all hold. Each soft clause in the core gets a fresh relaxation variable, and an exactly-one constraint over these variables is added as a hard constraint. Each core is a step on a lower bound, and the loop ends when the formula becomes satisfiable 0903.0843 §2.4 0903.0843 alg. 1.
The paper credits the original unweighted form to Fu and Malik, which is cited but not a card in this wiki 0903.0843 §2.4. The paper states that the at-most-one form of the constraint is enough for correctness, and that the best-performing variant it reports is an optimised version of this method 0903.0843 §2.4. It gives no details of that optimisation.
Weighted partial MaxSAT: WMSU1 (MSUnCore)
The weighted extension keeps a running lower bound. Each core raises the bound by the smallest soft weight it contains. A soft clause heavier than that minimum is split: a relaxed copy carries the minimum weight, and the original stays in the formula with the remaining weight. This avoids duplicating a clause once per unit of weight, which the paper says does not scale for large weights 0903.0843 §3 0903.0843 alg. 2.
The paper's solver for this variant, MSUnCore, uses a CNF SAT backend and solved 189 of 243 instances, the most of any solver it compares 0903.0843 tab. 2.
Weighted Boolean Optimization (WBO)
WBO accepts hard and soft constraints that are pseudo-Boolean rather than clauses, each soft constraint with a positive integer weight. The core-guided loop carries over with three changes. A pseudo-Boolean solver replaces the SAT solver and must return an unsatisfiable subset of constraints. A relaxed constraint is built by adding the bound times a fresh variable. The exactly-one constraint is written directly as a pseudo-Boolean sum, with no CNF encoding 0903.0843 §4.1.
WBO can let two constraints in one core share a relaxation variable, under a coefficient condition on opposite literals. Choosing the shared pairs is a matching problem. The prototype uses a greedy heuristic, which may use more relaxation variables than an optimal matching would 0903.0843 §4.1.
The paper reports WBO as solving 172 instances in total, a figure that does not match its own rows (see Contradictions) 0903.0843 tab. 3.
Sketched alternatives: PBO solvers and branch-and-bound
The paper outlines two other routes without implementing them: extending PBO solvers with relaxable soft constraints, and extending branch-and-bound MaxSAT solvers to pseudo-Boolean constraints. Both refine an upper bound on the optimum, while the core-guided methods above refine a lower bound 0903.0843 §4.2.
When to use which
| Situation | Use | Why |
|---|---|---|
| Weighted partial MaxSAT with clause-form constraints | WMSU1 (MSUnCore-style) | It solved the most instances in the paper's benchmark, 189 of 243 0903.0843 tab. 2. |
| Constraints are pseudo-Boolean and you want one solver for both forms | WBO | It accepts PB constraints natively, so there is no CNF encoding step. The paper notes that such encodings can blow up in the worst case 0903.0843 §5. On the paper's clause-form classes WBO solved fewer instances than MSUnCore 0903.0843 tab. 2 0903.0843 tab. 3. |
| Plain clause form and you only have a SAT solver with a core output | WMSU1 | It needs only clause relaxation and an exactly-one constraint, the same SAT interface as the unweighted method 0903.0843 alg. 2. |
| Your SAT or PB solver cannot return unsatisfiable subsets | Not covered by this card | Both core-guided variants need cores. The paper does not describe how WBO extracts them 0903.0843 §4.1. |
| You need a good solution early, before proof of optimality | Not covered by this card | Core-guided search raises a lower bound. The branch-and-bound route it sketches refines an upper bound, but the paper does not evaluate it 0903.0843 §4.2. |
| You need reproducible benchmark numbers | Check the source first | The IND instance class was listed as forthcoming in a later evaluation, and its availability is not stated 0903.0843 tab. 1. Solver versions, run counts and seeds are not stated 0903.0843 §5. |
Implementation sketch
A simplified core-guided loop for weighted partial MaxSAT, in our own words, following the structure of 0903.0843 alg. 2. Lines and identifiers are illustrative. The paper does not say how a clause is recognised across rounds, so the sketch keeps clause objects by identity.
# Core-guided weighted partial MaxSAT, after [arxiv:0903.0843 alg. 2]
def core_guided(hard, soft): # soft: list of (clause, weight)
# Lower bound on the optimum, starts at zero [§3]
lower_bound = 0
while True:
# SAT call on hard clauses plus the current soft clauses [§3]
result = sat_solve(hard, soft)
if result.satisfiable:
# No core left: the lower bound is the optimum [§3]
return lower_bound
core = result.core # soft clauses that cannot all hold [§3]
# Each core costs at least its smallest weight [§3]
w_min = min(weight_of(c) for c in core)
lower_bound += w_min
relax_vars = []
for clause in core:
# Fresh relaxation variable for this clause [§3]
r = new_var()
relax_vars.append(r)
if weight_of(clause) > w_min:
# Split: the copy takes w_min, the original keeps the rest
reduce_weight(clause, w_min)
soft.append((clause + [r], w_min))
else:
# Weight fully used: replace the clause by its copy
soft.remove(clause)
soft.append((clause + [r], w_min))
# Exactly one relaxation variable may be set (at most one also works) [§2.4]
hard.append(exactly_one(relax_vars))For WBO, replace the SAT call with a pseudo-Boolean call that also returns a core of constraints, and relax each constraint by adding its bound times the fresh variable §4.1. The shared-variable step is optional and changes only the number of fresh variables §4.1.
Contradictions
- Printed total versus rows in tab. 3. The WBO row gives 110, 39 and 33 per class, which sums to 182, but the printed total is 172 0903.0843 tab. 3. The text ranks WBO second behind MSUnCore and ahead of IncWMaxSatz, which holds for either total 0903.0843 §5. Per-class values are used as printed on this page.
- Caption versus text. The captions of the result tables say the counts are solved instances. The text says the tables summarise instances on which each solver was aborted 0903.0843 §5 0903.0843 tab. 2. The printed counts match the solved reading, since the IND column for the three strongest solvers is the full 110 instances 0903.0843 tab. 2.
- Exactly-one versus at-most-one in WBO. The WBO algorithm and text state that the relaxation variables sum to exactly one 0903.0843 §4.1 0903.0843 alg. 2. The worked WBO example uses at most one 0903.0843 eq. 9. The paper says at most one is enough for the core method 0903.0843 §2.4 but does not claim this for WBO.
No other card in this wiki reports on MaxSAT, so no cross-paper disagreement is recorded.
Papers
- Algorithms for Weighted Boolean Optimization: defines Weighted Boolean Optimization and extends core-guided MaxSAT to weighted partial MaxSAT and pseudo-Boolean constraints.
Source and license
Compiled from the papers listed on this page, all published under CC BY, CC BY-SA or CC0, with citations. See each paper's page for its authors and license.