---
kind: concept
slug: pseudo-boolean-optimization
title: Pseudo-Boolean optimization (PBO)
summary: >-
  Choose 0/1 values for variables so that linear constraints with integer coefficients hold and a linear cost is minimised. Covers three routes: native PB solvers, translation to weighted MaxSAT, and native core-guided Weighted Boolean Optimization. One source so far, with author-reported solved counts.
tags: [pseudo-boolean, combinatorial-optimization, sat-solving, max-sat]
papers: ["0903.0843"]
related: [maximum-satisfiability, constraint-satisfaction]
status: draft
updated_at: 2026-11-15
---

## Overview

A pseudo-Boolean (PB) problem has yes/no variables, linear constraints over
them with non-negative integer coefficients, and a linear objective to
minimise. The paper writes any such problem in one normal form, in which
every constraint is a "sum of weighted literals at least a bound" and every
objective term is a weighted variable [arxiv:0903.0843 §2.2] [arxiv:0903.0843 eq. 1].
Negated literals are allowed, so a single constraint can express a clause,
a cardinality rule or a general weighted threshold [arxiv:0903.0843 §2.2].

The same paper shows that PBO and weighted partial MaxSAT can be rewritten
into each other. An objective term becomes a soft unit clause, and a PB
constraint becomes hard clauses through a PB-to-CNF encoding
[arxiv:0903.0843 §2.3]. The two solver communities had developed separately,
which is the gap the paper addresses [arxiv:0903.0843 §1]. The concept page
for MaxSAT covers the clause side in more detail: [Maximum satisfiability](/concepts/maximum-satisfiability).
The [constraint satisfaction](/concepts/constraint-satisfaction) page places
PBO among other modelling routes.

## Variants

### Native PB solving

The constraints and objective stay in pseudo-Boolean form, and a PB solver
searches for a minimum-cost assignment. The paper compares five such solvers
as baselines, named BSOLO, PBS, Pueblo, Minisat+ and SAT4J (PB) [arxiv:0903.0843 §5].
It does not describe how these solvers work internally, so this page does
not characterise their methods [arxiv:0903.0843 §5]. Their solved counts are
reported in the results below.

### Translation to weighted MaxSAT

Each objective term becomes a soft unit clause whose weight is the term's
coefficient. Each PB constraint is encoded as hard clauses. The result is
solved as weighted partial MaxSAT [arxiv:0903.0843 §2.3]. The paper's own
core-guided MaxSAT solver, MSUnCore, uses this route on its clause-form
classes [arxiv:0903.0843 §5]. Card: [Algorithms for Weighted Boolean Optimization](/papers/0903.0843).

The cost of this route is the encoding step. The paper notes that
arc-consistent CNF encodings of general PB constraints can grow exponentially
in the worst case [arxiv:0903.0843 §5].

### Native core-guided Weighted Boolean Optimization

The paper's WBO framework keeps PB constraints as they are. It uses a
core-guided loop in which a PB solver returns an unsatisfiable subset.
Each constraint in the subset is relaxed by adding its bound times a fresh
variable to its left-hand side, and an exactly-one constraint is added over
the fresh variables [arxiv:0903.0843 §4.1]. The relaxed form is written out
in the paper's section on WBO [arxiv:0903.0843 §4.1]. The
paper does not describe how the PB solver extracts the subset
[arxiv:0903.0843 §4.1]. Card: [Algorithms for Weighted Boolean Optimization](/papers/0903.0843).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Constraints are mostly clauses and a weighted MaxSAT solver is available | Translation to weighted MaxSAT | MSUnCore solved 189 of 243 instances in the paper's benchmark, more than any other solver it tested [arxiv:0903.0843 tab. 2]. The benchmark is the paper's own. |
| Constraints go beyond clauses and you want to avoid a CNF blow-up | Native WBO, or native PB solving | The paper notes the CNF encoding can grow large [arxiv:0903.0843 §5]. WBO accepts PB constraints natively [arxiv:0903.0843 §4.1]. |
| You need one framework covering both weighted MaxSAT and PBO | Native WBO | It handles hard and soft PB constraints in one format [arxiv:0903.0843 §4]. On the paper's clause-form classes WBO solved fewer instances than MSUnCore [arxiv:0903.0843 tab. 2] [arxiv:0903.0843 tab. 3]. |
| Your PB solver cannot return unsatisfiable subsets | Native PB solving, or the MaxSAT route with a core-capable solver | Both core-guided routes need cores. The paper does not describe how WBO extracts them [arxiv:0903.0843 §4.1]. |
| You need a good solution early, before optimality is proven | Not answered by this page | Core-guided search raises a lower bound. The paper sketches a branch-and-bound alternative but reports no results for it [arxiv:0903.0843 §4.2]. |
| You need reproducible benchmark numbers | Check the instance source first | The IND 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]. |

