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

Decision Diagrams for Discrete Optimization: A Survey of Recent Advances

Author

Listed:
  • Margarita P. Castro

    (Department of Industrial and Systems Engineering, Pontificia Universidad Católica de Chile, Santiago 7820436, Chile)

  • Andre A. Cire

    (Department of Management, University of Toronto Scarborough and Rotman School of Management, Toronto, Ontario M1E 1A4, Canada)

  • J. Christopher Beck

    (Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada)

Abstract

In the last decade, decision diagrams (DDs) have been the basis for a large array of novel approaches for modeling and solving optimization problems. Many techniques now use DDs as a key tool to achieve state-of-the-art performance within other optimization paradigms, such as integer programming and constraint programming. This paper provides a survey of the use of DDs in discrete optimization, particularly focusing on recent developments. We classify these works into two groups based on the type of diagram (i.e., exact or approximate) and present a thorough description of their use. We discuss the main advantages of DDs, point out major challenges, and provide directions for future work.

Suggested Citation

  • Margarita P. Castro & Andre A. Cire & J. Christopher Beck, 2022. "Decision Diagrams for Discrete Optimization: A Survey of Recent Advances," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2271-2295, July.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:4:p:2271-2295
    DOI: 10.1287/ijoc.2022.1170
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1170
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.1170?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. Christian Tjandraatmadja & Willem-Jan van Hoeve, 2019. "Target Cuts from Relaxed Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 285-301, April.
    2. David Bergman & Leonardo Lozano, 2021. "Decision Diagram Decomposition for Quadratically Constrained Binary Optimization," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 401-418, January.
    3. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    4. Markus Behle, 2008. "On threshold BDDs and the optimal variable ordering problem," Journal of Combinatorial Optimization, Springer, vol. 16(2), pages 107-118, August.
    5. de Weerdt, Mathijs & Baart, Robert & He, Lei, 2021. "Single-machine scheduling with release times, deadlines, setup times, and rejection," European Journal of Operational Research, Elsevier, vol. 291(2), pages 629-639.
    6. David R. Morrison & Edward C. Sewell & Sheldon H. Jacobson, 2016. "Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 67-82, February.
    7. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    8. Marshall L. Fisher, 2004. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 50(12_supple), pages 1861-1871, December.
    9. R. Kipp Martin, 1987. "Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition," Operations Research, INFORMS, vol. 35(6), pages 820-831, December.
    10. Andre A. Cire & Willem-Jan van Hoeve, 2013. "Multivalued Decision Diagrams for Sequencing Problems," Operations Research, INFORMS, vol. 61(6), pages 1411-1428, December.
    11. Selvaprabu Nadarajah & Andre A. Cire, 2020. "Network-Based Approximate Linear Programming for Discrete Optimization," Operations Research, INFORMS, vol. 68(6), pages 1767-1786, November.
    12. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    13. Cheng Guo & Merve Bodur & Dionne M. Aleman & David R. Urbach, 2021. "Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1551-1569, October.
    14. Kinable, Joris & Cire, Andre A. & van Hoeve, Willem-Jan, 2017. "Hybrid optimization methods for time-dependent sequencing problems," European Journal of Operational Research, Elsevier, vol. 259(3), pages 887-897.
    15. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2012. "New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 356-371, August.
    16. Daniel Kowalczyk & Roel Leus, 2018. "A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 768-782, November.
    17. Marshall L. Fisher, 2004. "Comments on ÜThe Lagrangian Relaxation Method for Solving Integer Programming ProblemsÝ," Management Science, INFORMS, vol. 50(12_supple), pages 1872-1874, December.
    18. Amin Hosseininasab & Willem-Jan van Hoeve, 2021. "Exact Multiple Sequence Alignment by Synchronized Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 721-738, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. MacNeil, Moira & Bodur, Merve, 2024. "Leveraging decision diagrams to solve two-stage stochastic programs with binary recourse and logical linking constraints," European Journal of Operational Research, Elsevier, vol. 315(1), pages 228-241.

    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. Margarita P. Castro & Andre A. Cire & J. Christopher Beck, 2020. "An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 263-278, April.
    2. Selvaprabu Nadarajah & Andre A. Cire, 2020. "Network-Based Approximate Linear Programming for Discrete Optimization," Operations Research, INFORMS, vol. 68(6), pages 1767-1786, November.
    3. Zhang, Guowei & Jia, Ning & Zhu, Ning & Adulyasak, Yossiri & Ma, Shoufeng, 2023. "Robust drone selective routing in humanitarian transportation network assessment," European Journal of Operational Research, Elsevier, vol. 305(1), pages 400-428.
    4. Arvind U. Raghunathan & David Bergman & John N. Hooker & Thiago Serra & Shingo Kobori, 2024. "Seamless Multimodal Transportation Scheduling," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 336-358, March.
    5. Amin Hosseininasab & Willem-Jan van Hoeve, 2021. "Exact Multiple Sequence Alignment by Synchronized Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 721-738, May.
    6. Ioannis Fragkos & Zeger Degraeve & Bert De Reyck, 2016. "A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 465-482, August.
    7. Guopeng Song & Roel Leus, 2022. "Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3059-3079, November.
    8. An, Yu & Zhang, Yu & Zeng, Bo, 2015. "The reliable hub-and-spoke design problem: Models and algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 103-122.
    9. Dollevoet, Twan & van Essen, J. Theresia & Glorie, Kristiaan M., 2018. "Solution methods for the tray optimization problem," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1070-1084.
    10. Alexandre Belloni & Mitchell J. Lovett & William Boulding & Richard Staelin, 2012. "Optimal Admission and Scholarship Decisions: Choosing Customized Marketing Offers to Attract a Desirable Mix of Customers," Marketing Science, INFORMS, vol. 31(4), pages 621-636, July.
    11. Zhizhu Lai & Qun Yue & Zheng Wang & Dongmei Ge & Yulong Chen & Zhihong Zhou, 2022. "The min-p robust optimization approach for facility location problem under uncertainty," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1134-1160, September.
    12. Junming Liu & Weiwei Chen & Jingyuan Yang & Hui Xiong & Can Chen, 2022. "Iterative Prediction-and-Optimization for E-Logistics Distribution Network Design," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 769-789, March.
    13. Zheng, Jianfeng & Meng, Qiang & Sun, Zhuo, 2014. "Impact analysis of maritime cabotage legislations on liner hub-and-spoke shipping network design," European Journal of Operational Research, Elsevier, vol. 234(3), pages 874-884.
    14. Vasile BRÄ‚TIAN, 2018. "Portfolio Optimization. Application of the Markowitz Model Using Lagrange and Profitability Forecast," Expert Journal of Economics, Sprint Investify, vol. 6(1), pages 26-34.
    15. Muter, İbrahim, 2020. "Exact algorithms to minimize makespan on single and parallel batch processing machines," European Journal of Operational Research, Elsevier, vol. 285(2), pages 470-483.
    16. Miguel A. Lejeune & John Turner, 2019. "Planning Online Advertising Using Gini Indices," Operations Research, INFORMS, vol. 67(5), pages 1222-1245, September.
    17. Guy Desaulniers & Jørgen G. Rakke & Leandro C. Coelho, 2016. "A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem," Transportation Science, INFORMS, vol. 50(3), pages 1060-1076, August.
    18. Claudio Gambella & Joe Naoum-Sawaya & Bissan Ghaddar, 2018. "The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 554-569, August.
    19. Diego Pecin & Claudio Contardo & Guy Desaulniers & Eduardo Uchoa, 2017. "New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 489-502, August.
    20. Zhang, Zhi-Hai & Jiang, Hai & Pan, Xunzhang, 2012. "A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain," International Journal of Production Economics, Elsevier, vol. 140(1), pages 249-255.

    More about this item

    Keywords

    decision diagrams; discrete optimization;

    Statistics

    Access and download statistics

    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:34:y:2022:i:4:p:2271-2295. 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.