wikillm

Paper · 2009-03-04 · cs.AI, cs.LO

Algorithms for Weighted Boolean Optimization

Proposes Weighted Boolean Optimization (WBO), one framework that covers weighted partial MaxSAT and pseudo-Boolean optimization, and an unsatisfiability-based algorithm for it. Cores are relaxed with fresh variables and weights are split by the core's minimum weight. On 243 industrial-style instances, the unsatisfiability-based MSUnCore solves the most (189), ahead of WBO (172 printed).

Maximum satisfiability (MaxSAT)Pseudo-Boolean optimization (PBO)Constraint satisfactionmaxsatpseudo-booleansat-solvingcombinatorial-optimization

arXivPDFMarkdown9 min read

AI-compiled by claude-haiku-5-5 on 2026-11-13, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

Some puzzles ask you to pick true or false for many yes/no variables so that all hard rules hold, and, among those choices, the total penalty of broken soft preferences is as small as possible. Two research communities built solvers for this kind of problem under different names, MaxSAT and pseudo-Boolean optimization, using different rule formats.

This paper builds one format that covers both, called Weighted Boolean Optimization. It also gives a solving method that works by finding small groups of rules that cannot all be satisfied at once. The solver then pays for one rule in each group, relaxes it, and tries again. The result is a lower bound that keeps rising until it meets a real solution.

In the authors' experiments, the method that treats such groups as the main tool solved the most instances in their test set.

TL;DR

  • Defines WBO: hard and soft pseudo-Boolean constraints with integer weights, minimising the weight of violated soft constraints §4.
  • Extends the unsatisfiability-based MSU1 (Fu and Malik) method to weighted partial MaxSAT by splitting a clause's weight at the core's minimum §3.
  • Extends the same method to WBO, so one solver handles MaxSAT, weighted MaxSAT and PBO, with native pseudo-Boolean constraints §4.1.
  • Author-reported: MSUnCore (the weighted-partial MaxSAT extension) solves 189 of 243 instances, WBO 172 as printed tab. 2 tab. 3.

Problem

Weighted partial MaxSAT and pseudo-Boolean optimization (PBO) are separate formalisms with translations between them, but in 2009 their solvers evolved separately §1. Unsatisfiability-based MaxSAT solvers, which find a core (an unsatisfiable subset of clauses) with a SAT solver and relax it, had been limited to unweighted and partial variants and to a restricted form of PBO §1. Encoding weights by copying a clause as many times as its weight is stated to be unlikely to scale for large weights §3.

Method

Problem definitions

Pseudo-Boolean optimization asks for an assignment that satisfies linear constraints with non-negative integer coefficients and minimises a linear objective. Any pseudo-Boolean formulation can be brought into this normal form §2.2:

\begin{aligned} \text{minimize } & \sum_{j \in N} c_j\, x_j \\ \text{subject to } & \sum_{j \in N} a_{ij}\, l_j \ge b_i, \\ & l_j \in \{x_j, \bar{x}_j\},\ x_j \in \{0,1\},\ a_{ij}, b_i, c_j \in \mathbb{N}_0^{+} \end{aligned} eq. 1 §2.2

Weighted partial MaxSAT has hard clauses that must hold and weighted soft clauses whose weight is paid when violated. Hard clauses can also be written as weighted clauses with a weight above the sum of all soft weights §2.1.

Weighted Boolean Optimization generalises both. Hard and soft constraints are pseudo-Boolean constraints. Each soft constraint has a positive integer weight, and the goal is to satisfy all hard constraints while minimising the weight of violated soft constraints §4.

Translations

  • Soft clause to PBO. For soft clause \omega_i = (l_1 \vee \dots \vee l_k) with weight c_i, add a selection variable s_i and the constraint s_i + \sum_j l_j \ge 1. Minimise \sum_i c_i s_i §2.3. Worked example eq. 2 eq. 3.
  • PBO objective to MaxSAT. For each objective term c_j x_j, add the soft unit clause (\bar{x}_j) with weight c_j. Pseudo-Boolean constraints become hard clauses via a PB-to-CNF encoding §2.3. Worked example eq. 4 eq. 5.

Unsatisfiability-based MaxSAT (MSU1, Fu and Malik)

alg. 1 repeatedly calls a SAT solver on the working formula. On UNSAT it takes the returned core, gives every soft clause in it a fresh relaxation variable, and adds an Equals1 constraint over these variables. Equals1 may be replaced by AtMost1 without affecting correctness §2.4. The paper describes the current best-performing variant as an optimised version of this method §2.4.

Weighted extension (WMSU1)

alg. 2 keeps a lower bound cost_lb and the cost of each clause.

Pseudocode
# Unsatisfiability-based (partial) weighted MaxSAT  [alg. 2]
# Input:  weighted partial CNF phi (hard clauses carry no cost)
# Output: lower bound on the minimum weight of violated soft clauses

