Semiring Labelled Decision Diagrams, Revisited: Canonicity and Spatial Efficiency Issues

1 Introduction

In configuration problems of combinatorial objects (like cars), there are two key tasks for which short, guaranteed response times are expected: conditioning (propagating the end-user's choices: version, engine, various options ...) and optimization (maintaining the minimum cost of a feasible car satisfying the user's requirements). When the set of feasible objects and the corresponding cost functions are represented as valued CSPs (VCSPs for short see [Schiex et al., 1995]), the optimization task is NP-hard in the general case, so short response times cannot be ensured.

Valued decision diagrams (VDDs) from the families ADD [Bahar et al., 1993], EVBDD [Lai and Sastry, 1992; Lai et al., 1996; Amilhastre et al., 2002] and their generalization SLDD [Wilson, 2005], and AADD [Tafertshofer and Pedram, 1997; Sanner and McAllester, 2005] do not have such a drawback and appear as interesting representation languages for compiling mappings associating valuations with assignments of discrete variables (including utility functions and probability distributions). Indeed, those languages offer tractable conditioning and tractable optimization (under some conditions in the SLDD case). However, the efficiency of these operations is directly related to the size of the compiled formulae. Following [Darwiche and Marquis, 2002], the choice of the target representation language for the compiled forms must be guided by its succinctness. From the practical side, normalization (and all the more canonicity) are also important: subformulae in normalized form can be more efficiently recognized and the canonicity of the compiled formulae facilitates the search for compiled forms of optimal size (see the discussion about it in [Darwiche, 2011]). Indeed, the ability to ensure a unique form for subformulae prevents them from being represented twice or more.

∗This work is partially supported by the project BR4CP ANR11-BS02-008 of the French National Agency for Research.

In this paper, the SLDD family [Wilson, 2005] is revisited, focusing on the canonicity and the spatial efficiency issues. We extend the SLDD setting by relaxing some algebraic requirements on the valuation structure. This extension allows us to capture the AADD language as an element of e-SLDD, the revisited SLDD family. We point out a normalization procedure which extends the AADD 's one to some representation languages of e-SLDD. We also provide a number of succinctness results relating some elements of e-SLDD with ADD and AADD. We finally report some experimental results where we compiled some instances of an industrial configuration problem into each of those languages, thus comparing their spatial efficiency from the practical side.

The rest of the paper is organized as follows. Section 2 gives some formal preliminaries on valued decision diagrams. Section 3 presents the e-SLDD family and describes our normalization procedure. In Section 4, succinctness results concerning ADD, some elements of the e-SLDD family, and AADD are pointed out. Section 5 gives and discusses our empirical results about the spatial efficiency of those languages. Finally, Section 6 concludes the paper. 1

2 Valued Decision Diagrams

Given a finite set X = {x1, . . . , xn} of variables where each variable x ∈ X ranges over a finite domain Dx, we are interested in representing mappings associating an element from a valuation set E with assignments ⃗x = {(xi, di) | di ∈

1 A full-proof version of the paper is available at ftp://ftp.irit.fr/ IRIT/ADRIA/ijcai13FMS.pdf

Dxi , i = 1, . . . , n} ( ⃗X will denote the set of all assignments over X). E is the carrier of a valuation structure E, which can be more or less sophisticated from an algebraic point of view. A representation language given X w.r.t. a valuation structure E is mainly a set of data structures. The targeted mapping is called the semantics of the data structure and the data structure is a representation of the mapping:

Definition 1 (representation language) (inspired from [Gogic et al., 1995]) Given a valuation structure E, a representation language L over X w.r.t. E is a 4-tuple 〈CL,VarL, IL, sL〉 where CL is a set of data structures α (also referred to as CL formulae), VarL : CL → 2X is a scope function associating with each CL formula the subset of X it depends on, IL is an interpretation function associating with each CL formula α a mapping IL(α) from the set of all assignments of VarL(α) to E, and sL is a size function from CL to N providing the size of any CL formula.

