Research map / Learning theory and algorithms / Combinatorial and search optimization
Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach
Hannes Ihalainen, Dieter Vandesande, André Schidler, Jeremias Berg, Bart Bogaerts, Matti Järvisalo
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use numerically exact mode in SCIP instead of floating point | SCIP · PBO instances | instances solved: 913 -> 762 | Hurt |
| Use reified solution-improving constraints instead of plain SIS | SIS · PBO instances (single) | instances solved: 672 -> 651 | Hurt |
| Add core-boosting to solution-improving search (ablation) | SIS · PBO instances (single) | instances solved: 672 -> 716 | Improved |
| Add Roundingsat verification of optimal solutions (OptLB hybrid) to Gurobi with SIS + CB | SIS + CB · PBO instances | instances solved: 716 -> 746 | Improved |
| Verify all lower bounds (AllLB) instead of only optimal solution (OptLB) | SIS + CB hybrid · PBO instances | instances solved: 746 -> 737 | Hurt |
| Verify only forced lower bounds (ForceLB) instead of OptLB | SIS + CB hybrid · PBO instances | instances solved: 746 -> 731 | Hurt |
| Use OptLB hybrid instead of single solver for reified SIS | SIS Reified · PBO instances | instances solved: 651 -> 704 | Improved |
| Add stochastic local search to Gurobi hitting set computation | Gurobi · PBO instances | instances solved: +17 | Improved |
| Add stochastic local search to Exact SCIP (ablation) | Exact SCIP · PBO instances | instances solved: +44; memory -0.48 GB | Improved |
| Add stochastic local search to core-guided hitting set | Core Guided · PBO instances | instances solved: +41 | Improved |
| Add stochastic local search to OptLB hybrids (ablation) | SIS + CB OptLB · PBO instances | instances solved: +3 | Improved |
| Add stochastic local search to SIS (ablation) | SIS · PBO instances | average memory (GB): +0.02 | No clear effect |
Closest papers by meaning
- Cutting to the Core of Pseudo-Boolean Optimization: Combining Core-Guided Search with Cutting Planes Reasoning (AAAI 2021 · similarity 0.88)
- Theoretical and Empirical Analysis of Cost-Function Merging for Implicit Hitting Set WCSP Solving (AAAI 2024 · similarity 0.86)
- Certifying Parity Reasoning Efficiently Using Pseudo-Boolean Proofs (AAAI 2021 · similarity 0.85)
- A Sharp Leap from Quantified Boolean Formula to Stochastic Boolean Satisfiability Solving (AAAI 2021 · similarity 0.85)
- On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? (AAAI 2024 · similarity 0.83)
- Unifying Decision and Function Queries in Stochastic Boolean Satisfiability (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
