Local-Search Techniques for Boolean Combinations of Pseudo-Boolean Constraints

Lengning Liu, Miroslaw TruszczynskiAAAI 2006

Abstract

This paper introduces a novel logic, Propositional Logic with Pseudo-Boolean constraints ($PL(PB)$), designed to model complex search problems more concisely than standard Conjunctive Normal Form (CNF). By adapting Stochastic Local Search (SLS) techniques—specifically WalkSAT and RNovelty+—to operate directly on $PL(PB)$ descriptions, the authors circumvent the exponential size blow-up associated with CNF conversion. The core innovation involves using combinatorial formulas to calculate "virtual" break and make counts, allowing the solver to navigate the search space efficiently. Experimental results across four combinatorial domains demonstrate that this approach significantly outperforms traditional solvers like wsat(oip) in both speed and reliability.

Introduction

Most modern automated reasoning relies on SAT solvers, which typically require input in Conjunctive Normal Form (CNF). While CNF is a standard "OR"-based format, many real-world constraints—such as "at most $k$ items can be selected" or "the total weight must exceed $w$"—are more naturally expressed as pseudo-boolean (PB) constraints (linear inequalities over 0-1 variables).

Translating these PB constraints into CNF often leads to a "representation explosion," where the resulting file is exponentially larger than the original problem description. This size blow-up hinders the efficiency of standard solvers. While previous research has addressed solvers that handle PB constraints directly, this paper tackles the more complex challenge of boolean combinations of these constraints (e.g., "Constraint A must be true OR Constraint B must be true"), a common requirement in sophisticated configuration and optimization tasks.

Methods: The $PL(PB)$ Formalism and Virtual Counts

The authors propose the Propositional Logic with Pseudo-Boolean constraints ($PL(PB)$) to provide a high-level modeling language. To solve theories within this logic, they adapted Stochastic Local Search (SLS) heuristics, specifically WalkSAT (skc) and RNovelty+ (rnp).

The primary technical hurdle in local search is deciding which variable to "flip" based on how many clauses would become unsatisfied (the "break-count") or satisfied (the "make-count"). In a $PL(PB)$ framework, the solver avoids building the explicit CNF theory ($cl(T)$) to prevent memory issues. To solve this, the authors derived combinatorial formulas using binomial coefficients that allow the solver to estimate these counts directly from the high-level $PL(PB)$ description. These "virtual counts" allow the solver to maintain the agility of local search while leveraging the modeling power of pseudo-boolean logic.

Experimental Evaluation

The authors implemented two solvers, wsat(plpb)-skc and wsat(plpb)-rnp, and evaluated them against 50 random instances for each of four distinct search problems:

  1. Vertex-cover (vcov): Identifying a subset of vertices that covers every edge in a graph.
  2. Bounded spanning tree (bst): Finding a spanning tree where the sum of edge weights at each vertex remains below a specific threshold.
  3. Weighted dominating set (wdm): A graph problem involving vertex weights and neighborhood coverage requirements.
  4. Weighted n-queens (wnq): A variation of the classic puzzle where squares have weights, and queens must satisfy distance and total weight constraints.

Results and Discussion

The experimental results, summarized in the table below, demonstrate that the $PL(PB)$ approach is significantly faster and more reliable than the standard wsat(oip) solver.

Table 1: Performance comparison across four problem domains (vcov, bst, wdm, wnq). Metrics shown as Solved / Fastest / Median Time (seconds).

Key findings include:

  • Speedup in Complex Problems: On the "Weighted n-queens" problem, wsat(plpb)-skc solved all 50 instances with a median time of ~52 seconds. In contrast, wsat(oip) only managed to solve 2 instances before hitting the 1000-second timeout.
  • Reliability: For the "Weighted dominating set" problem, wsat(plpb)-rnp was the fastest in 26 out of 50 cases, with a median runtime of 0.64 seconds, while wsat(oip) failed to solve the vast majority of instances.
  • Efficiency in Runtime Distribution: As shown in the runtime distribution for the "Bounded spanning tree" problem, the $PL(PB)$ variants reach a 1.0 probability of solving an instance much faster than the baseline solver.
Figure 1: Probability of solving instances over time for the bounded spanning tree problem (v=30, e=240, w=15).

Conclusion

The $PL(PB)$ framework proves that conciseness is a form of power in automated reasoning. By treating high-level logic as a data structure, solvers can "see" global problem structures that are obscured in massive CNF translations. The "virtual" shortcut—calculating clause behavior mathematically rather than materializing the clauses—enables high-performance local search on complex constraints.

Future work remains to address numerical overflows caused by binomial coefficients in very large problems and to further refine heuristics like RNovelty+ by exploring the interaction between "noise," "age," and pseudo-boolean constraints.

Summary updated

BibTeX
@inproceedings{liu2006local,
  author = {Lengning Liu and Miroslaw Truszczynski},
  title = {{Local-Search Techniques for Boolean Combinations of Pseudo-Boolean Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure