Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Behle, M.: Binary decision diagrams and integer programming (2007)
Bergman, D., Cire, A.A., van Hoeve, W.-J., Hooker, J.: Branch-and-bound based on decision diagrams. In: Bergman, D., Cire, A.A., van Hoeve, W.-J., Hooker, J. (eds.) Decision Diagrams for Optimization. AIFTA, pp. 95–122. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-42849-9_6
Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 100(8), 677–691 (1986)
Castro, M.P., Cire, A.A., Christopher Beck, J.: Decision diagrams for discrete optimization: a survey of recent advances. INFORMS J. Comput. 34(4), 2271–2295 (2022)
de Weerdt, M., Baart, R., He, L.: Single-machine scheduling with release times, deadlines, setup times, and rejection. Eur. J. Oper. Res. 291(2), 629–639 (2021)
Frohner, N., Raidl, G.R.: Towards improving merging heuristics for binary decision diagrams. In: Matsatsinis, N.F., Marinakis, Y., Pardalos, P. (eds.) LION 2019. LNCS, vol. 11968, pp. 30–45. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-38629-0_3
Hooker, J.N.: Job sequencing bounds from decision diagrams. In: Beck, J.C. (ed.) CP 2017. LNCS, vol. 10416, pp. 565–578. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66158-2_36
Horn, M., Maschler, J., Raidl, G.R., Rönnberg, E.: A-based construction of decision diagrams for a prize-collecting scheduling problem. Comput. Oper. Res. 126, 105125 (2021)
Perez, G.: Decision diagrams: constraints and algorithms. Ph.D. thesis, Université Côte d’Azur (2017)
Pisinger, D.: Where are the hard Knapsack problems? Comput. Oper. Res. 32(9), 2271–2284 (2005)
Wegener, I.: Branching Programs and Binary Decision Diagrams: Theory and Applications. SIAM (2000)
Acknowledgements
This research was funded by the Return Programme of the Federal State of North Rhine Westphalia (NRW Rückkehrprogramm).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Nafar, M., Römer, M. (2024). Lookahead, Merge and Reduce for Compiling Relaxed Decision Diagrams for Optimization. In: Dilkina, B. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024. Lecture Notes in Computer Science, vol 14743. Springer, Cham. https://doi.org/10.1007/978-3-031-60599-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-60599-4_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-60601-4
Online ISBN: 978-3-031-60599-4
eBook Packages: Computer ScienceComputer Science (R0)