PB-smodels a Pseudo-Boolean Solver

Gayathri NamasivayamAAAI 2006

Introduction

Pseudo-Boolean (PB) constraints—linear inequalities where variables are restricted to 0 or 1—are essential for modeling complex search and optimization problems in logistics, hardware verification, and scheduling. While specialized PB-solvers often rely on techniques derived from SAT solving, PB-smodels introduces a novel approach by bridging the gap between PB solving and Answer Set Programming (ASP). By repurposing the smodels engine, which natively handles "weight constraints," this system demonstrates that general-purpose logic programming solvers can be highly competitive in the PB domain.

The PB2smodels Translation

The core contribution is the PB2smodels translation procedure. This tool converts PB constraints into logic programs that smodels can process. The mapping follows a mathematically rigorous transformation:

  1. Variables: Every 0-1 variable is treated as a propositional atom in a "choice rule," allowing the solver to explore both truth values.
  2. Inequalities: Linear inequalities (e.g., $\sum w_i x_i \leq c$) are translated into logic rules where the body is a weight constraint with corresponding upper or lower bounds.
  3. Optimization: Statements like minimize or maximize are mapped directly to smodels optimization rules.

The author provides formal proof (Theorem 1) ensuring that the "stable models" (solutions) of the generated logic program correspond exactly to the solutions of the original PB constraints.

Experimental Evaluation

The performance of PB-smodels was evaluated against two state-of-the-art solvers, MiniSat+ and Pueblo, using two primary datasets:

  • PB 2005 Competition Benchmarks: 386 optimization instances from the official evaluation.
  • Randomly Generated Instances: A suite of classic combinatorial problems including Weighted N-queens, the Traveling Salesperson Problem (TSP), and the Weighted Dominating Set problem.

Key Results and Insights

The results suggest that solver performance is highly dependent on problem structure. While SAT-based solvers like MiniSat+ excelled at specific competition benchmarks, the logic-programming approach of PB-smodels proved significantly more robust on randomized, structured search problems.

Table 1: Comparison of instances solved by PB-smodels, MiniSat+, and Pueblo across PB'05 and Random benchmarks.

As shown in Table 1, PB-smodels was the clear winner on random instances, solving 400 instances compared to 380 by Pueblo and 298 by MiniSat+. On the PB'05 optimization set, PB-smodels solved 144 instances; while lower than its competitors, the performance remained competitive for a general-purpose tool.

Figure 1: Cumulative number of TSP instances solved within specific time intervals.

In the Traveling Salesperson Problem (11 cities, length bound 25), PB-smodels showed a superior run-time distribution. As illustrated in Figure 1, it solved more instances within shorter time intervals (e.g., <5 seconds) than both MiniSat+ and Pueblo, maintaining this lead across the testing window.

Conclusion

The success of PB-smodels highlights the cross-domain utility of ASP solvers. Because their internal weight constraint mechanisms are mathematically analogous to PB inequalities, they are naturally well-suited for these problems. Future work will likely involve refining the translation process to better handle industrial optimization benchmarks, potentially combining the strengths of SAT-based learning with ASP's expressive constraint handling.

Summary updated

BibTeX
@inproceedings{namasivayam2006pb,
  author = {Gayathri Namasivayam},
  title = {{PB-smodels a Pseudo-Boolean Solver}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure