Details

Autor(en) / Beteiligte

• Nafar, Mohsen
• Römer, Michael
• Dilkina, Bistra

Titel

Lookahead, Merge and Reduce for Compiling Relaxed Decision Diagrams for Optimization

Ist Teil von

• Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2024, p.74-82

Ort / Verlag

Cham: Springer Nature Switzerland

Erscheinungsjahr

2024

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• In this paper, we propose a new approach for the top-down compilation of relaxed Binary Decision Diagrams (BDDs) for Discrete Optimization: Lookahead, Merge and Reduce. The approach is inspired by the bottom-up algorithm for reducing exact BDDs in which equivalent nodes, that is, nodes with the same partial completions, are merged. In our top-down compilation approach, we apply this reduction algorithm for determining which states to be merged by constructing a lookahead layer, merging the lookahead layer nodes according to some heuristic and then deeming nodes having the same feasible completions in the lookahead BDD as approximately equivalent. Moreover, under certain structural properties we prove an upper limit on the size of the reduced layers given the size of the merged lookahead layer. In a set of preliminary computational experiments, we evaluate our approach for the 0/1 Knapsack problem, showing that the approach often achieves much stronger bounds than the traditional top-down compilation scheme.