Introduction
The Set Cover Problem (SCP) and Dominating Set Problem (DSP) are fundamental NP-hard optimization challenges with extensive applications in industrial scheduling, logistics, and network design. While these problems can be encoded into Weighted Partial MaxSAT (WPMS), general-purpose solvers often fail to exploit the specific logical structures inherent in these translations. Researchers have introduced DomSAT, a specialized local search solver designed to bridge this gap by leveraging the unique "monotone" structure of SCP and DSP encodings.
The DomSAT Framework
DomSAT distinguishes itself by recognizing that when SCP or DSP are translated into logic, the resulting formulas possess a specific shape: hard clauses (requirements) contain only positive literals, while soft clauses (costs) represent the negation of picking an item. This monotonicity implies that adding items never violates a hard constraint; it only increases the total cost.
The solver operates in three distinct phases:
- Construction: The problem is simplified using three novel reduction rules based on "dominating relations." For instance, if picking Item A covers a superset of what Item B covers at a lower cost, Item B is pruned. A greedy heuristic then generates an initial feasible solution.
- Local Search: The core engine utilizes a four-level variable selection heuristic:
- Descent Mode: Swaps items to reduce cost while maintaining validity.
- Exploitation Mode: Selects variables to satisfy constraints while minimizing cost impact.
- Aspiration Mode: Employs a "two-variable flip" to escape local optima.
- Perturbation Mode: Introduces randomness to explore new search spaces.
- Recovery: The simplified variables are mapped back to the original problem space to provide the final assignment.
A critical innovation in DomSAT is its scoring function, which calculates the ratio of satisfied constraints to cost increase: $score(x) = hscore(x) / |sscore(x)|$. Additionally, the solver employs a streamlined "one-sided configuration checking" to prevent cycling, applying it only when a variable is currently unselected.
Experimental Evaluation
The authors evaluated DomSAT against a diverse array of benchmarks, including the OR-Library (weighted SCP), Steiner Triple Systems (unweighted SCP), and massive real-world graphs for DSP. Crucially, they tested the solver on industrial "Rail" instances—large-scale weighted SCP problems derived from Italian railway scheduling.
Key Results
DomSAT demonstrated significant superiority over state-of-the-art solvers such as WCC (specialized SCP), FastMWDS (specialized DSP), and top-tier MaxSAT solvers like Loandra and Open-wbo.
- Industrial Scale Performance: On the massive Rail benchmarks, DomSAT consistently found lower-cost solutions than all competitors, often in significantly less time.
- DSP Dominance: In a test of 130 Dominating Set instances, DomSAT identified the best-known solution in 124 cases, whereas the next best solver (FastWMDS) succeeded in only 18.
- Impact of Reductions: Ablation studies confirmed that the reduction rules are vital; without them, performance on industrial-scale data degraded significantly.
Conclusion
By specializing for the monotone structure of Set Cover and Dominating Set problems, DomSAT outperforms general-purpose MaxSAT solvers on industrial-scale benchmarks. While its specialization limits its use on general MaxSAT problems (e.g., hardware verification), it provides a powerful template for solving other combinatorial problems with similar structures, such as the Steiner Tree Problem or Set Partitioning.
Summary updated