## Results

Author-reported. The benchmark has 243 instances in three classes: IND
(110), FIR (59) and SYN (74) [arxiv:0903.0843 tab. 1]. Solved counts for the
PBO and WBO solvers [arxiv:0903.0843 tab. 3]:

| Class | BSOLO | PBS | Pueblo | Minisat+ | SAT4J (PB) | WBO |
|---|---|---|---|---|---|---|
| IND | 17 | 0 | 0 | 0 | 60 | 110 |
| FIR | 20 | 11 | 14 | 22 | 7 | 39 |
| SYN | 51 | 19 | 30 | 30 | 22 | 33 |
| Total (of 243), as printed | 88 | 30 | 44 | 52 | 89 | 172 |

The WBO total is printed as 172, but its row sums to 182
[arxiv:0903.0843 tab. 3]. Among the PBO solvers, SAT4J (PB) and BSOLO
score best on these counts [arxiv:0903.0843 §5]. The text also reports
qualitative run-time results in a figure, with no numbers given
[arxiv:0903.0843 fig. 1].

## Implementation sketch

The translation of an objective to soft clauses, and of constraints to hard
clauses, following [arxiv:0903.0843 §2.3]. The encoder is a parameter because
the paper does not fix one for general PB constraints [arxiv:0903.0843 §5].

```pseudocode
# Each objective term c * x becomes a soft unit clause  [§2.3]
# Input: list of (c, x) pairs, c a non-negative integer  [eq. 1]
def objective_to_soft(terms):
    soft = []
    for c, x in terms:
        # The clause (not x) is violated exactly when x is true,
        # so the violation weight is c  [§2.3]
        soft.append({"clause": [not x], "weight": c})
    return soft

# Each PB constraint becomes hard clauses through an encoder  [§2.3]
def constraints_to_hard(constraints, encode_cnf):
    hard = []
    for con in constraints:
        # The encoder is a choice; arc-consistent encodings can blow up  [§5]
        hard.extend(encode_cnf(con))
    return hard
```

## Contradictions

Within the one paper, not between papers:

- **Total versus rows in Table 3.** The WBO row sums to 182, but the printed
  total is 172 [arxiv:0903.0843 tab. 3]. The text ranks WBO behind MSUnCore
  and ahead of IncWMaxSatz, which holds for either total [arxiv:0903.0843 §5].
- **Solved versus aborted.** The text describes the tables as instances
  aborted by each solver, but the captions say solved. The counts match the
  solved reading [arxiv:0903.0843 §5] [arxiv:0903.0843 tab. 3].
- **Exactly one versus at most one.** The paper states the relaxation constraint as
  exactly one for WBO [arxiv:0903.0843 §4.1], while its worked example uses
  at most one [arxiv:0903.0843 eq. 9]. The paper says at most one suffices
  for its core method [arxiv:0903.0843 §2.4] but does not claim this for WBO.
- **Abstract versus tables.** The abstract claims large gains for the
  unsatisfiability-based method over dedicated algorithms [arxiv:0903.0843 abstract].
  The tables count solved instances only and do not measure the size of the gain
  [arxiv:0903.0843 tab. 2] [arxiv:0903.0843 tab. 3].

## Papers

- [Algorithms for Weighted Boolean Optimization](/papers/0903.0843): normal form for PB constraints, translations to and from weighted MaxSAT, and the WBO core-guided solver with its benchmark counts.
