On Aligning Non-Order-Associated Binary Decision Diagrams
研究了如何最优对齐两个二元决策图（BDD），即通过最小化总大小来强制变量顺序一致。通过引入简化问题并设计启发式算法，实验表明该方法能有效降低中间图变换的复杂度，并应用于无容量设施选址问题。
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. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Funding: This work was supported by the Office of Naval Research [Grant N00014-17-1-2421]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/ijoc.2023.1293 .