Different formulae can share the same semantics:

Definition 2 (equivalent formulae) Let L1 (resp. L2) be a representation language over X w.r.t. E1 (resp. E2) where E1 = E2. α ∈ L1 is equivalent to β ∈ L2 iff VarL1 (α) = VarL2 (β) and IL1 (α) = IL2 (β).

In this paper, we are specifically interested in data structures of the form of valued decision diagrams:

Definition 3 (valued decision diagram) A valued decision diagram (VDD) over X w.r.t. E is a finite DAG α with a single root, s.t. every internal node N is labelled with a variable x ∈ X and if Dx = {d1, . . . , dk}, then N has k outgoing arcs a1, . . . , ak, so that the arc ai of α is valued by v(ai) = di. We note out(N) (resp. in(N) ) the arcs outgoing from (resp. incoming to N). Nodes and arcs can also be labelled by elements of E: if N (resp. ai) is node (resp. an arc) of α, then φ(N) (resp. φ(ai)) denotes the label of N (resp. ai). Finally, each VDD α is a read-once formula, i.e., for each path from the root of α to a sink, every variable x ∈ X occurs at most once as a node label.

When ordered VDDs are considered, a total ordering over X is chosen and for each path from the root of α to a sink, the associated sequence of internal node labels is required to be compatible w.r.t. this variable ordering.

The key problems we focus on are the conditioning problem (given a CL formula α over X w.r.t. E and an assignment ⃗y ∈ ⃗Y where Y ⊆ X, compute a CL formula representing the restriction of IL(α) by ⃗y) and the optimization problem (given a CL formula α over X w.r.t. E, find an assignment ⃗ x∗ ∈ ⃗X such that IL(α)( ⃗ x∗ ) is not dominated w.r.t. some relation ⪰ over E - typically, ⪰ is a total order). Conditioning is an easy operation on a VDD α. Mainly, for each (y, di) ∈ ⃗y, just by-pass in α every node N labeled by y by linking directly each of its parents to the child Ni of N such that v((N,Ni)) = di (N and all its outgoing arcs are thus removed). However, optimization is often more demanding, depending on the family of VDDs under consideration.

ADD, SLDD, and AADD are representation languages composed of valued decision diagrams. The scope functions VarADD, VarSLDD, and VarAADD are the same ones and they return the set of variables Var(α) from X where each x ∈ Var(α) labels at least one node in α. The size functions sADD, sSLDD, and sAADD are closely related: the size of a (labelled) decision graph α is the size of the graph (number of nodes plus number of arcs) plus the sizes of the labels in it. The main difference between ADD, SLDD, and AADD lies in the way the decision diagrams are labelled and interpreted.

For ADD, no specific assumption has to be made on the valuation structure E, even if E = R is often considered:

Definition 4 (ADD) ADD is the 4-tuple 〈CADD, VarADD, IADD, sADD〉 where CADD is the set of ordered VDDs α over X such that sinks S are labelled by elements of E, and the arcs are not labelled; IADD is defined inductively by: for every assignment ⃗x over X,

• if α is a sink node S, labelled by φ(S) = e, then IADD(α)(⃗x) = e,
• else the root N of α is labelled by x ∈ X; let d ∈ Dx such that (x, d) ∈ ⃗x, a = (N,M) the arc such that v(a) = d, and β the ADD formula rooted at node M in α; we have IADD(α)(⃗x) = IADD(β)(⃗x).

Optimization is easy on an ADD formula: every path from the root of α to a sink labelled by a non-dominated valuation among those labeling the sinks of α can be read as a (usually partial) variable assignment which can be extended to a (full) optimal assignment.

In the SLDD framework [Wilson, 2005], the valuation structure E must take the form of a commutative semiring 〈E, ⊕, ⊗, 0s, 1s〉: ⊕ and ⊗ are associative and commutative mappings from E × E to E, with identity elements (respectively) 0s and 1s, ⊗ left and right distributes over ⊕, and 0s is an annihilator for ⊗ (∀a ∈ E, a ⊗ 0s = 0s ⊗ a = 0s).

