Research map / Learning theory and algorithms / Combinatorial and search optimization
Improving Exact Algorithm for Pseudo Boolean Optimization with Two New Phase Selection Heuristics
Yujiao Zhao, Yizhan Xiang, Jiangnan Li, Yiyuan Wang, Minghao Yin
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 |
|---|---|---|---|
| add TORC optimistic phase selection | Exact · PB16 (1600 inst) | objective value: degraded 291 instances, improved 130 | Hurt |
| add RTORC and RLRP phase strategies plus local search | Exact · PB16 (1600 inst) | #S solved: 1031 -> 1060 | Improved |
| add RTORC and RLRP plus local search | Exact · PB16 (1600 inst) | #win: 1012 -> 1194 | Improved |
| add RTORC and RLRP plus local search | RoundingSat-log · PB25 (555 inst) | #S solved: 283 -> 326 | Improved |
| add RTORC and RLRP plus local search | RoundingSat-nolog · PB24 (478 inst) | #win: 287 -> 354 | Improved |
| add RTORC (replacing solution-based phase saving) (ablation) | Exact-PS · PB16 (1600 inst) | #win vs variant: better on 295, worse on 227 instances | Improved |
| add RLRP rephase (ablation) | Exact-PS · PB16 (1600 inst) | #win vs variant: better on 304, worse on 244 instances | Improved |
| add local search for initial upper bound (ablation) | Exact-PS · PB16 (1600 inst) | #win vs variant: better on 546, worse on 307 instances | Improved |
| tune RLRP parameters delta, beta, lambda, Tp (ablation) | Exact-PS · sensitivity sets | #solved: fluctuation within 2 instances | No clear effect |
| combine PBO solver with SCIP (hybrid) | Exact-PS · PB24 (478 inst) | #S solved: 263 -> 288 | Improved |
Closest papers by meaning
- (1+1) Genetic Programming with Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error (AAAI 2025 · similarity 0.82)
- Retrieval-Guided Reinforcement Learning for Boolean Circuit Minimization (ICLR 2024 · similarity 0.81)
- CEGAR-Based Approach for Solving Combinatorial Optimization Modulo Quantified Linear Arithmetics Problems (AAAI 2024 · similarity 0.81)
- MetaBox-v2: A Unified Benchmark Platform for Meta-Black-Box Optimization (NeurIPS 2025 · similarity 0.81)
- EARL-BO: Reinforcement Learning for Multi-Step Lookahead, High-Dimensional Bayesian Optimization (ICML 2025 · similarity 0.81)
- Meta-Black-Box-Optimization through Offline Q-function Learning (ICML 2025 · similarity 0.81)
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.
