Large-Scale
Knowledge Processing # 11
Using Binary Decision Diagrams(Part 2)

Faculty of Information Scienceand Technology, Hokkaido Univ.
Takashi Horiyama
1Application of BDDs:
Design and verification of logic circuits◼

Verification : Equivalence of combinatorial circuits◼

◼

Description of the specification (What are outputted fromthe inputs) and designed circuit (In many case, it isoptimized by a design compiler)
Reference circuit and designed circuit
Combinatorial
circuit xSpecificationyz◼

◼

Exhaustively check whether the outputs of the above two (“spec.
and circuit” etc.) are the same for all inputs (If we use truthtables, we need to check all 2n cases ...)
Represent both Boolean functions of the spec. and the designed
circuit by BDDs◼

Same Boolean functions have the same root node (Uniqueness)2

Application of BDDs:
Design and verification of logic circuits
◼

◼

◼
◼

Sequential circuits (circuits that have states, where thestates changes according to the inputs)

Check whether all sequences of the outputs are the samefor all sequences of the inputs (This check is much moredifficult than that for combinatorial circuits)
States are stored in registers (memory elements)
Exhaustively check state transitions on all inputs

xyregister3

Application of BDDs:
Combinatorial problems and optimization
◼
◼
◼

◼

Represent a combinatorial problem by Boolean variables
More precisely, represent constraints (conditions to besatisfied) of a combinatorial problem by Boolean functions
Construct a BDD representing the AND of the Booleanfunctions representing the constraints◼ We have all feasible solutions !
If we have BDDs, it is easy to evaluate
the linear sum of the costs◼ We can easily obtain
the optimal solutions from BDDs !

4

Using BDDs (1)◼

◼

Determine whether a given combination isa feasible solution or not◼ Traverse a BDD from the root node
◼ Ex.) { x1, x3 } ? … Yes since (x1, x2, x3) = (1, 0, 1) gives 1{ x2 } ?
… No since (x1, x2, x3) = (0, 1, 0) gives 0

Enumerate all solutions from a BDD◼ Depth first search◼ When we come to the 1-node,
we have a feasible solution◼ Ex.) {x2, x3}, {x1, x3},
{x1, x2}, {x1, x2, x3}
5

Using BDDs (2)◼

Evaluation of the linear sum of the cost◼
◼

At each node, the costs for its 0-edge and 1-edge arecompared, and the better edge is adopted
The cost of the root node is the optimal valueEx.) minimize – 4 x1 – 5 x2 + 2 x3
-9-30-edge: x
1-edge:cost 2 - 50-edge: cost -31-edge: cost -5 - 4

maximize 3 x1 - 5 x2 + 2 x3
5-3-520-edge: cost 2
1-edge: cost -520-edge: x (no feasible solution)
1-edge: feasible solution with cost 226

Short break◼

Take a deep breath, and relax yourself

7Combinatorial optimization:
Knapsack problemPrice

60 yen30 yen40 yen50 yen40 yen30 yenUtility

36

27

1250

28

24

◼

We can buy snacks within 100 yen(i.e., the budget is 100 yen)◼
◼

◼

We can adopt (i.e., take) at most 1 piece for each item
We cannot divide an item

We’d like to maximize the sum of the utilities

The images of the snacks are from the web sites of Meiji Co. Ltd., and Morinaga & Co., Ltd.

https://www.meiji.co.jp https://www.morinaga.co.jp8Knapsack problem : Variable xi
Item

Item 1

Item2

Item3

Item4

Item5

Item6

Price (yen) 60 yen

30 yen2740 yen
1250 yen
5040 yen2830 yen
24

Utility◼

◼

xi =36

1 … We take itemi

0 … Do not take itemi

We can buy snacks within 100 yen(i.e., the budget is 100 yen)◼

60 x1 + 30 x2 + 40 x3 + 50 x4 + 40 x5 + 30 x6 ≦ 1009Knapsack problem : Formulation
Item

Item 1

Item2

Item3

Item4

Item5

Item6

Price (yen)p1u1p2
u2p3
u3p4u4p5u5p6u6

Utility◼

◼

Objective function
6◼ Maximize : ∑ i = 1 ui xi

Constraints
6◼

∑ i = 1 pi xi ≦ 100◼

xi ∊ { 0, 1 }0-1 integer
programming problem( i = 1, 2, ..., 6)
10Combinatorial optimization:
Knapsack problem◼

Represent constraint Σi pi xi ≦ c by a BDD(How ? → see the next slide)◼

Maximize the objective function Σi ui xi(see p. 6)

11

Represent the constraint of theknapsack problem by a BDD
Budget is
100 yentakeitem5

do nottake item5

Item

Item 5

Budget
100 yen Price (yen) 60 yen
Utility

36

Item4

Item3

Item2

Item130 yen 30 yen 60 yen 30 yen
27
12502812Represent the constraint of theknapsack problem by a BDD
Budget becomes 40 yen
since we take Item5 (60 yen)

Item

Item 5

Budget
100 yen Price (yen) 60 yen
Utility

36

Item4

Item3

Item2

Item1

30 yen 30 yen 60 yen 30 yen
27
1250
2813Represent the constraint of theknapsack problem by a BDD

Item

Item 5

Budget
100 yen Price (yen) 60 yen
Utility

36

Item4

Item3

Item2

Item130 yen 30 yen 60 yen 30 yen
27
12502814

Represent the constraint of theknapsack problem by a BDD

Equivalent nodes
are shared(Budget for thissubproblem is 10)15

Represent the constraint of theknapsack problem by a BDD

16

Represent the constraint of theknapsack problem by a BDD◼

◼

◼

Once the BDD representing the constraints areobtained, it is easy to minimize/maximize
the linear sum of the costs
Note that, however, if our task is just an optimization,
it is not recommended to construct BDDs
(since it requires much computation time andhuge memory consumption)
Benefits of constructing BDDs◼

◼

Optimization with changing the objective function(We can ovoid searching the solution space twice ormore for different objective function)
We can combine the BDDs with other constraints(Apply operation is easy)17Summary◼
◼

Design and verification of logic circuits
Combinatorial problems and optimization◼
◼
◼

Determine whether a given combination is a feasible
solution or not
Evaluate the linear sum of the costsEx.） Knapsack problem

1819