Research map / Learning theory and algorithms / Combinatorial and search optimization
Farsighted Probabilistic Sampling: A General Strategy for Boosting Local Search MaxSAT Solvers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Apply two-level farsighted probabilistic sampling to SATLike3.0 | SATLike3.0 · PMS_2018–PMS_2021 and WPMS_2018–WPMS_2021 | #win.: 111 vs 61; 212 vs 142; 189 vs 112; 108 vs 64; 115 vs 64; 222 vs 100; 183 vs 86; 84 vs 64 | Helped |
| Apply FPS to CCEHC | CCEHC · WPMS_2018–WPMS_2021 | #win.: 78 vs 58; 143 vs 94; 112 vs 89; 46 vs 59 | Mixed |
| Apply FPS to Dist | Dist · PMS_2018–PMS_2021 | #win.: 87 vs 73; 170 vs 152; 145 vs 119; 77 vs 74 | Mixed |
| Apply FPS to BandMaxSAT | BandMaxSAT · PMS_2018–PMS_2021 and WPMS_2018–WPMS_2021 | #win.: 105 vs 79; 203 vs 158; 172 vs 135; 91 vs 89; 102 vs 73; 179 vs 149; 153 vs 121; 83 vs 62 | Helped |
| Replace SATLike-c local search component with MaxFPS | SATLike-c · PMS_2018–PMS_2021 and WPMS_2018–WPMS_2021 | average score: 0.8682 vs 0.8399; 0.8796 vs 0.8734; 0.8696 vs 0.8457; 0.8802 vs 0.8508; 0.9084 vs 0.8931; 0.9091 vs 0.8810; 0.8868 vs 0. | Helped |
| Use FPS's best sampled single-variable/pair escape choice instead of random walk (ablation) | MaxFPS · PMS and WPMS benchmarks | #win.: 104 vs 75; 202 vs 172; 163 vs 140; 98 vs 89; 119 vs 69; 212 vs 123; 177 vs 104; 89 vs 61 | Helped |
| Add two-level look-ahead to the single-flip baseline, retaining random-walk escape (ablation) | SATLike3.0 · PMS and WPMS benchmarks | #win.: 106 vs 63; 206 vs 142; 161 vs 112; 105 vs 68; 90 vs 92; 188 vs 131; 156 vs 116; 71 vs 75 | Helped |
| Extend two-level look-ahead to three levels (ablation) | MaxFPS · PMS and WPMS benchmarks | #win.: 96 vs 44; 194 vs 103; 148 vs 86; 89 vs 58; 85 vs 57; 181 vs 92; 164 vs 61; 83 vs 32 | Hurt |
| Perform look-ahead when a single-flip improvement already exists (ablation) | MaxFPS · PMS and WPMS benchmarks | #win.: 96 vs 80; 194 vs 166; 148 vs 136; 89 vs 85; 85 vs 70; 181 vs 144; 164 vs 112; 83 vs 51 | Hurt |
| Remove early stopping after finding an improving variable pair (ablation) | MaxFPS · PMS and WPMS benchmarks | #win.: 106 vs 85; 198 vs 186; 177 vs 161; 96 vs 90; 109 vs 92; 188 vs 164; 160 vs 133; 78 vs 76 | Hurt |
Closest papers by meaning
- Better Understandings and Configurations in MaxSAT Stochastic Local Search Solvers via Anytime Performance Analysis (AAAI 2025 · similarity 0.92)
- Enhance Diversified Top-k MaxSAT Solving by Incorporating New Strategy for Generating Diversified Initial Assignments (Student Abstract) (AAAI 2024 · similarity 0.87)
- Improving the Lower Bound in Branch-and-Bound Algorithms for MaxSAT (AAAI 2025 · similarity 0.85)
- Theoretical and Empirical Analysis of Cost-Function Merging for Implicit Hitting Set WCSP Solving (AAAI 2024 · similarity 0.84)
- Automatic Core-Guided Reformulation via Constraint Explanation and Condition Learning (AAAI 2024 · similarity 0.84)
- Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization (NeurIPS 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.