TL;DR
This paper presents a hybrid approach combining Mixed Integer Programming (MIP) and a core-guided MaxSAT solver to efficiently find minimum hitting sets. By strategically switching between these solvers based on instance characteristics and employing novel preprocessing techniques, they achieve a solution that can tackle all instances of the 2025 PACE challenge within the given time limits.
What Problem Does This Paper Address?
The paper tackles the Minimum Hitting Set (MHS) problem, a classic NP-complete problem. Given a collection of sets, the goal is to find the smallest possible set that contains at least one element from each of the given sets. This problem has applications in various fields, including constraint satisfaction and optimization. The authors are specifically addressing the challenge of solving MHS instances for the 2025 PACE (Programming Contest for Exact Computation) challenge, which requires efficient and robust solvers. While existing solvers like MaxSAT and MIP are powerful, neither can solve all instances within the tight time constraints of such competitions.
Methods
The authors propose a hybrid strategy that leverages the strengths of both MIP and MaxSAT solvers.
- Preprocessing: Two key preprocessing rules are introduced:
- Element Reduction: If element
vis present in every set thatuis in,ucan be removed from all sets. This is because any hitting set that hitsuwill also hitv, and replacinguwithvin a hitting set still yields a minimum hitting set. This rule is found to be crucial for performance. - Set Reduction: If set
S'is a subset of setS,S'can be removed. Any hitting set that intersectsSwill also intersectS'. This rule is found to be less impactful as solvers already handle this redundancy well. - Solver Selection: Instances with fewer than 250 distinct elements are passed to a MIP solver (specifically SCIP). Larger instances are handled by their custom MaxSAT solver.
- MaxSAT Solver: The core of their MaxSAT approach is the "core-guided" algorithm OLL, implemented using the Cadical SAT solver. Core-guided methods work by dissecting the MaxSAT problem into smaller "cores" and then using these cores to reformulate the problem, introducing structure that helps the underlying SAT solver find solutions more efficiently. They also incorporate an upper bound from a local search algorithm (NuWLS) to guide the search for cores and warm-start the MIP solver.
- Lower Bounds: For the MaxSAT solver, they employ lower bounds derived from finding large sets of disjoint cliques within the instance's structure. This helps initialize the solver with promising information.
Datasets
The paper evaluates their approach on the instances provided for the 2025 PACE challenge. No new datasets were introduced.
Key Insights and Ideas
- Hybridization is Key: Neither MIP nor MaxSAT alone is sufficient to solve all MHS instances within the PACE challenge constraints. A hybrid approach, intelligently switching between solvers, is essential for comprehensive performance.
- Preprocessing Matters: The element reduction preprocessing rule is not just a minor optimization; it's critical for enabling the MIP solver to handle certain instances effectively.
- Core-Guided MaxSAT Structure: The effectiveness of core-guided MaxSAT lies in its ability to introduce structure into the propositional encoding, making it easier for SAT solvers to navigate the search space. The choice of cores significantly impacts performance.
- Upper Bounds for Guidance: Using an initial upper bound from local search can significantly aid the MaxSAT solver in finding good "cores" and can also be used to warm-start the MIP solver.
Key Results
The paper states that their combined MIP and MaxSAT approach, with the described preprocessing, is able to solve all 100 public competition instances of the 2025 PACE challenge within the 30-minute time limit. While the MaxSAT solver alone could solve 94 instances, the hybrid approach ensures all are covered.
Limitations and Future Work
- Core Strategy: The authors acknowledge that they have not yet established a sufficiently robust strategy for finding (meta-)cores that consistently provides optimal results. This is identified as a key area for future research.
- Runtime Variability: Even with their successful approach, the runtimes for individual instances can vary by orders of magnitude, suggesting that further improvements in core selection or solver tuning could still be beneficial.
Summary updated