Research map / Learning theory and algorithms / Combinatorial and search optimization
Prediction-Based Adaptive Variable Ordering Heuristics for Constraint Satisfaction Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PBAVOH, which represents binary search trees by NPD sequences and uses LSTM and GBDT predictors trained on easy instances to probe and select the best variable ordering heuristic for hard CSP instances.
Problem
Selecting an efficient variable ordering heuristic adaptively for each constraint satisfaction problem instance, since different VOHs vary greatly in performance on the same instance.
Approach
Represent binary branching search trees by the NPD sequence (numbers of positive decisions before each failure), and predict the total failure count of a search tree from its partial prefix with LSTM and GBDT models trained on easy instances, then choose the candidate VOH with the lowest predicted score during a probing phase.
Key results
- PBAVOH solves 381 of hard instances versus 285 for AST and 307 for SEVOH, with PAR2 of 182.7 versus 686.8 for SEVOH.
- PBAVOH selects efficient candidate VOHs for 307 of 356 hard instances (about 86%), compared with 285 (80%) for SEVOH.
- Over all 1876 instances PBAVOH solves 1328 instances, the highest among all compared methods, with PAR2 65.2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PBAVOH instead of FRBA on MiniZinc instances | CSP solving · MiniZinc instances (All) | solved instances: 1291 -> 1328 | Helped |
| Use PBAVOH instead of SEVOH on MiniZinc instances | CSP solving · MiniZinc instances (All) | PAR2 (1328): 238.1 -> 65.2 | Helped |
| Use PBAVOH instead of FRBA on hard MiniZinc instances | CSP solving · MiniZinc instances (Hard) | solved instances: 356 -> 381 | Helped |
| Use PBAVOH instead of SEVOH on hard MiniZinc instances | CSP solving · MiniZinc instances (Hard) | PAR2 (381): 686.8 -> 182.7 | Helped |
| Combine LSTM and GBDT prediction outputs rather than use SEVOH for candidate selection | PBAVOH candidate selection · Hard instances (356) | %Solved: 80% -> 86% | Helped |
| Combine LSTM and GBDT prediction outputs rather than use SEVOH for candidate selection | PBAVOH candidate selection · Hard instances (356) | %Best: 60% -> 49% | Hurt |
| Use GBDT rather than LSTM for candidate selection | PBAVOH · Hard instances (356) | %Solved: 84% -> 69% | Hurt |
Surprising findings
- Models trained on the 'unseen' problems (excluding the target problem) still outperform random selection, suggesting common structure in search trees across problems.
Limitations
- Only four candidate VOHs and one value selector are considered.
- Evaluation restricted to MiniZinc instances solved with the Choco solver.
Experimental setup
Datasets: MiniZinc benchmark suite (46 models, 1876 instances)
Benchmarks: MiniZinc benchmark suite
Metrics: number of solved instances PAR2 score of runtime
Baselines: AST SEVOH ABS CHS dom/wdegca.cd FRBA Time split solver Virtual best candidate Random selection
Builds on: SEVOH Activity-based Search Conflict-history Search Failure-based Search Adaptive Single Tournament
Closest papers by meaning
- Right Branches Matter in Failure-based Variable Ordering Heuristics (AAAI 2026 · similarity 0.93)
- Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction (ICML 2025 · similarity 0.83)
- Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (NeurIPS 2025 · similarity 0.83)
- The Impact of Literal Sorting on Cardinality Constraint Encodings (AAAI 2025 · similarity 0.83)
- EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulations (ICML 2025 · similarity 0.82)
- On the Modelling of Constraints with Tractable Logical Operators (AAAI 2025 · similarity 0.82)
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.