On Aligning Non-Order-Associated Binary Decision Diagrams

Alexey A. Bochkarev () and J. Cole Smith ()
Additional contact information
Alexey A. Bochkarev: Department of Mathematics, Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau, Kaiserslautern 67663, Germany
J. Cole Smith: Department of Electrical Engineering and Computer Science, Syracuse University, Syracuse, New York 13244

INFORMS Journal on Computing, 2023, vol. 35, issue 5, 910-928

Abstract: Recent studies employ collections of binary decision diagrams (BDDs) to solve combinatorial optimization problems. This paper focuses on the problem of optimally aligning two BDDs, that is, transforming them to enforce a common order of variables while keeping the total size of the diagrams as small as possible. We address this problem, which is known to be NP-hard, by introducing and studying a simplified problem instead of working with the more complex original diagrams. We discuss some basic properties of the simplified problem, design a corresponding heuristic for the original problem, and show empirically that this approach yields good quality alignments while significantly reducing the complexity of intermediate diagram transformations. We highlight the practicality of this approach in the context of a variation of the uncapacitated facility location problem.

Keywords: analysis of algorithms; data structures; binary decision diagrams; combinatorial optimization problems (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.1293 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:5:p:910-928

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().