[Back]

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