Research map / Learning theory and algorithms / Combinatorial and search optimization
Encoding Multi-Valued Decision Diagram Constraints as Binary Constraint Trees
Ruiwei Wang, Roland H.C. Yap
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 |
|---|---|---|---|
| Reduce the DTBE with the four TBE reduction rules (ablation) | MDD constraints · XCSP table benchmarks | total solving time: TBE is the fastest propagator on 71% of instances; up to 12 times faster than CT and 98 times faster than CD | Improved |
| Apply all four reduction rules rather than keeping the original DTBE (ablation) | MDD constraints · XCSP table benchmarks | evaluated size: up to 2166 times smaller | Improved |
| Apply Rule 4 to DTBE (ablation) | MDD constraints · XCSP table benchmarks | evaluated size | Improved |
| Use DTBE without reduction rules instead of CD (ablation) | MDD constraints · Car Sequencing, Pentominoes, and Nurse Scheduling | search nodes/s | No clear effect |
| Reduce the DTBE to TBE using Algorithm 1 (ablation) | MDD constraints · Car Sequencing C-3 | search nodes/s: 530 -> 814 | Improved |
| Reduce the DTBE to TBE using Algorithm 1 (ablation) | MDD constraints · Pentominoes P-20 | search nodes/s: 15 -> 246 | Improved |
| Reduce the DTBE to TBE using Algorithm 1 (ablation) | MDD constraints · Nurse Scheduling N-4 | search nodes/s: 43 -> 3728 | Improved |
| Use a BCT GAC propagator rather than CD | MDD constraints · XCSP table benchmarks | solving time: up to 98 times faster | Improved |
| Use a BCT GAC propagator rather than CT | table constraints encoded as MDDs and BCTs · XCSP table benchmarks | solving time: up to 12 times faster | Improved |
| Reduce BCT size more strongly (ablation) | TBE propagator versus CD · XCSP table benchmarks | solving time | Improved |
Closest papers by meaning
- On the Modelling of Constraints with Tractable Logical Operators (AAAI 2025 · similarity 0.86)
- Encoding Constraints as Binary Constraint Networks Satisfying BTP (AAAI 2024 · similarity 0.85)
- Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms (ICML 2025 · similarity 0.82)
- Using Clustering to Strengthen Decision Diagram Bounds for Discrete Optimization (AAAI 2024 · similarity 0.82)
- The Impact of Literal Sorting on Cardinality Constraint Encodings (AAAI 2025 · similarity 0.81)
- Witty: An Efficient Solver for Computing Minimum-Size Decision Trees (AAAI 2025 · similarity 0.80)
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.
