Concept · 1 paper · updated 2026-11-15
Pseudo-Boolean optimization (PBO)
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.
pseudo-booleancombinatorial-optimizationsat-solvingmax-sat
Markdown4 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
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 0903.0843 §2.2 0903.0843 eq. 1. Negated literals are allowed, so a single constraint can express a clause, a cardinality rule or a general weighted threshold 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 0903.0843 §2.3. The two solver communities had developed separately, which is the gap the paper addresses 0903.0843 §1. The concept page for MaxSAT covers the clause side in more detail: Maximum satisfiability. The 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) 0903.0843 §5. It does not describe how these solvers work internally, so this page does not characterise their methods 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 0903.0843 §2.3. The paper's own core-guided MaxSAT solver, MSUnCore, uses this route on its clause-form classes 0903.0843 §5. Card: Algorithms for Weighted Boolean Optimization.
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 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 0903.0843 §4.1. The relaxed form is written out in the paper's section on WBO 0903.0843 §4.1. The paper does not describe how the PB solver extracts the subset 0903.0843 §4.1. Card: Algorithms for Weighted Boolean Optimization.
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 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 0903.0843 §5. WBO accepts PB constraints natively 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 0903.0843 §4. On the paper's clause-form classes WBO solved fewer instances than MSUnCore 0903.0843 tab. 2 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 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 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 0903.0843 tab. 1. Solver versions, run counts and seeds are not stated 0903.0843 §5. |
Results
Author-reported. The benchmark has 243 instances in three classes: IND (110), FIR (59) and SYN (74) 0903.0843 tab. 1. Solved counts for the PBO and WBO solvers 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 0903.0843 tab. 3. Among the PBO solvers, SAT4J (PB) and BSOLO score best on these counts 0903.0843 §5. The text also reports qualitative run-time results in a figure, with no numbers given 0903.0843 fig. 1.
Implementation sketch
The translation of an objective to soft clauses, and of constraints to hard clauses, following 0903.0843 §2.3. The encoder is a parameter because the paper does not fix one for general PB constraints 0903.0843 §5.
# 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 hardContradictions
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 0903.0843 tab. 3. The text ranks WBO behind MSUnCore and ahead of IncWMaxSatz, which holds for either total 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 0903.0843 §5 0903.0843 tab. 3.
- Exactly one versus at most one. The paper states the relaxation constraint as exactly one for WBO 0903.0843 §4.1, while its worked example uses at most one 0903.0843 eq. 9. The paper says at most one suffices for its core method 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 0903.0843 abstract. The tables count solved instances only and do not measure the size of the gain 0903.0843 tab. 2 0903.0843 tab. 3.
Papers
- Algorithms for Weighted Boolean Optimization: normal form for PB constraints, translations to and from weighted MaxSAT, and the WBO core-guided solver with its benchmark counts.
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.