Definition 5 (SLDD) Let E = 〈E, ⊕, ⊗, 0s, 1s〉 be a commutative semiring. SLDD is the 4-tuple 〈CSLDD, VarSLDD, ISLDD, sSLDD〉 where CSLDD is the set of VDDs α over X with a unique sink S, satisfying φ(S) = 1s, and such that the arcs are labelled by elements of E, and ISLDD is defined inductively by: for every assignment ⃗x over X,

• if α is the sink node S, then ISLDD(α)(⃗x) = 1s,
• else the root N of α is labelled by x ∈ X; let d ∈ Dx such that (x, d) ∈ ⃗x, a = (N,M) the arc such that v(a) = d, and β the SLDD formula rooted at node M in α; we have ISLDD(α)(⃗x) = φ(a) ⊗ ISLDD(β)(⃗x).

SLDD languages are not specifically suited to optimization w.r.t. any relation ⪰. Specifically, [Wilson, 2005] considers the following addition-is-max-or-min assumption about ⊕:

Under this assumption, ⊕ is idempotent and the relation ⊴ defined by a ⊴ b iff a⊕b = a is total. [Wilson, 2005] shows that, when ⪰ coincides with ⊴, computing the valuation of ISLDD(α) maximal w.r.t. ⪰ amounts to performing ⊕- variable elimination; this can be achieved in polynomial time under the linear-time computability assumption for ⊗ and ⊕.

Sanner and Mc Allester's AADD framework [2005] focuses on the valuation set E = R+ but enables decision graphs into which the arcs are labelled with pairs of values from R+ and considers two operators, namely + and ×:

Definition 6 (AADD) AADD is the 4-tuple 〈CAADD, VarAADD, IAADD sAADD〉 where CAADD is the set of ordered VDDs α over X with a unique sink S, satisfying φ(S) = 1, and such that the arcs are labelled by pairs 〈q, f〉 in R+ × R+; IAADD is defined inductively by: for every assignment ⃗x over X,

• if α is the sink node S, then IAADD(α)(⃗x) = 1,
• else the root N of α is labelled by x ∈ X; let d ∈ Dx such that (x, d) ∈ ⃗x, a = (N,M) the arc such that v(a) = d and φ(a) = 〈q, f〉, and β the AADD formula rooted at node M in α; we have

For the normalization purpose, each α is equipped with a pair 〈q0, f0〉 from R+ × R+ (the "offset", labeling the root of α); the interpretation function of the resulting "augmented" AADD is given by, for every assignment ⃗x over X, I 〈q0,f0〉 AADD (α)(⃗x) = q0 + (f0 × IAADD(α)(⃗x)).

Conditioning and optimization are also tractable on AADD formulae (see [Sanner and McAllester, 2005]).

3 Revisiting the SLDD Framework

In the following, we extend the SLDD framework in two directions: we relax the algebraic requirements imposed on the valuation structure and we point out a normalization procedure which extends the AADD 's one to some representation languages of e-SLDD, the extended SLDD family.

A first useful observation is that, in the SLDD framework, ⊕ is not used for defining the SLDD language. Actually, different ⊕ may be considered over the same formula (e.g., when SLDD is used to compile a Bayesian net, ⊕ = + can be used for marginalization purposes and ⊕ = max can be considered when a most probable explanation is looked for). This explains why the requirements imposed on ⊕ in the SLDD setting can be relaxed. Let us recall that a monoid is a triple 〈E,⊗, 1s〉 where E is a set endowed with an associative binary operator ⊗ with identity element 1s:

Definition 7 (e-SLDD) For any monoid E = 〈E, ⊗, 1s〉, e-SLDD is the 4-tuple 〈Ce-SLDD, Vare-SLDD, Ie-SLDD⊗ , se-SLDD〉, defined as the SLDD one, except that, for the normalization purpose, each e-SLDD formula α is associated with a value q0 ∈ E (the "offset" of the data structure, labeling its root); the interpretation function I q0 e-SLDD of the extended SLDD setting is given by, for every assignment ⃗x over X,

