Variable Ordering
One of the most important parameters that determines the size of a decision diagram is the variable ordering. In this chapter we formally study the impact of variable ordering on the size of exact decision diagrams for the maximum independent set problem.
- PDF / 250,189 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 55 Downloads / 220 Views
Variable Ordering
Abstract One of the most important parameters that determines the size of a decision diagram is the variable ordering. In this chapter we formally study the impact of variable ordering on the size of exact decision diagrams for the maximum independent set problem. We provide worst-case bounds on the size of the exact decision diagram for particular classes of graphs. For general graphs, we show that the size is bounded by the Fibonacci numbers. Lastly, we demonstrate experimentally that variable orderings that produce small exact decision diagrams also produce better bounds from relaxed decision diagrams.
7.1 Introduction The ordering of the vertices plays an important role in not only the size of exact decision diagrams, but also in the bound obtained by DD-based relaxations and restrictions. It is well known that finding orderings that minimize the size of DDs (or even improving on a given ordering) is NP-hard [58, 35]. We found that the ordering of the vertices is the single most important parameter in creating smallwidth exact DDs and in proving tight bounds via relaxed DDs. In this chapter we analyze how the combinatorial structure of a problem can be exploited to develop variable orderings that bound the size of the DD representing its solution space. We will particularly focus on the maximum independent set problem (MISP) for our analysis, first described in Section 3.5. Given a graph G = (V, E) with a vertex set V , an independent set I is a subset I ⊆ V such that no two vertices in I are connected by an edge in E, i.e., (u, v) ∈ E for any distinct u, v ∈ I. If we
© Springer International Publishing Switzerland 2016 D. Bergman et al., Decision Diagrams for Optimization, Artificial Intelligence: Foundations, Theory, and Algorithms, DOI 10.1007/978-3-319-42849-9_7
123
124
7 Variable Ordering
associate weights with each vertex j ∈ V , the MISP asks for a maximum-weight independent set of G. Since variables are binaries, the resulting diagram is a binary decision diagram (BDD). Different orderings can yield exact BDDs with dramatically different widths. For example, Fig. 7.1 shows a path on six vertices with two different orderings given by x1 , . . . , x6 and y1 , . . . , y6 . In Fig. 7.2(a) we see that the vertex ordering x1 , . . . , x6 yields an exact BDD with width 1, while in Fig. 7.2(b) the vertex ordering y1 , . . . , y6 yields an exact BDD with width 4. This last example can be extended to a path with 2n vertices, yielding a BDD with a width of 2n−1 , while ordering the vertices according to the order in which they lie on the paths yields a BDD of width 1.
x1
x2
x3
x4
x5
x6
y1
y4
y2
y5
y3
y6
Fig. 7.1 Path graph.
x1
y1
x2
y2
x3
y3
x4
y4
x5
y5
x6
y6 (a)
(b)
Fig. 7.2 (a) Variable order that results in a small reduced BDD. (b) Variable order that results in a larger reduced BDD.
Our study focuses on studying variable orderings for the layers of a BDD representing the set of feasible solutions to a MISP instance. For particular classes of graphs, variabl
Data Loading...
