AI Paper Atlas

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

AAAI 2022 · Learning theory and algorithms › Combinatorial and search optimization · approach: Structure and complexity of constraint reasoning · 5 citations (OpenAlex)

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 changedWhereMeasuredEffect
Reduce the DTBE with the four TBE reduction rules (ablation)MDD constraints · XCSP table benchmarkstotal solving time: TBE is the fastest propagator on 71% of instances; up to 12 times faster than CT and 98 times faster than CDImproved
Apply all four reduction rules rather than keeping the original DTBE (ablation)MDD constraints · XCSP table benchmarksevaluated size: up to 2166 times smallerImproved
Apply Rule 4 to DTBE (ablation)MDD constraints · XCSP table benchmarksevaluated sizeImproved
Use DTBE without reduction rules instead of CD (ablation)MDD constraints · Car Sequencing, Pentominoes, and Nurse Schedulingsearch nodes/sNo clear effect
Reduce the DTBE to TBE using Algorithm 1 (ablation)MDD constraints · Car Sequencing C-3search nodes/s: 530 -> 814Improved
Reduce the DTBE to TBE using Algorithm 1 (ablation)MDD constraints · Pentominoes P-20search nodes/s: 15 -> 246Improved
Reduce the DTBE to TBE using Algorithm 1 (ablation)MDD constraints · Nurse Scheduling N-4search nodes/s: 43 -> 3728Improved
Use a BCT GAC propagator rather than CDMDD constraints · XCSP table benchmarkssolving time: up to 98 times fasterImproved
Use a BCT GAC propagator rather than CTtable constraints encoded as MDDs and BCTs · XCSP table benchmarkssolving time: up to 12 times fasterImproved
Reduce BCT size more strongly (ablation)TBE propagator versus CD · XCSP table benchmarkssolving timeImproved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy