---
kind: concept
slug: maximum-satisfiability
title: Maximum satisfiability (MaxSAT)
summary: >-
  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.
tags: [max-sat, combinatorial-optimization, sat-solving]
papers: ["0903.0843"]
related: [constraint-satisfaction, branch-and-bound]
status: draft
updated_at: 2026-11-15
---

## 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 [arxiv:0903.0843 §2.1]. Pseudo-Boolean optimization
(PBO) asks a similar question with linear constraints over integer
coefficients [arxiv:0903.0843 §2.2]. The 2009 paper shows that each side can
be rewritten in the other's form [arxiv: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 [arxiv: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 [arxiv:0903.0843 §2.4] [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:0903.0843 §3] [arxiv: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
[arxiv: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 [arxiv: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 [arxiv: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) [arxiv: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
[arxiv: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 [arxiv: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 [arxiv:0903.0843 §5]. On the paper's clause-form classes WBO solved fewer instances than MSUnCore [arxiv:0903.0843 tab. 2] [arxiv: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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:0903.0843 tab. 1]. Solver versions, run counts and seeds are not stated [arxiv:0903.0843 §5]. |

## Implementation sketch

A simplified core-guided loop for weighted partial MaxSAT, in our own words,
following the structure of [arxiv: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.

```pseudocode
# 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
  [arxiv:0903.0843 tab. 3]. The text ranks WBO second behind MSUnCore and
  ahead of IncWMaxSatz, which holds for either total [arxiv: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 [arxiv:0903.0843 §5] [arxiv: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 [arxiv: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 [arxiv:0903.0843 §4.1]
  [arxiv:0903.0843 alg. 2]. The worked WBO example uses at most one
  [arxiv:0903.0843 eq. 9]. The paper says at most one is enough for the core
  method [arxiv: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](/papers/0903.0843): defines Weighted Boolean Optimization and extends core-guided MaxSAT to weighted partial MaxSAT and pseudo-Boolean constraints.
