...

Optimization Bounds from Binary Decision Diagrams J. N. Hooker

by user

on
Category: Documents
1

views

Report

Comments

Transcript

Optimization Bounds from Binary Decision Diagrams J. N. Hooker
Optimization Bounds from
Binary Decision Diagrams
J. N. Hooker
Joint work with
David Bergman, André Ciré, Willem van Hoeve
Carnegie Mellon University
Boolean Workshop, April 2013
Binary Decision Diagrams
• BDDs historically used for circuit design and verification.
– Lee 1959, Akers 1978, Bryant 1986.
Binary Decision Diagrams
• BDDs historically used for circuit design and verification.
– Lee 1959, Akers 1978, Bryant 1986.
• Compact graphical representation of boolean function.
– Can also represent feasible set of problem with binary
variables.
– Slight generalization (MDDs) represents finite domain variables.
Binary Decision Diagrams
• BDD is result of superimposing isomorphic subtrees in a
search tree.
– Unique reduced BDD for given variable ordering.
– “Caching” is a popular theme in knowledge representation.
• Constraints need not have an inequality representation.
The 0-1 inequality
300 x0  300 x1  285 x2  285 x3  265 x4  265 x5  230 x6
230 x7  190 x8  200 x9  400 x10  200 x11  400 x12  200 x13
400 x14  200 x15  400 x16  200 x17  400 x18  2700
has 117,520 minimal
solutions
The 0-1 inequality
300 x0  300 x1  285 x2  285 x3  265 x4  265 x5  230 x6
230 x7  190 x8  200 x9  400 x10  200 x11  400 x12  200 x13
400 x14  200 x15  400 x16  200 x17  400 x18  2700
has 117,520 minimal
solutions
The BDD has only 152
nodes.
Paths from top to bottom
right correspond to feasible
solutions
Binary Decision Diagrams
• BDD can grow exponentially with problem size.
– So we use a smaller, relaxed BDD that represents superset of
feasible set.
• Andersen, Hadzic, Hooker, Tiedemann 2007.
• For alldiff systems, reduced search tree from
>1 million nodes to 1 node.
• Subsequent papers with Hadzic, Hoda, van Hoeve,
O’Sullivan.
• We focus on independent set problem on a graph…
Independent Set Problem
Let each vertex have weight wi
Select nonadjacent vertices to maximize
w x
i
i
2
3
4
1
6
5
i
2
x1
3
4
1
6
x2
5
x3
Exact BDD for
independent set
problem
x4
“zero-suppressed”
BDD
x5
x6
2
x1
3
x1 = 1
4
1
6
5
x2 = 0
x2
x3
Exact BDD for
independent set
problem
x4
“zero-suppressed”
BDD
x5
x6
2
x1
3
4
1
6
x2
5
x3
Paths from top
to bottom
correspond to
the 11 feasible
solutions
x4
x5
x6
2
x1
3
4
1
6
x2
5
x3
Paths from top
to bottom
correspond to
the 11 feasible
solutions
x4
x5
x6
2
x1
3
4
1
6
x2
5
x3
Paths from top
to bottom
correspond to
the 11 feasible
solutions
x4
x5
x6
2
x1
3
4
1
6
x2
5
x3
Paths from top
to bottom
correspond to
the 11 feasible
solutions
x4
x5
x6
2
x1
3
4
1
6
x2
5
x3
Paths from top
to bottom
correspond to
the 11 feasible
solutions
…and so
forth
x4
x5
x6
2
x1
3
4
1
6
w1
0
x2
0
5
w2
For objective
function,
associate
weights with
arcs
x3
0
w3
w3
w4
0
0
0
x4
w4
x5
0
0
w5
w6
0
w5
x6
2
x1
3
4
1
6
w1
0
x2
0
5
w2
For objective
function,
associate
weights with
arcs
x3
0
w3
w3
w4
0
0
0
x4
w4
x5
0
Optimal solution
is longest path
0
w5
w6
0
w5
x6
Objective Function
• In general, objective function can be any separable
function.
– Linear or nonlinear, convex or nonconvex
• BDDs can be generalized to nonseparable objective
functions.
– There is a unique reduced BDD with canonical edge costs.
2
3
{123456}
x1
{23456}
x2
4
1
6
5
{3456}
{35}
{456}
To build BDD,
associate state
with each node
x4
{4}
{56}
x3
{5}
x5
x6
{6}

2
{123456}
3
4
1
6
x1
x2
5
x3
x4
x5
To build BDD,
associate state
with each node
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{35}
x3
x4
x5
To build BDD,
associate state
with each node
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
{35}
{4}
x3
x4
x5
To build BDD,
associate state
with each node
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
{456}
{35}
x4
{4}
{5}
Merge nodes
that correspond
to the same
state
x3
x5
x6

2
3
{123456}
x1
{23456}
x2
4
1
6
5
{3456}
{35}
{456}
Merge nodes
that correspond
to the same
state
x4
{4}
{56}
x3
{5}
x5
x6
{6}

2
3
{123456}
x1
{23456}
x2
4
1
6
5
{3456}
{35}
{456}
Merge nodes
that correspond
to the same
state
x4
{4}
{56}
x3
{5}
x5
x6
{6}

2
3
{123456}
x1
{23456}
x2
4
1
6
5
{3456}
{35}
x3
Width = 2
{456}
{56}
Merge nodes
that correspond
to the same
state
x4
{4}
{5}
x5
x6
{6}

2
{123456}
3
4
1
6
x1
x2
5
x3
x4
To build relaxed
BDD, merge
some additional
nodes as we go
along
x5
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{35}
x3
x4
To build relaxed
BDD, merge
some additional
nodes as we go
along
x5
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
{35}
{4}
To build relaxed
BDD, merge
some additional
nodes as we go
along
x3
x4
x5
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
{4}
To build relaxed
BDD, merge
some additional
nodes as we go
along
x3
x4
x5
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
{456}
{4}
To build relaxed
BDD, merge
some additional
nodes as we go
along
x3
x4
x5
x6

2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
{456}
To build relaxed
BDD, merge
some additional
nodes as we go
along
x3
x4
x5
x6

2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
x4
{456}
To build relaxed
BDD, merge
some additional
nodes as we go
along
{56}
{6}

x3
x5
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
x4
{456}
To build relaxed
BDD, merge
some additional
nodes as we go
along
{56}
{6}

x3
x5
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
x3
Width = 1
x4
{456}
To build relaxed
BDD, merge
some additional
nodes as we go
along
{56}
{6}

x5
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
x3
Width = 1
x4
{456}
Represents 18
solutions,
including 11
feasible
solutions
{56}
{6}

x5
x6
2
3
4
1
6
{123456}
x1
{23456}
x2
5
{3456}
x3
Width = 1
x4
{456}
Longest path
gives bound
of 3 on optimal
value of 2
{56}
{6}

x5
x6
Variable Ordering
• Variable ordering is key.
– Just as in branching methods.
– Some orderings provide much tighter bounds.
• Width of exact BDD is bounded by Fibonacci numbers.
– For an ordering induced by maximal path decomposition of the
graph.
• We used a dynamic ordering heuristic.
– Next variable is the one appearing in the smallest number of
states on the current level.
• Better than maximal path ordering.
Merging Heuristic
• Which nodes to merge when building relaxation?
• A longest path heuristic seems by far the best.
– Order nodes on current layer by increasing length
of longest path into each node.
– Merge nodes in this order.
– We lose information in areas not likely to be part of the solution.
• This is better than merging nodes with more vertices in
the corresponding states.
Width of BDD
• Wider BDDs
yield tighter
bounds.
– But take
longer to
build.
Comparison with LP Bound
• Random and benchmark instances
• Compare with LP bound at root node in CPLEX
– Use clique cover IP formulation
• Requires precomputing clique cover.
max  w i y i
y
i Ck
i
i
 1, all cliques Ck in clique cover
y i  0,1, all i
Comparison with LP Bound
• CPLEX settings
– Turn off presolve
• It makes CPLEX bound worse or at most 1 better.
• BDD bounds don’t use presolve.
– Use full cutting plane resources
– Use interior point (barrier) LP solver
• Faster than simplex on these instances.
Random instances
10.6
15.0
15.3
LP + cuts
7.8
Bound / Optimal value
13.6
9.4
9.8
4.6
0.9
3.7
1.1
0.8
Solution time, sec
BDD 1000
0.7
15.0
13.8
0.5
11.8
BDD 10,000
0.2
7.8
3.9
Density
0.5
0.07
0.02
0.01
0.07
0.02
0.01
BDD 1000 Bound / Optimal value
Random instances
3.7
1.1
BDD 10,000
0.07
Density 0.5
LP+cuts Bound / Optimal value
BDD 10,000 Bound / Optimal value
Random instances
LP+cuts Bound / Optimal value
DIMACS instances
45.1
Bound / Optimal value
LP + cuts
149
50.2
3.5
6.5
55.4
6.5
BDD 1000
43.6
34.3
BDD 10,000
6.9
2.9
10.4
4.2
0.01
Density
0.01
BDD 1000 Bound / Optimal value
DIMACS instances
LP+cuts Bound / Optimal value
BDD 10,000 Bound / Optimal value
DIMACS instances
LP+cuts Bound / Optimal value
Incrementality
• Fast incremental calculation of bound.
– Modify relaxed BDD after variable is fixed in branching tree
(fast).
– Recompute longest path (fast).
• However, may be better to rebuild relaxation from
scratch.
– Research issue.
Recent Work
• Restricted BDDs as primal heuristic
– All paths are feasible.
– Longest path is a good feasible solution
– Reduce width by intelligently removing nodes.
• Apply to independent set problem
– DIMACS instances
– Compare with lower bound obtained by CPLEX primal heuristics
at rote node.
1
Restricted BDD
Width = 3
2
6
5
3
1
4
4
2
3
5
Longest path is
feasible solution
and gives upper bound
of 2 on optimal value of 3
6
DIMACS instances
Recent Work
• General BDD-based solver
– Branch in the BDD.
– Combine with BDD-based propagation
– BDD-based bounds, primal heuristic
• No LP relaxation, cutting planes
– Linearity, convexity irrelevant
• Possibly nonseparable objective function
– Dynamic programming style formulation
• Specify state variable for BDDs
– Integrate MIP, BDDs, CP, DP.
Recent Work
• Novel branching scheme
– Branch in relaxed BDD.
– Branch on pools of partial solutions.
– Reduce symmetry.
Relaxed BDD
6
Exact down
to here
5
1
2
3
1
4
4
2
3
5
6
Relaxed BDD
6
5
Branch on nodes
in this layer
1
2
3
1
4
4
2
3
5
6
Relaxed BDD
1
2
6
First branch
5
3
1
4
4
2
3
5
6
Relaxed BDD
1
2
6
5
Second branch
3
1
4
4
2
3
5
6
Relaxed BDD
1
2
6
Third branch
5
3
1
4
4
2
3
5
Continue recursively
6
DIMACS instances
Root Node Gap Comparison
DIMACS instances
Number Solved Comparison
End Gap Comparison
Fly UP