N. Frohner, G. Raidl:

"Towards Improving Merging Heuristicsfor Binary Decision Diagrams";

Talk: Learning and Intelligent OptimizatioN Conference LION, Chania, Greece; 2019-05-27 - 2019-05-31; in: "LION 2019: Learning and Intelligent Optimization", LNCS, 11968 (2020), ISBN: 978-3-030-38628-3; 30 - 45.

Over the last years, binary decision diagrams (BDDs) have

become a powerful tool in the field of combinatorial optimization. They

are directed acyclic multigraphs and represent the solution space of

binary optimization problems in a recursive way. During their construction,

merging of nodes in this multigraph is applied to keep the size

within polynomial bounds resulting in a discrete relaxation of the original

problem. The longest path length through this diagram corresponds

then to an upper bound of the optimal objective value. The algorithm

deciding which nodes to merge is called a merging heuristic. A commonly

used heuristic for layer-wise construction is minimum longest path length

(minLP) which sorts the nodes in a layer descending by the currently

longest path length to them and subsequently merges the worst ranked

nodes to reduce the width of a layer. A shortcoming of this approach is

that it neglects the (dis-)similarity between states it merges, which we

assume to have negative impact on the quality of the finally obtained

bound. By means of a simple tie breaking procedure, we show a way

to incorporate the similarity of states into minLP using different distance

functions to improve dual bounds for the maximum independent

set problem (MISP) and the set cover problem (SCP), providing empirical

evidence for our assumption. Furthermore, we extend this procedure

by applying similarity-based node merging also to nodes with close but

not necessarily identical longest path values. This turns out to be beneficial

for weighted problems where ties are substantially less likely to

occur. We evaluate the method on the weighted MISP and tune parameters

that control as to when to apply similarity-based node merging.

http://dx.doi.org/10.1007/978-3-030-38629-0

https://publik.tuwien.ac.at/files/publik_293655.pdf

Created from the Publication Database of the Vienna University of Technology.