def wmsu1(phi):
    # Working formula, initially phi  [alg. 2]
    working = phi
    # Lower bound on the optimum, starts at zero  [alg. 2]
    cost_lb = 0
    while True:
        # SAT call; on UNSAT the solver returns a core  [alg. 2]
        status, core = sat(working)
        if status == SAT:
            # Satisfiable: cost_lb is the optimum  [alg. 2]
            return cost_lb
        # Smallest soft weight in the core  [alg. 2]
        min_c = min(cost[w] for w in core if not hard(w))
        # Each core raises the bound by its smallest weight  [alg. 2]
        cost_lb = cost_lb + min_c
        relax_vars = []
        for clause in core:
            if hard(clause):
                continue
            # Fresh relaxation variable for this clause  [alg. 2]
            r = new_variable()
            relax_vars.append(r)
            relaxed = clause + [r]
            if cost[clause] > min_c:
                # Split: the copy takes min_c, the original keeps the rest
                # and stays in the working formula  [alg. 2]
                cost[clause] = cost[clause] - min_c
                working.add(relaxed, cost=min_c)
            else:
                # Weight fully used: replace the clause by its copy  [alg. 2]
                working.remove(clause)
                working.add(relaxed, cost=min_c)
        # Equals1 over the new relaxation variables, all hard  [alg. 2]
        working.add_hard(exactly_one(relax_vars))

The paper's worked example §3 takes the core \{(\bar x_2 \vee x_3), (\bar x_1 \vee x_3), (\bar x_3, 6), (x_1 \vee x_2, 3)\} from the instance of eq. 2. Here min_c = 3. The clause of weight 6 becomes a weight-3 relaxed copy and a weight-3 original. The clause of weight 3 is replaced by its relaxed copy.

Weighted Boolean Optimization (WBO)

The core-based loop of alg. 2 carries over, with three changes §4.1:

  1. The SAT solver is replaced by a pseudo-Boolean solver that can also return an unsatisfiable subset of pseudo-Boolean constraints. The paper does not describe how this extraction works.

  2. A relaxed constraint is built from the original \omega = \sum_j a_j l_j \ge b by adding b \cdot r:

    \omega_R = b\, r + \sum_j a_j l_j \ge b §4.1

  3. The Equals1 constraint is added directly as the pseudo-Boolean constraint \sum_{r \in V_R} r = 1, with no CNF encoding §4.1.

Sharing relaxation variables. Two soft constraints in one core may share a relaxation variable r if there is a literal x_k with x_k in the first, \bar x_k in the second, and the coefficient of x_k in each constraint is at least that constraint's bound §4.1. Then at most one of the two can be violated, as the two conditions cannot both fail under the same assignment of x_k. The worked example eq. 8 reduces four relaxation variables to two eq. 9 §4.1.

Choosing which constraints share. Finding the fewest relaxation variables maps to a maximum-cardinality matching in an undirected graph. Vertices are the constraints of the core. Edges join pairs that may share a variable. The matching can be solved in polynomial time §4.1, but the prototype uses a greedy heuristic §4.1.

Other PBO and MaxSAT algorithms. The paper sketches two alternatives: extending PBO solvers with relaxable soft constraints and a weighted-sum cost, and extending branch-and-bound MaxSAT solvers to pseudo-Boolean constraints. It notes that these refine an upper bound, whereas the core-based method refines a lower bound §4.2.

Hyperparameters

NameValueWhereNotes
CPU time limit1800 s§5per instance
RAM limit1 GB§5
Hardwarecluster of Linux AMD Opteron 2 GHz servers, 1 GB RAM§5core count not stated
Instance formatoriginal representation of each class§5no re-encoding, to avoid bias
SAT engine, WBOMinisat2§5
SAT engine, MSUnCorePicoSAT§5
Relaxation sharinggreedy matching§4.1greedy order not stated
Equals1 in WBOpseudo-Boolean \sum r = 1§4.1the example uses \le 1, see Pitfalls
Solver versions, number of runs, random seedsnot stated

Results

Author-reported. Setup: three instance classes, 243 instances in total tab. 1. The IND class has 110 instances, is weighted partial MaxSAT, and was drawn from a MaxSAT Evaluation that the paper lists as forthcoming. The FIR class (59 instances) and the SYN class (74 instances) are partial MaxSAT instances taken from the 2007 and 2005 Pseudo-Boolean Evaluations tab. 1. Solvers ran on the hardware in the Hyperparameters table §5.

Solved instances, weighted MaxSAT solvers tab. 2:

ClassWMaxSatzMiniMaxSatIncWMaxSatzCloneSAT4J (MS)MSUnCore
IND110110010110
FIR7143351045
SYN222919132134
Total (of 243)40431621841189

Solved instances, PBO and WBO solvers tab. 3:

