On Aligning Non-Order-Associated Binary Decision Diagrams

Alexey A. Bochkarev, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)910-928
Number of pages19
JournalINFORMS Journal on Computing
Volume35
Issue number5
DOIs
StatePublished - Sep 2023

Keywords

  • analysis of algorithms
  • binary decision diagrams
  • combinatorial optimization problems
  • data structures

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'On Aligning Non-Order-Associated Binary Decision Diagrams'. Together they form a unique fingerprint.

Cite this