Several choices for ⊗ remain usually possible when E is fixed; we sometimes make the notation of the language more precise (but not too heavy) and write e-SLDD⊗ instead of e-SLDD.

Obviously, the e-SLDD framework captures the SLDD one: when 〈E, ⊕, ⊗, 0s, 1s〉 is a commutative semiring, then 〈E, ⊗, 1s〉 is a monoid, and every SLDD formula can be interpreted as an e-SLDD one (choose q0 = 1s). Interestingly, the e-SLDD framework also captures the AADD language:

Proposition 1 Let E = R+ × R+, 1s = 〈0, 1〉 and ⊗ = ⋆ be defined by ∀b, b′ , c, c′ ∈ E, 〈b, c〉 ⋆ 〈b′ , c′ 〉 = 〈b + c × b′ , c × c′ 〉. E = 〈E, ⊗, 1s〉 is a monoid.

The correspondence between AADD and e-SLDD⋆ is made precise by the following proposition:

Proposition 2 Let α be an AADD formula, also viewed as an e-SLDD⋆ formula. We have: ∀⃗x ∈ ⃗X, if IAADD(α)(⃗x) = a and Ie-SLDD⋆ (α)(⃗x) = 〈b, c〉, then a = b + c.

Observe that ⋆ is not commutative: the relaxation of the commutativity assumption is necessary to capture the AADD framework within the e-SLDD family.

Let us now switch to the normalization/canonicity issues for e-SLDD. When compiling a formula, normalization (and all the more canonicity) are important for computational reasons: in practice, subformulae in reduced, normalized form which have been already encountered and cached can be more efficiently recognized. Besides, when the canonicity property is ensured, the recognition issue boils down to a simple equality test. Thus, canonicity is more demanding and is achieved for ordered VDDs, only: reduced ADD formulae and normalized and reduced AADD formulae (which are ordered VDDs) offer the canonicity property. Contrastingly, though some simplification rules have been considered in [Wilson, 2005], no normalization procedure and canonicity conditions for SLDD have been pointed out so far.

The idea at work for normalizing AADD formulae is to propagate from the sink to the root of the diagram the minimum valuations of the outgoing arcs. In our more general framework, minimality is characterized by an idempotent, commutative and associative operator ⊕, which induces the binary relation ⊵ over E given by:

The fact that is ⊕ is associative (resp. commutative, idempotent) implies that the induced relation ⊵ is transitive (resp. antisymmetric, reflexive), hence an order over E.

Definition 8 (⊕-normalisation, ⊕-reduction) An e-SLDD formula α is ⊕-normalized iff for any node N of α, ⊕a∈out(N)φ(a) = 1s (by convention, we define ⊕a∈∅φ(a) = 1s). An e-SLDD formula α is ⊕-reduced iff it is ⊕- normalized, and reduced, i.e., it does not contain any (distinct) isomorphic nodes 2 and any redundant nodes. 3

To allow to propagate valuations in VCSPs, where ⊵ is a total order, ⊗ is commutative and ⊗ is monotonic w.r.t. ⊵ (i.e., ⊗ is distributive over ⊕), [Cooper and Schiex, 2004] assume a "fairness" property of ⊗ w.r.t. ⊕: for any valuations a, b ∈ E such that a⊕b = b, there exists a unique valuation which is the maximal element w.r.t. ⊵ among the c ∈ E satisfying b ⊗ c = c ⊗ b = a.

Here, we relax these conditions so as to be able to encompass the case of the (possibly partial) relation ⊵ induced by ⊕. Let us state that ⊗ is left-distributive over ⊕ iff ∀a, b, c ∈ E, c ⊗ (a⊕b) = (c ⊗ a)⊕(c ⊗ b), and ⊗ is left-fair w.r.t. ⊕ iff ∀a, b ∈ E, if a⊕b = b, then there exists a unique valuation of E, noted a ⊗-1 b, which is the maximal element w.r.t. ⊵ among the c ∈ E satisfying b ⊗ c = a.

2N and M are isomorphic when they are labelled by the same variable and there exists a bijection f from out(N) to out(M) such that ∀a ∈ out(N), a and f(a) have the same end node and φ(a) = φ(f (a)).

3N is redundant when all outgoing arcs a are labelled by the same value φ(a) and reach the same end node.

Definition 9 (extended SLDD condition) A valuation structure E = 〈E, ⊕, ⊗, 1s〉 satisfies the extended SLDD condition iff 〈E, ⊗, 1s〉 is a monoid, ⊕ is a mapping from E × E to E, which is associative, commutative, and idempotent, ⊗ is leftdistributive over ⊕ and left-fair w.r.t. ⊕.

The extended SLDD condition is close to the commutative semiring assumption for SLDD. However, it requires neither the commutativity of ⊗, nor an annihilator for ⊗, and leftdistributivity of ⊗ over ⊕ is less demanding than (full) distributivity; on the other hand, the left-fairness condition of ⊗ w.r.t. ⊕ is imposed. The idempotence of ⊕ is also less demanding than the "addition-is-max-or-min" condition.

The valuation considered in the AADD framework satisfies the extended SLDD condition:

Proposition 3 The valuation structure E = 〈R+ ×R+, ⊕, ⋆, 〈0, 1〉〉 where ⊕ = min⋆ is defined by ∀b, b′ , c, c′ ∈ E: 〈b, b′ 〉 min⋆ 〈c, c′ 〉 = 〈min(b, c), max (b + b′ , c + c′ ) - min(b, c)〉, satisfies the extended SLDD condition.

In the AADD case, E = R+ × R+ is not totally ordered by ⊵ (for instance, none of 〈0, 2〉⊵〈1, 2〉 and 〈1, 2〉⊵〈0, 2〉 hold since 〈0, 2〉min⋆〈1, 2〉 = 〈1, 2〉min⋆〈0, 2〉 = 〈0, 3〉). When 〈a, a′ 〉 ⊵ 〈b, b′ 〉 holds, we have:

• 〈a, a′ 〉 ⋆-1 〈b, b′ 〉 = 〈1, 0〉 if b′ = 0,
• 〈a, a′ 〉 ⋆-1 〈b, b′ 〉 = 〈 a-b b′ , a′ b′ 〉 if b′ > 0.

e-SLDD⋆ denotes the corresponding e-SLDD language.

Weighted finite automata and edge-valued binary decision diagrams are captured by using E = 〈R+,min,+, 0〉. The following pairs, consisting of a valuation structure - a representation language, can actually be considered:

• E = 〈R+,min,+, 0〉 - e-SLDD+.
• E = 〈R+, max , ×, 1〉 - e-SLDD×.
• E = 〈R+ ∪ {+∞}, max , min, +∞〉 - e-SLDDmin .
• E = 〈R+, min, max , 0〉 - e-SLDDmax .

Proposition 4 The valuation structures E = 〈R+, min, +, 0〉, E = 〈R+, max, ×, 1〉, E = 〈R+ ∪ {+∞}, max, min, +∞〉 and E = 〈R+, min, max , 0〉 satisfy the extended SLDD condition.

We are now ready to extend the AADD normalization procedure to the e-SLDD language, under the extended SLDD condition. Algorithm 1 is the normalization procedure. This procedure proceeds backwards (i.e., from the sink to the root). Figure 1 gives an e-SLDD⋆ formula and the corresponding min⋆-reduced formula.

Proposition 5 Assume that E = 〈E, ⊕, ⊗, 1s〉 satisfies the extended SLDD condition. If ⊕ satisfies the addition-ismax-or-min property then, for any e-SLDD formula α, a ⊕- reduced e-SLDD formula equivalent to α can be computed in polynomial time provided that ⊗, ⊗-1 and ⊕ can be computed in linear time.

Algorithm 1: normalize(α)

input : an e-SLDD⊗ formula α, with offset q0 output: an e-SLDD⊗ formula which is ⊕-normalized

• and equivalent to α 1 for each node N of α in inverse topological ordering do 2 qmin := ⊕a∈out(N)φ(a) 3 for each a ∈ out(N) do 4 if φ(a) == qmin then φ(a) := 1s elseφ(a) := φ(a) ⊗-1 qmin 5 for each a ∈ in(N) do φ(a) := φ(a) ⊗ qmin 6 q0 := q0 ⊗ qmin 7 return α

〈1, 2〉 3 5 〈1, 1〉 〈0, 1 9 〉 〈 27 , 57 〉 〈0, 1 7 〉

Figure 1: An e-SLDD⋆ formula (left) and the corresponding min⋆-reduced e-SLDD⋆ formula (right). x, y and z are Boolean variables. A (resp. plain) edge corresponds to the assignment of the variable labeling its source to 0 (resp. 1).

Clearly, the linear-time computability assumptions are satisfied by the operators ⊗, ⊗-1 , and ⊕ associated with e-SLDD+, e-SLDD×, e-SLDDmin, e-SLDDmax . Thus, the formulae from all these languages can be ⊕-reduced in polynomial time.

Interestingly, addition-is-max-or-min is not a necessary condition for ensuring a normalized form; left-cancellativity of ⊗ (∀a, b, c ∈ E, if c⊗a = c⊗b and c is not an annihilator for ⊗, then a = b) is also enough:

Proposition 6 Assume that E = 〈E, ⊕, ⊗, 1s〉 satisfies the extended SLDD condition. If ⊗ is left-cancellative, then for any e-SLDD formula α, a ⊕-reduced e-SLDD formula equivalent to α it can be computed in polynomial time provided that ⊗, ⊗-1 and ⊕ can be computed in linear time.

Furthermore, when ⊗ is left-cancellative, the canonicity property is ensured for ordered e-SLDD formulae (even if ⊵ is not total):

Proposition 7 Assume that E = 〈E, ⊕, ⊗, 1s〉 satisfies the extended SLDD condition. If ⊗ is left-cancellative, then two ordered e-SLDD formulae are equivalent iff they have the same ⊕-reduced form.

Especially, since +, × and ⋆ are left-cancellative, the ordered e-SLDD+ (resp. e-SLDD×, e-SLDD⋆) formulae offer the canonicity property.

Let us finally switch to conditioning and optimization. First, conditioning does not preserve the ⊕-reduction of a formula in the general case, but this is computationally harmless since the ⊕-reduction of a conditioned formula can be done in polynomial time. As to optimization, when ⊵ is total, any ⊕- reduced e-SLDD formula α contains a path the arcs of which are labelled by 1s. The (usually partial) variable assignment along this path can be extended to a full minimal solution ⃗ x∗ w.r.t. ⊵, and the offset of α is equal to Ie-SLDD(α)( ⃗ x∗ ). However, in the general case, the ordering ⪰ is not equal to ⊵, so the normalization procedure does not help for determining a minimal solution ⃗ x∗ w.r.t. ⪰ (or equivalently, a maximal solution w.r.t. the inverse ordering ⪯). Nevertheless, a simple left-monotonicity condition over the valuation structure is enough for ensuring that a minimal solution ⃗ x∗ w.r.t. ⪰ can be computed in time polynomial in the size of the e-SLDD formula, using dynamic programming. The result of [Wilson, 2005] indeed can be extended as follows:

Proposition 8 For any monoid E = 〈E, ⊗, 1s〉 such that E is totally pre-ordered by ⪰, if ⊗ is left-monotonic w.r.t. ⪰ (for any a, b, c ∈ E, if a ⪰ b then c ⊗ a ⪰ c ⊗ b), then for any e-SLDD formula α, a solution ⃗ x∗ minimal w.r.t. ⪰ can be computed in time polynomial in the size of α.