ClassBSOLOPBSPuebloMinisat+SAT4J (PB)WBO
IND1700060110
FIR20111422739
SYN511930302233
Total (of 243), as printed8830445289172

The WBO total is printed as 172, but its row sums to 182 (see Pitfalls).

Qualitative results from the text and fig. 1 (cumulative run times for IncWMaxSatz, MSUnCore and WBO over all instances, not reported numerically):

  • Among MaxSAT solvers, IncWMaxSatz, MSUnCore and WBO solve all IND instances. Other MaxSAT solvers solve few of them §5 tab. 2.
  • MSUnCore has the best overall run times, followed by WBO and IncWMaxSatz. IncWMaxSatz can be faster than WBO on the easiest IND instances §5 fig. 1.
  • Among PBO solvers, SAT4J (PB) and BSOLO score best. SAT4J (PB) solves more instances than SAT4J (MaxSAT) §5 tab. 2 tab. 3.
  • The abstract claims orders-of-magnitude gains for unsatisfiability-based MaxSAT over dedicated algorithms [abstract]. The tables give solved counts only, so the size of the gain is not measured in them.

Paper vs code

No official code. The paper has no code link, no project page and no URL in its bibliography (checked in the LaTeX source and the .bbl file). A GitHub repository search for wbo maxsat returned sat-group/open-wbo and forks, which are later solvers from a different line of development, not the 2009 prototype. They were not used. A GitHub search for msunCore returned no repository. A first search with the title words and a malformed organisation filter returned HTTP 422 and was not retried.

Pitfalls

  • Table 3 total does not match its rows. The WBO row is 110 + 39 + 33 = 182, but the printed total is 172. The text ranks WBO second after MSUnCore and above IncWMaxSatz (162), which holds for either figure. The per-class values are read as printed.
  • Caption and text disagree. The text says the tables summarise instances aborted by each solver. The captions say Solved. The numbers match the solved reading: IND shows 110 for the three best solvers, which is all 110 IND instances. Use the solved reading.
  • Correctness is argued, not proved. The theorem for WMSU1 (the returned value is the minimum cost of unsatisfied clauses) rests on the earlier discussion in the section and on the cited Fu and Malik proof [FM06] §3. The card has no self-contained proof.
  • Splitting keeps the original clause. When a clause's weight exceeds min_c, the original stays in the working formula with its reduced weight. The copy with weight min_c joins it. A clause can therefore be relaxed in several rounds alg. 2. The paper does not say how a clause is identified across rounds. The algorithm comment says relaxed clauses are "tagged non-auxiliary" without defining the tag alg. 2.
  • Equals1 versus AtMost1 in WBO. Algorithm 2 and the text state \sum r = 1 §4.1 alg. 2. The worked example eq. 9 uses s_1 + s_2 \le 1. The paper does not explain the difference. Its MSU discussion says AtMost1 is enough for correctness §2.4, which would cover the example, but the claim for WBO is not stated.
  • Sharing needs both bounds. A relaxation variable is shared only when each constraint's coefficient on the opposite literals is at least its bound. Under a plain clause (bound 1) this is almost always true. For general pseudo-Boolean constraints it is a check to implement, not an assumption.
  • Greedy matching is not optimal. The prototype uses a greedy matching §4.1, so the number of relaxation variables may exceed the optimum. The greedy order and tie-breaking are not stated.
  • Pseudo-Boolean to CNF may blow up. For constraints beyond cardinality, arc-consistent CNF encodings can be exponential in the worst case, which the paper notes when comparing MSUnCore (CNF) with WBO (native) §5.
  • Instance and setup gaps. The IND class is listed as "to appear in MaxSAT Evaluation 2009" tab. 1. Availability of the instances is not stated, so the benchmark cannot be checked from the paper alone. Solver versions, the number of runs and seeds are not stated §5.
  • Commented-out material. Several blocks in the source are commented out with the comment environment, including an earlier version of the results tables and related-work text. They are not part of the published paper and are not cited here.
  • Figure 1 is qualitative. It shows cumulative run times for three solvers fig. 1. Numbers are not given, so do not read exact times from it.

Lineage

  • Builds on: Fu and Malik's MSU1.0 unsatisfiability-based MaxSAT algorithm [FM06] (not a card in this wiki), and the MSU family of later refinements [jpms-corr07, jpms-date08, jpms-sat08b] (not cards in this wiki).
  • Compared against: WMaxSatz, MiniMaxSat, IncWMaxSatz, Clone and SAT4J (MaxSAT) as weighted MaxSAT solvers; BSOLO, PBS, Pueblo, Minisat+ and SAT4J (PB) as PBO solvers §5.
  • Superseded by: not stated in content already on this wiki.

Source and license

Adapted from “Algorithms for Weighted Boolean Optimization” by Vasco Manquinho, Joao Marques-Silva, Jordi Planes (arXiv:0903.0843), used under http://creativecommons.org/licenses/by/3.0/. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors.