IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v35y2023i5p910-928.html
   My bibliography  Save this article

On Aligning Non-Order-Associated Binary Decision Diagrams

Author

Listed:
  • 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)

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.

Suggested Citation

  • Alexey A. Bochkarev & J. Cole Smith, 2023. "On Aligning Non-Order-Associated Binary Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 910-928, September.
    • Handle: RePEc:inm:orijoc:v:35:y:2023:i:5:p:910-928
    DOI: 10.1287/ijoc.2023.1293
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2023.1293
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2023.1293?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Owen, Susan Hesse & Daskin, Mark S., 1998. "Strategic facility location: A review," European Journal of Operational Research, Elsevier, vol. 111(3), pages 423-447, December.
    2. Leonardo Lozano & David Bergman & J. Cole Smith, 2020. "On the Consistent Path Problem," Operations Research, INFORMS, vol. 68(6), pages 1913-1931, November.
    3. ReVelle, C.S. & Eiselt, H.A. & Daskin, M.S., 2008. "A bibliography for some fundamental problem categories in discrete location science," European Journal of Operational Research, Elsevier, vol. 184(3), pages 817-848, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Rodolfo Mendoza-Gómez & Roger Z. Ríos-Mercado & Karla B. Valenzuela-Ocaña, 2019. "An Efficient Decision-Making Approach for the Planning of Diagnostic Services in a Segmented Healthcare System," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 18(05), pages 1631-1665, September.
    2. Rentizelas, Athanasios A. & Tatsiopoulos, Ilias P., 2010. "Locating a bioenergy facility using a hybrid optimization method," International Journal of Production Economics, Elsevier, vol. 123(1), pages 196-209, January.
    3. Tomaz Dentinho & Vasco Silva, 2012. "Optimization of Location Services in the city of Huambo. Confirmation of the Theory of Central Places," ERSA conference papers ersa12p254, European Regional Science Association.
    4. Varsei, Mohsen & Polyakovskiy, Sergey, 2017. "Sustainable supply chain network design: A case of the wine industry in Australia," Omega, Elsevier, vol. 66(PB), pages 236-247.
    5. Mingjian Wu & Tae J. Kwon & Karim El-Basyouny, 2020. "A Citywide Location-Allocation Framework for Driver Feedback Signs: Optimizing Safety and Coverage of Vulnerable Road Users," Sustainability, MDPI, vol. 12(24), pages 1-20, December.
    6. Haase, Knut & Hoppe, Mirko, 2008. "Standortplanung unter Wettbewerb - Teil 1: Grundlagen," Discussion Papers 2/2008, Technische Universität Dresden, "Friedrich List" Faculty of Transport and Traffic Sciences, Institute of Transport and Economics.
    7. Shariat-Mohaymany, Afshin & Babaei, Mohsen & Moadi, Saeed & Amiripour, Sayyed Mahdi, 2012. "Linear upper-bound unavailability set covering models for locating ambulances: Application to Tehran rural roads," European Journal of Operational Research, Elsevier, vol. 221(1), pages 263-272.
    8. Jimenez, Charlotte & Dauzère-Pérès, Stéphane & Feuillebois, Christian & Pauly, Eric, 2013. "Optimizing the positioning and technological choices of RFID elements for aircraft part identification," European Journal of Operational Research, Elsevier, vol. 227(2), pages 350-357.
    9. Sanjay Jena & Jean-François Cordeau & Bernard Gendron, 2015. "Modeling and solving a logging camp location problem," Annals of Operations Research, Springer, vol. 232(1), pages 151-177, September.
    10. Sarkar, Biswajit & Majumder, Arunava, 2013. "A study on three different dimensional facility location problems," Economic Modelling, Elsevier, vol. 30(C), pages 879-887.
    11. Dönmez, Zehranaz & Kara, Bahar Y. & Karsu, Özlem & Saldanha-da-Gama, Francisco, 2021. "Humanitarian facility location under uncertainty: Critical review and future prospects," Omega, Elsevier, vol. 102(C).
    12. Gross, Wendelin & Butz, Christian, 2014. "Design of Sustainable Transportation Networks," Chapters from the Proceedings of the Hamburg International Conference of Logistics (HICL), in: Kersten, Wolfgang & Blecker, Thorsten & Ringle, Christian M. (ed.), Next Generation Supply Chains: Trends and Opportunities. Proceedings of the Hamburg International Conference of Logistics (HICL), Vol. 18, volume 18, pages 137-160, Hamburg University of Technology (TUHH), Institute of Business Logistics and General Management.
    13. Ramos Manoel João & Feiden Aldi & Sousa Fragoso Rui Manuel de, 2019. "A Multi-objective Approach for Supply Chain Network Design: Tilapia Pisciculture in Paraná State - Brazil," Journal of Agricultural & Food Industrial Organization, De Gruyter, vol. 17(1), pages 1-14, May.
    14. Wu, Shanhua & Yang, Zhongzhen, 2018. "Locating manufacturing industries by flow-capturing location model – Case of Chinese steel industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 112(C), pages 1-11.
    15. Wu, Shanhua & Yang, Zhongzhen, 2018. "Optimizing location of manufacturing industries in the context of economic globalization: A bi-level model based approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 501(C), pages 327-337.
    16. Fetter, Gary & Rakes, Terry, 2012. "Incorporating recycling into post-disaster debris disposal," Socio-Economic Planning Sciences, Elsevier, vol. 46(1), pages 14-22.
    17. Kress, Dominik & Pesch, Erwin, 2012. "Sequential competitive location on networks," European Journal of Operational Research, Elsevier, vol. 217(3), pages 483-499.
    18. Alan Murray, 2010. "Advances in location modeling: GIS linkages and contributions," Journal of Geographical Systems, Springer, vol. 12(3), pages 335-354, September.
    19. Robert F. Dell & P. Lee Ewing & William J. Tarantino, 2008. "Optimally Stationing Army Forces," Interfaces, INFORMS, vol. 38(6), pages 421-435, December.
    20. Klibi, Walid & Martel, Alain & Guitouni, Adel, 2010. "The design of robust value-creating supply chain networks: A critical review," European Journal of Operational Research, Elsevier, vol. 203(2), pages 283-293, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:35:y:2023:i:5:p:910-928. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.