BDD-based Constraint Solving

Technique

BDD-based constraint solving is a constrained-random stimuli generation technique that builds a Binary Decision Diagram representing the feasible solution space of a set of constraints. It is valued because, once built, a BDD can produce solutions with a uniform distribution over that space. The cited evidence positions BDD-based solving as one tier of a multi-solver architecture (used in eUVM for medium-complexity multi-domain constraints and in CRAVE as part of a portfolio with SAT/SMT), and contrasts it with SAT-only approaches such as PyVSC.

First seen 5/25/2026

Last seen 9/27/2026

Evidence 8 chunks

Wiki v2

WIKI

Overview

BDD-based constraint solving is a constrained-random verification technique in which a Binary Decision Diagram (BDD) is constructed to represent the satisfying assignments of a set of constraints. The cited evidence frames it as one tier within multi-solver constrained-random verification flows rather than as a universal replacement for SAT or SMT solving.

Strengths and Limits

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

3 connections

CRAVE ← implements 100% 2e

CRAVE integrates BDD-based constraint-solving techniques.

CRAVE ← uses 100% 2e

The text states BDD-based techniques have been integrated into CRAVE’s solver portfolio, indicating use of this technique.

eUVM ← uses 100% 1e

eUVM uses BDD-based solvers to handle multi-domain constraints of medium complexity.

LINKED ENTITIES

1 links

CRAVE USES Extracted graph relationship

CITATIONS

5 sources

5 citations — click to expand

[1] CRAVE integrates BDD-based and SAT/SMT-based techniques for constraint-solving using a portfolio approach to enable very fast generation of constraint solutions. CRAVE - Institute for Computer Science, JKU Linz

[2] CRAVE uses a portfolio approach running an SMT-based and a BDD-based constraint-solver in parallel on the same constraints, and prefers the BDD once it is built because it guarantees a uniform distribution among all solutions; metaSMT is used as a unified engine-independent interface. CRAVE: An Advanced Constrained Random Verification Library (SoC 2012 paper)

[3] The CRAVE metaSMT backend exposes both BDD-related engines (CUDD, AIGER) and SAT/SMT engines (SWORD, Z3, Boolector, MiniSAT, PicoSAT), and CRAVE's constraint analyzer resolves contradictions formally. CRAVE: An Advanced Constrained Random Verification Library (SoC 2012 paper)

[4] In eUVM, BDD-based solvers handle multi-domain constraints of medium complexity, while a native solver handles elementary single-domain constraints and SMT/SAT solvers handle convoluted constraints that BDDs cannot handle (Z3, Boolector, CMSGen named as examples); compile-time parsing and analysis of constraints are attributed to D-language code introspection and CTFE. eUVM DVCon paper (previous article source chunks)

[5] PyVSC is described as not deploying a BDD solver and instead relying completely on SAT solvers for multi-variable constraints, resulting in a non-uniform spread of solutions compared with SystemVerilog and eUVM; at the time of the paper, CRAVE could not handle complex RISC-V-DV constraints. eUVM DVCon paper (previous article source chunks)