4 Succinctness of VDDs: Theoretical Results

Let L1 (resp. L2) be a representation language over X w.r.t. E1 (resp. E2). The notion of succinctness and of translations usually considered over propositional languages (see [Darwiche and Marquis, 2002]) can be extended as follows:

Definition 10 (succinctness) L1 is at least as succinct as L2, denoted L1 ≤s L2, iff there exists a polynomial p such that for every α ∈ CL2 , there exists β ∈ CL1 which is equivalent to α and such that sL1 (β) ≤ p(sL2 (α)).

Definition 11 (linear / polynomial translation) L2 is linearly (resp. polynomially) translatable into L1, denoted L1 ≤l L2 (resp. L1 ≤p L2), iff there exists a linear-time (resp. polynomial-time) algorithm f from CL2 to CL1 such that for every α ∈ CL2 , α is equivalent to f(α).

<s (resp. <p, <l) denotes the asymmetric part of ≤s (resp. ≤p, ≤l), and ∼s (resp. ∼p, ∼l) denotes the symmetric part of ≤s (resp. ≤p, ≤l). By construction, ∼s, ∼p, ∼l are equivalence relations.

We have obtained the following result showing that every ADD is linearly translatable into any e-SLDD (sharing the same valuation set E):

Proposition 9 e-SLDD ≤l ADD.

As to the valuation set E = R+, we get:

Proposition 10

• ADD ∼p e-SLDDmax .
• e-SLDD× ̸≤s e-SLDD+ and e-SLDD+ ̸≤s e-SLDD×.
• AADD <s e-SLDD+ <s ADD.
• AADD <s e-SLDD× <s ADD.

Similarly, for E = R+ ∪{+∞}, ADD ∼p e-SLDDmin holds.

5 Succinctness of VDDs: Empirical Results

While succinctness is a way to compare representation languages w.r.t. the concept of spatial efficiency, it does not capture all aspects of this concept, for two reasons (at least). On the one hand, succinctness focuses on the worst case, only. On the other hand, it is of qualitative (ordinal) nature: succinctness indicates when an exponential separation can be achieved between two languages but does not enable to draw any quantitative conclusion on the sizes of the compiled forms. This is why it is also important to complete succinctness results with some size measurements.

To this aim, we made some experiments. We designed a bottom-up ordered e-SLDD compiler. This compiler takes as input VCSP instances in the XML format described in [Roussel and Lecoutre, 2009] or Bayesian networks conforming to the XML format given in [Cozman, 2002]. When VCSP instances are considered, the compiler generates a data structure equivalent to each valued constraint of the instance, under the form of a reduced e-SLDD+ formula, and incrementally combines them w.r.t. + using a simplified version of the apply(+) procedure described in [Sanner and McAllester, 2005]. Similarly, when Bayesian network instances are considered, the conditional probability tables are first compiled into reduced e-SLDD× formulae, which are then combined using ×. At each combination step, the current e-SLDD formula is reduced. We developed a toolbox which also contains procedures for transforming any e-SLDD+ (resp. e-SLDD×) formula into an equivalent ADD formula, and any ADD formula into an equivalent e-SLDD+ (resp. e-SLDD×, AADD) formula; the transformation procedure from e-SLDD+ (resp. e-SLDD×) formulae to ADD formulae roughly consists in pushing the labels from the root to the last arcs of the diagram. The transformation procedures from ADD formulae to e-SLDD+, e-SLDD× and AADD formulae are basically normalization procedures.

We considered two families of benchmarks. The VCSP instances we used concern car configurations problems; 4 these instances contain hard constraints and soft constraints, with valuations representing prices, to be aggregated additively. They have the following characteristic features:

• Small: #variables=139; max. domain size=16; #constraints=176 (including 29 soft constraints)
• Medium: #variables=148; max. domain size=20; #constraints=268 (including 94 soft constraints)
• Big: #variables=268; max. domain size=324; #constraints=2157 (including 1825 soft constraints)

We also compiled only the soft constraints of the benchmarks, leading to three other instances, referred to as {Small, Medium, Big} Price only. As to Bayesian networks, which are of multiplicative nature (joint probabilities are products of conditional probabilities), we used some standard benchmarks [Cozman, 2002].

4 These instances have been built in collaboration with the french car manufacturer Renault; they are described in more depth in [Astesana et al., 2013].

Each configuration (resp. Bayesian net) instance has been compiled into an e-SLDD+ formula (resp. an e-SLDD× formula), and then transformed into an ADD formula, an e-SLDD× formula (resp. an e-SLDD+ formula), and an AADD formula - the time needed for the compilation and the sizes on the compiled formulae are reported in Table 1 (resp. Table 2). In order to determine a variable ordering, we used the Maximum Cardinality Search heuristic [Tarjan and Yannakakis, 1984] in reverse order, as proposed in [Amilhastre, 1999] for the compilation of (classical) CSPs. This heuristic is easy to compute and efficient; experiments reported in [Amilhastre, 1999] show that it typically outperforms several standard CSP variable ordering heuristics.

We ran all our experiments on a computer running at 800MHz with 256Mb of memory. "m-o" means that the available memory has been exhausted, and that the program aborted for this reason.

Our experiments confirm some of the theory-oriented succinctness results, especially the fact that the succinctness of e-SLDD+ and of e-SLDD× are incomparable but each of them is strictly more succinct than ADD. Unsurprisingly, when the values of the soft constraints are to be aggregated additively as this is the case for configuration instances (resp. multiplicatively, as this is the case for Bayesian nets), e-SLDD+ (resp. e-SLDD×) performs better than e-SLDD× (resp. e-SLDD+). AADD does not prove to be better than e-SLDD+ in the additive case, or better than e-SLDD× in the multiplicative case. 5 Thus, targeting the AADD language does not lead to much better compiled formulae from the spatial efficiency point of view, when the mapping to be represented is additive or multiplicative in essence, but not both.

5 On the Bayesian net instances, the resulting ADD and AADD formulae are larger than the ones obtained by [Sanner and McAllester, 2005]. This is due to the way numeric labels are merged (remember that reals are approximated by finite-precision floating-point num-

6 Conclusion

In this paper, we have extended the SLDD family to the e-SLDD family, thanks to a relaxation of some requirements on the valuation structure, which is harmless for the conditioning and optimization purposes. The e-SLDD family is general enough to capture AADD as a specific element. We have pointed out a normalization procedure and a canonicity condition for formulae from some e-SLDD languages, including e-SLDD+ and e-SLDD×. We have also compared the spatial efficiency of some elements of the e-SLDD family, i.e., e-SLDD+ and e-SLDD×, with ADD and AADD from both the theoretical side and the practical side. Though e-SLDD+ (resp. e-SLDD×) is less succinct than AADD from a theoretical point of view, it proves space-efficient enough for enabling the compilation of cost-based configuration problems (resp. Bayesian networks).

Interestingly, one of the conditions pointed out in the e-SLDD setting for tractable normalization (and reduction) does not impose the valuation set E to be totally ordered. Clearly, this paves the way for the compilation of multicriteria objective functions as e-SLDD representations. Investigating this issue is a major perspective for future works. Another important issue for further research is to draw the full knowledge compilation map for VDD languages, which will require to identify the tractable queries and transformations of interest, depending on the algebraic properties of the valuation structure.

bers on a computer). Indeed, in our implementation, e1 and e2 are considered identical whenever e1 -e2 < 10-9 .e1 (where e1 ≥ e2). Since e1, e2 ≤ 1 (they represent probabilities) the standard merging condition e1 - e2 < 10-9 considered in [Sanner and McAllester, 2005] is subsumed by ours. This explains the size discrepancy.