Calculating Valid Domains for BDD-Based Interactive Configuration
Calculating Valid Domains for BDD-Based Interactive
Configuration
Tarik Hadzic, Rune Moller Jensen, Henrik Reif Andersen
Computational Logic and Algorithms Group,
IT University of Copenhagen, Denmark
tarik@itu.dk,rmj@itu.dk,hra@itu.dk
Abstract. In these notes we formally describe the functionality of Calculating
Valid Domains from the BDD representing the solution space of valid configu-
rations. The formalization is largely based on the CLab [1] configuration frame-
work.
1 Introduction
Interactive configuration problems are special applications of Constraint Satisfaction
Problems (CSP) where a user is assisted in interactively assigning values to variables by
a software tool. This software, called a configurator, assists the user by calculating and
displaying the available, valid choices for each unassigned variable in what are called
valid domains computations. Application areas include customising physical products
(such as PC’s and cars) and services (such as airplane tickets and insurances).
Three important features are required of a tool that implements interactive configu-
ration: it should be complete (all valid configurations should be reachable through user
interaction), backtrack-free (a user is never forced to change an earlier choice due to
incompleteness in the logical deductions), and it should provide real-time performance
(feedback should be fast enough to allow real-time interactions). The requirement of
obtaining backtrack-freeness while maintaining completeness makes the problem of
calculating valid domains NP-hard. The real-time performance requirement enforces
further that runtime calculations are bounded in polynomial time. According to user-
interface design criteria, for a user to perceive interaction as being real-time, system
response needs to be within about 250 milliseconds in practice [2]. Therefore, the cur-
rent approaches that meet all three conditions use off-line precomputation to generate
an efficient runtime data structure representing the solution space [3,4,5,6]. The chal-
lenge with this data structure is that the solution space is almost always exponentially
large and it is NP-hard to find. Despite the bad worst-case bounds, it has nevertheless
turned out in real industrial applications that the data structures can often be kept small
[7,5,4].
2 Interactive Configuration
The input model to an interactive configuration problem is a special kind of Constraint
Satisfaction Problem (CSP) [8,9] where constraints are represented as propositional
formulas:
http://arxiv.org/abs/0704.1394v1
Definition 1. A configuration model C is a triple (X,D,F ) where X is a set of vari-
ables {x0, . . . , xn−1}, D = D0 × . . . × Dn−1 is the Cartesian product of their finite
domains D0, . . . , Dn−1 and F = {f0, ..., fm−1} is a set of propositional formulae over
atomic propositions xi = v, where v ∈ Di, specifying conditions on the values of the
variables.
Concretely, every domain can be defined as Di = {0, . . . , |Di| − 1}. An assign-
ment of values v0, . . . , vn−1 to variables x0, . . . , xn−1 is denoted as an assignment
ρ = {(x0, v0), . . . , (xn−1, vn−1)}. Domain of assignment dom(ρ) is the set of vari-
ables which are assigned: dom(ρ) = {xi | ∃v ∈ Di.(xi, v) ∈ ρ} and if dom(ρ) = X
we refer to ρ as a total assignment. We say that a total assignment ρ is valid, if it satisfies
all the rules which is denoted as ρ |= F .
A partial assignment ρ′, dom(ρ′) ⊆ X is valid if there is at least one total assign-
ment ρ ⊇ ρ′ that is valid ρ |= F , i.e. if there is at least one way to successfully finish
the existing configuration process.
Example 1. Consider specifying a T-shirt by choosing the color (black, white, red, or
blue), the size (small, medium, or large) and the print (”Men In Black” - MIB or ”Save
The Whales” - STW). There are two rules that we have to observe: if we choose the
MIB print then the color black has to be chosen as well, and if we choose the small size
then the STW print (including a big picture of a whale) cannot be selected as the large
whale does not fit on the small shirt. The configuration problem (X,D,F ) of the T-
shirt example consists of variables X = {x1, x2, x3} representing color, size and print.
Variable domains are D1 = {black ,white, red , blue}, D2 = {small ,medium , large},
and D3 = {MIB , STW }. The two rules translate to F = {f1, f2}, where f1 =
(x3 = MIB) ⇒ (x1 = black ) and f2 = (x3 = STW ) ⇒ (x2 6= small). There
are |D1||D2||D3| = 24 possible assignments. Eleven of these assignments are valid
configurations and they form the solution space shown in Fig. 1. ♦
(black , small ,MIB) (black , large, STW ) (red , large,STW )
(black ,medium,MIB) (white,medium,STW ) (blue,medium,STW )
(black ,medium,STW ) (white, large ,STW ) (blue, large, STW )
(black , large,MIB) (red ,medium,STW )
Fig. 1. Solution space for the T-shirt example
2.1 User Interaction
Configurator assists a user interactively to reach a valid product specification, i.e. to
reach total valid assignment. The key operation in this interaction is that of computing,
for each unassigned variable xi ∈ X \dom(ρ), the valid domainD
i ⊆ Di. The domain
is valid if it contains those and only those values with which ρ can be extended to be-
come a total valid assignment, i.e. Dρi = {v ∈ Di | ∃ρ
′ : ρ′ |= F ∧ρ∪{(xi, v)} ⊆ ρ
The significance of this demand is that it guarantees the user backtrack-free assignment
to variables as long as he selects values from valid domains. This reduces cognitive
effort during the interaction and increases usability.
At each step of the interaction, the configurator reports the valid domains to the
user, based on the current partial assignment ρ resulting from his earlier choices. The
user then picks an unassigned variable xj ∈ X \ dom(ρ) and selects a value from
the calculated valid domain vj ∈ D
j . The partial assignment is then extended to ρ ∪
{(xj , vj)} and a new interaction step is initiated.
3 BDD Based Configuration
In [5,10] the interactive configuration was delivered by dividing the computational ef-
fort into an offline and online phase. First, in the offline phase, the authors compiled a
BDD representing the solution space of all valid configurations Sol = {ρ | ρ |= F}.
Then, the functionality of calculating valid domains (CV D) was delivered online, by
efficient algorithms executing during the interaction with a user. The benefit of this ap-
proach is that the BDD needs to be compiled only once, and can be reused for multiple
user sessions. The user interaction process is illustrated in Fig. 2.
InCo(Sol, ρ)
1: while |Solρ| > 1
2: compute D
ρ = CVD(Sol, ρ)
3: report D
to the user
4: the user chooses (xi, v) for some xi 6∈ dom(ρ), v ∈ D
5: ρ← ρ ∪ {(xi, v)}
6: return ρ
Fig. 2. Interactive configuration algorithm working on a BDD representation of the so-
lutions Sol reaches a valid total configuration as an extension of the argument ρ.
Important requirement for online user-interaction is the guaranteed real-time expe-
rience of user-configurator interaction. Therefore, the algorithms that are executing in
the online phase must be provably efficient in the size of the BDD representation. This
is what we call the real-time guarantee. As the CV D functionality is NP-hard, and the
online algorithms are polynomial in the size of generated BDD, there is no hope of pro-
viding polynomial size guarantees for the worst-case BDD representation. However, it
suffices that the BDD size is small enough for all the configuration instances occurring
in practice [10].
3.1 Binary Decision Diagrams
A reduced ordered Binary Decision Diagram (BDD) is a rooted directed acyclic graph
representing a Boolean function on a set of linearly ordered Boolean variables. It has
one or two terminal nodes labeled 1 or 0 and a set of variable nodes. Each variable node
is associated with a Boolean variable and has two outgoing edges low and high. Given
an assignment of the variables, the value of the Boolean function is determined by a
path starting at the root node and recursively following the high edge, if the associated
variable is true, and the low edge, if the associated variable is false. The function value
is true, if the label of the reached terminal node is 1; otherwise it is false. The graph is
ordered such that all paths respect the ordering of the variables.
A BDD is reduced such that no pair of distinct nodes u and v are associated with the
same variable and low and high successors (Fig. 3a), and no variable node u has iden-
tical low and high successors (Fig. 3b). Due to these reductions, the number of nodes
u v u
x x x
(a) (b)
Fig. 3. (a) nodes associated to the same variable with equal low and high successors
will be converted to a single node. (b) nodes causing redundant tests on a variable are
eliminated. High and low edges are drawn with solid and dashed lines, respectively
in a BDD for many functions encountered in practice is often much smaller than the
number of truth assignments of the function. Another advantage is that the reductions
make BDDs canonical [11]. Large space savings can be obtained by representing a col-
lection of BDDs in a single multi-rooted graph where the sub-graphs of the BDDs are
shared. Due to the canonicity, two BDDs are identical if and only if they have the same
root. Consequently, when using this representation, equivalence checking between two
BDDs can be done in constant time. In addition, BDDs are easy to manipulate. Any
Boolean operation on two BDDs can be carried out in time proportional to the product
of their size. The size of a BDD can depend critically on the variable ordering. To find
an optimal ordering is a co-NP-complete problem in itself [11], but a good heuristic for
choosing an ordering is to locate dependent variables close to each other in the order-
ing. For a comprehensive introduction to BDDs and branching programs in general, we
refer the reader to Bryant’s original paper [11] and the books [12,13].
3.2 Compiling the Configuration Model
Each of the finite domain variables xi with domain Di = {0, . . . , |Di| − 1} is encoded
by ki = ⌈log|Di|⌉ Boolean variables x
0, . . . , x
. Each j ∈ Di, corresponds to a
binary encoding v0 . . . vki−1 denoted as v0 . . . vki−1 = enc(j). Also, every combina-
tion of Boolean values v0 . . . vki−1 represents some integer j ≤ 2
ki − 1, denoted as
j = dec(v0 . . . vki−1). Hence, atomic proposition xi = v is encoded as a Boolean ex-
pression xi0 = v0 ∧ . . . ∧ x
= vki−1. In addition, domain constraints are added
to forbid those assignments to v0 . . . vki−1 which do not translate to a value in Di, i.e.
where dec(v0 . . . vki−1) ≥ |Di|.
Let the solution space Sol over ordered set of variables x0 < . . . < xk−1 be repre-
sented by a Binary Decision Diagram B(V,E,Xb, R, var), where V is the set of nodes
u, E is the set of edges e and Xb = {0, 1, . . . , |Xb| − 1} is an ordered set of variable
indexes, labelling every non-terminal node u with var(u) ≤ |Xb| − 1 and labelling
the terminal nodes T0, T1 with index |Xb|. Set of variable indexes Xb is constructed
by taking the union of Boolean encoding variables
i=0 {x
0, . . . , x
} and ordering
them in a natural layered way, i.e. xi1j1 < x
iff i1 < i2 or i1 = i2 and j1 < j2.
Every directed edge e = (u1, u2) has a starting vertex u1 = π1(e) and ending
vertex u2 = π2(e). R denotes the root node of the BDD.
Example 2. The BDD representing the solution space of the T-shirt example introduced
in Sect. 2 is shown in Fig. 4. In the T-shirt example there are three variables: x1, x2 and
x3, whose domain sizes are four, three and two, respectively. Each variable is repre-
sented by a vector of Boolean variables. In the figure the Boolean vector for the vari-
able xi with domain Di is (x
i , x
i , · · ·x
i ), where li = ⌈lg |Di|⌉. For example, in
the figure, variable x2 which corresponds to the size of the T-shirt is represented by the
Boolean vector (x02, x
2). In the BDD any path from the root node to the terminal node
1, corresponds to one or more valid configurations. For example, the path from the root
node to the terminal node 1, with all the variables taking low values represents the valid
configuration (black , small ,MIB). Another path with x01, x
1, and x
2 taking low values,
and x12 taking high value represents two valid configurations: (black ,medium,MIB)
and (black ,medium, STW ), namely. In this path the variable x03 is a don’t care variable
and hence can take both low and high value, which leads to two valid configurations.
Any path from the root node to the terminal node 0 corresponds to invalid configura-
tions. ♦
4 Calculating Valid Domains
Before showing the algorithms, let us first introduce the appropriate notation. If an
index k ∈ Xb corresponds to the j + 1-st Boolean variable x
j encoding the finite
domain variable xi, we define var1(k) = i and var2(k) = j to be the appropriate
mappings. Now, given the BDD B(V,E,Xb, R, var), Vi denotes the set of all nodes
u ∈ V that are labelled with a BDD variable encoding the finite domain variable xi, i.e.
Vi = {u ∈ V | var1(u) = i}. We think of Vi as defining a layer in the BDD. We define
Ini to be the set of nodes u ∈ Vi reachable by an edge originating from outside the Vi
layer, i.e. Ini = {u ∈ Vi| ∃(u
′, u) ∈ E. var1(u
′) < i}. For the root node R, labelled
with i0 = var1(R) we define Ini0 = Vi0 = {R}.
We assume that in the previous user assignment, a user fixed a value for a finite
domain variable x = v, x ∈ X , extending the old partial assignment ρold to the current
Fig. 4. BDD of the solution space of the T-shirt example. Variable xji denotes bit vj of
the Boolean encoding of finite domain variable xi.
assignment ρ = ρold ∪ {(x, v)}. For every variable xi ∈ X , old valid domains are
denoted as Dρoldi , i = 0, . . . , n− 1. and the old BDD B
ρold is reduced to the restricted
BDD, Bρ(V,E,Xb, var). The CV D functionality is to calculate valid domains D
for remaining unassigned variables xi 6∈ dom(ρ) by extracting values from the newly
restricted BDD Bρ(V,E,Xb, var).
To simplify the following discussion, we will analyze the isolated execution of the
CV D algorithms over a given BDD B(V,E,Xb, var). The task is to calculate valid
domains V Di from the starting domains Di. The user-configurator interaction can be
modelled as a sequence of these executions over restricted BDDs Bρ, where the valid
domains are Dρi and the starting domains are D
The CV D functionality is delivered by executing two algorithms presented in Fig.
5 and Fig. 6. The first algorithm is based on the key idea that if there is an edge e =
(u1, u2) crossing over Vj , i.e. var1(u1) < j < var1(u2) then we can include all the
values from Dj into a valid domain V Dj ← Dj .
We refer to e as a long edge of length var1(u2) − var1(u1). Note that it skips
var(u2)− var(u1) Boolean variables, and therefore compactly represents the part of a
solution space of size 2var(u2)−var(u1).
For the remaining variables xi, whose valid domain was not copied by CV D −
Skipped, we execute CV D(B, xi) from Fig. 6. There, for each value j in a domain D
we check whether it can be part of the domain Di. The key idea is that if j ∈ Di then
there must be u ∈ Vi such that traversing the BDD from u with binary encoding of j
CV D − Skipped(B)
1: for each i = 0 to n− 1
2: L[i]← i+ 1
3: T ← TopologicalSort(B)
4: for each k = 0 to |T | − 1
5: u1 ← T [k], i1 ← var1(u1)
6: for each u2 ∈ Adjacent[u1]
7: L[i1]← max{L[i1], var1(u2)}
8: S ← {}, s← 0
9: for i = 0 to n− 2
10: if i+ 1 < L[s]
11: L[s]← max{L[s], L[i+ 1]}
12: else
13: if s+ 1 < L[s] S ← S ∪ {s}
14: s← i+ 1
15: for each j ∈ S
16: for i = j to L[j]
17: V Di ← Di
Fig. 5. In lines 1-7 the L[i] array is created to record longest edge e = (u1, u2) orig-
inating from the Vi layer, i.e. L[i] = max{var1(u
′) | ∃(u, u′) ∈ E.var1(u) = i}.
The execution time is dominated by TopologicalSort(B) which can be implemented
as depth first search in O(|E|+ |V |) = O(|E|) time. In lines 8-14, the overlapping long
segments have been merged in O(n) steps. Finally, in lines 15-17 the valid domains
have been copied in O(n) steps. Hence, the total running time is O(|E|+ n).
CV D(B, xi)
1: V Di ← {}
2: for each j = 0 to |Di| − 1
3: for each k = 0 to |Ini| − 1
4: u← Ini[k]
′ ← Traverse(u, j)
6: if u
′ 6= T0
7: V Di ← V Di ∪ {j}
8: Return
Fig. 6. Classical CVD algorithm. enc(j) denotes the binary encoding of number j to ki
values v0, . . . , vki−1. If Traverse(u, j) from Fig. 7 ends in a node different then T0,
then j ∈ V Di.
will lead to a node other than T0, because then there is at least one satisfying path to T1
allowing xi = j.
Traverse(u, j)
1: i← var1(u)
2: v0, . . . , vki−1 ← enc(j)
3: s← var2(u)
4: if Marked[u] = j return T0
5: Marked[u]← j
6: while s ≤ ki − 1
7: if var1(u) > i return u
8: if vs = 0 u← low(u)
10: else u← high(u)
12: if Marked[u] = j return T0
13: Marked[u]← j
14: s← var2(u)
Fig. 7. For fixed u ∈ V, i = var1(u), Traverse(u, j) iterates through Vi and returns
the node in which the traversal ends up.
When traversing with Traverse(u, j) we mark the already traversed nodes ut with
j, Marked[ut] ← j and prevent processing them again in the future j-traversals
Traverse(u′, j). Namely, if Traverse(u, j) reached T0 node through ut, then any
other traversal Traverse(u′, j) reaching ut must as well end up in T0. Therefore, for
every value j ∈ Di, every node u ∈ Vi is traversed at most once, leading to worst case
running time complexity of O(|Vi| · |Di|). Hence, the total running time for all variables
is O(
i=0 |Vi| · |Di|).
The total worst-case running time for the two CV D algorithms is thereforeO(
i=0 |Vi|·
|Di|+ |E|+ n) = O(
i=0 |Vi| · |Di|+ n).
References
1. Jensen, R.M.: CLab: A C++ library for fast backtrack-free interactive product configuration.
http://www.itu.dk/people/rmj/clab/ (2007)
2. Raskin, J.: The Humane Interface. Addison Wesley (2000)
3. Amilhastre, J., Fargier, H., Marquis, P.: Consistency restoration and explanations in
dynamic CSPs-application to configuration. Artificial Intelligence 1-2 (2002) 199–234
ftp://fpt.irit.fr/pub/IRIT/RPDMP/Configuration/.
4. Madsen, J.N.: Methods for interactive constraint satisfaction. Master’s thesis, Department
of Computer Science, University of Copenhagen (2003)
5. Hadzic, T., Subbarayan, S., Jensen, R.M., Andersen, H.R., Møller, J., Hulgaard, H.: Fast
backtrack-free product configuration using a precompiled solution space representation. In:
PETO Conference, DTU-tryk (2004) 131–138
6. Møller, J., Andersen, H.R., Hulgaard, H.: Product configuration over the internet. In: Pro-
ceedings of the 6th INFORMS Conference on Information Systems and Technology. (2002)
7. Configit Software A/S. http://www.configit-software.com (online)
8. Tsang, E.: Foundations of Constraint Satisfaction. Academic Press (1993)
9. Dechter, R.: Constraint Processing. Morgan Kaufmann (2003)
10. Subbarayan, S., Jensen, R.M., Hadzic, T., Andersen, H.R., Hulgaard, H., Møller, J.: Com-
paring two implementations of a complete and backtrack-free interactive configurator. In:
CP’04 CSPIA Workshop. (2004) 97–111
11. Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transactions
on Computers 8 (1986) 677–691
12. Meinel, C., Theobald, T.: Algorithms and Data Structures in VLSI Design. Springer (1998)
13. Wegener, I.: Branching Programs and Binary Decision Diagrams. Society for Industrial and
Applied Mathematics (SIAM) (2000)
	Calculating Valid Domains for BDD-Based Interactive Configuration
	Tarik Hadzic, Rune Moller Jensen, Henrik Reif Andersen
