Decision Diagrams for Discrete Optimization: A Survey of Recent Advances

References

• Akers SB (1978) Binary decision diagrams. IEEE Trans. Comput. C-27(6):509–516.Crossref, Google Scholar
• Amilhastre J, Fargier H, Niveau A, Pralet C (2014) Compiling CSPs: A complexity map of (non-deterministic) multivalued decision diagrams. Proc. IEEE Internat. Conf. on Tools with Artificial Intelligence, 1–8.Google Scholar
• Andersen HR, Hadžić T, Hooker JN, Tiedemann P (2007) A constraint store based on multivalued decision diagrams. Bessiére C, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 118–132.Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2012) New state-space relaxations for solving the traveling salesman problem with time windows. INFORMS J. Comput. 24(3):356–371.Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MW, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Becker B, Behle M, Eisenbrand F, Wimmer R (2005) BDDs in a branch and cut framework. Nikoletseas SE, ed. Proc. Internat. Workshop on Experiment. and Efficient Algorithms (Springer, Berlin, Heidelberg), 452–463.Google Scholar
• Behle M (2007) Binary decision diagrams and integer programming. PhD thesis, Saarland University, Saarbrücken, Germany.Google Scholar
• Behle M (2008) On threshold BDDs and the optimal variable ordering problem. J. Comb. Optim. 16(2):107–118.Crossref, Google Scholar
• Behle M, Eisenbrand F (2007) 0/1 vertex and facet enumeration with BDDs. Applegate D, Brodal GS, eds. Proc. of the Ninth Workshop on Algorithm Engineering and Experiments (SIAM, Philadeplhia), 158–165.Google Scholar
• Benders J (1962) Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4(1):238–252.Crossref, Google Scholar
• Bergman D, Cire AA (2016a) Decomposition based on decision diagrams. Quimper C-G, ed. Proc. Internat. Conf. on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Springer, Berlin, Heidelberg), 45–54.Google Scholar
• Bergman D, Cire AA (2016b) Multiobjective optimization by decision diagrams. Rueher M, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 86–95.Google Scholar
• Bergman D, Cire AA (2016c) Theoretical insights and algorithmic tools for decision diagram-based optimization. Constraints 21(4):533–556.Crossref, Google Scholar
• Bergman D, Cire AA (2017) On finding the optimal BDD relaxation. Salvagnin D, Lombardi M, eds. Proc. Internat. Conf. on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Springer, Berlin, Heidelberg), 41–50.Google Scholar
• Bergman D, Cire AA (2018) Discrete nonlinear optimization by state-space decompositions. Management Sci. 64(10):4700–4720.Link, Google Scholar
• Bergman D, Lozano L (2021) Decision diagram decomposition for quadratically constrained binary optimization. INFORMS J. Comput. 33(1):401–418.Link, Google Scholar
• Bergman D, Cardonha C, Mehrani S (2019) Binary decision diagrams for bin packing with minimum color fragmentation. Rousseau L-M, Stergiou K, eds. Proc. Internat. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (Springer, Berlin, Heidelberg), 57–66.Google Scholar
• Bergman D, Cire AA, van Hoeve WJ (2014a) MDD propagation for sequence constraints. J. Artificial Intelligence Res. 50(1):697–722.Crossref, Google Scholar
• Bergman D, Cire AA, van Hoeve WJ (2015a) Improved constraint propagation via Lagrangian decomposition. Pesant G, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 30–38.Google Scholar
• Bergman D, Cire AA, van Hoeve WJ (2015b) Lagrangian bounds from decision diagrams. Constraints. 20(3):346–361.Crossref, Google Scholar
• Bergman D, van Hoeve WJ, Hooker JN (2011) Manipulating MDD relaxations for combinatorial optimization. Achterberg T, Beck JC, eds. Proc. Internat. Conf. on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Springer, Berlin, Heidelberg), 20–35.Google Scholar
• Bergman D, Bodur M, Cardonha C, Cire AA (2021) Network models for multiobjective discrete optimization. INFORMS J. Comput. In press.Link, Google Scholar
• Bergman D, Cire AA, van Hoeve WJ, Hooker JN (2014b) Optimization bounds from binary decision diagrams. INFORMS J. Comput. 26(2):253–268.Link, Google Scholar
• Bergman D, Cire AA, van Hoeve WJ, Hooker JN (2016a) Decision Diagrams for Optimization, 1st ed. (Springer International Publishing).Crossref, Google Scholar
• Bergman D, Cire AA, van Hoeve WJ, Hooker JN (2016b) Discrete optimization with decision diagrams. INFORMS J. Comput. 28(1):47–66.Link, Google Scholar
• Bergman D, Cire AA, van Hoeve WJ, Yunes T (2014c) BDD-based heuristics for binary optimization. J. Heuristics 20(2):211–234.Crossref, Google Scholar
• Bergman D, Cire AA, Sabharwal A, Samulowitz H, Saraswat V, van Hoeve WJ (2014d) Parallel combinatorial optimization with decision diagrams. Simonis H, ed. Proc. Internat. Conf. on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Springer, Berlin, Heidelberg), 351–367.Google Scholar
• Bertsekas DP (2017) Dynamic Programming and Optimal Control vol. 1, 3rd ed. (Athena Scientific, Belmont, MA).Google Scholar
• Bollig B, Wegener I (1996) Improving the variable ordering of OBDDs is NP-complete. IEEE Trans. Comput. 45(9):993–1002.Crossref, Google Scholar
• Bryant RE (1986) Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 100(8):677–691.Crossref, Google Scholar
• Bryant RE (1992) Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Comput. Survey 24(3):293–318.Crossref, Google Scholar
• Cappart Q, Goutierre E, Bergman D, Rousseau LM (2019) Improving optimization bounds using machine learning: Decision diagrams meet deep reinforcement learning. Van Hentenryck P, Zhou Z-H, eds. Proc. Conf. AAAI Artificial Intelligence (AAAI Press, Palo Alto, CA) 33:1443–1451.Google Scholar
• Castro MP, Cire AA, Beck JC (2020a) An MDD-based Lagrangian approach to the multi-commodity pickup-and-delivery TSP. INFORMS J. Comput. 32(2):263–278.Abstract, Google Scholar
• Castro MP, Cire AA, Beck JC (2022) A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming. Math. Programming, Forthcoming.Crossref, Google Scholar
• Castro MP, Piacentini C, Cire AA, Beck JC (2018) Relaxed decision diagrams for cost-optimal classical planning. Frances G, Gnad D, Katz M, Lipovetzky N, Muise C, Ramirez M, Sievers S, eds. Proc. Workshop on Heuristics and Search for Domain-Independent Planning (International Conference on Automated Planning and Scheduling, Delft, the Netherlands), 50–58.Google Scholar
• Castro MP, Piacentini C, Cire AA, Beck JC (2019) Relaxed BDDs: An admissible heuristic for delete-free planning based on a discrete relaxation. Lipovetzky N, Onaindia E, Smith D, eds. Proc. Internat. Conf. on Automated Planning and Scheduling (AAAI Press, Palo Alto, CA), 77–85.Google Scholar
• Castro MP, Piacentini C, Cire AA, Beck JC (2020b) Solving delete free planning with relaxed decision diagram based heuristics. J. Artificial Intelligence Res. 67(1):607–651.Crossref, Google Scholar
• Cheng KC, Yap RH (2008) Maintaining generalized arc consistency on ad hoc r-ary constraints. Stuckey PJ, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 509–523.Google Scholar
• Cheng KC, Yap RH (2010) An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints 15(2):265–304.Crossref, Google Scholar
• Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145–164.Crossref, Google Scholar
• Cire AA, Hooker JN (2014) The separation problem for binary decision diagrams. Hellerstein L, Turán G, eds. Proc. Internat. Sympos. on Artificial Intelligence and Math. (International Symposium on Artificial Intelligence and Mathematics, Chicago), 1–7.Google Scholar
• Cire AA, van Hoeve WJ (2012) MDD propagation for disjunctive scheduling. McCluskey L, Williams T, Silva B, Reinaldo J, Bonet B, eds. Proc. Internat. Conf. on Automated Planning and Scheduling (AAAI Press, Palo Alto, CA), 11–19.Google Scholar
• Cire AA, van Hoeve WJ (2013) Multivalued decision diagrams for sequencing problems. Oper. Res. 61(6):1411–1428.Link, Google Scholar
• Cire AA, Diamant A, Yunes T, Carrasco A (2019) A network-based formulation for scheduling clinical rotations. Production Oper. Management 28(5):1186–1205.Crossref, Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming, 1st ed. (Springer International Publishing).Crossref, Google Scholar
• Cornuéjols G (2008) Valid inequalities for mixed integer linear programs. Math. Programming 112(1):3–44.Crossref, Google Scholar
• Davarnia D (2021) Strong relaxations for continuous nonlinear programs based on decision diagrams. Oper. Res. Lett. 49(2):239–245.Crossref, Google Scholar
• Davarnia D, van Hoeve WJ (2021) Outer approximation for integer nonlinear programs via decision diagrams. Math. Programming 187(1):111–150.Crossref, Google Scholar
• de Lima VL, Alves C, Clautiaux F, Iori M, de Carvalho JMV (2022) Arc flow formulations based on dynamic programming: Theoretical foundations and applications. Eur. J. Oper. Res. 296(1):3–21.Crossref, Google Scholar
• de Uña D, Gange G, Schachte P, Stuckey PJ (2019) Compiling CP subproblems to MDDs and d-DNNFs. Constraints 24(1):56–93.Crossref, Google Scholar
• de Weerdt M, Baart R, He L (2021) Single-machine scheduling with release times, deadlines, setup times, and rejection. Eur. J. Oper. Res. 291(2):629–639.Crossref, Google Scholar
• Dijkstra EW, (1959) A note on two problems in connexion with graphs. Numerical Math. 1(1):269–271.Crossref, Google Scholar
• Fisher ML (2004) The Lagrangian relaxation method for solving integer programming problems. Management Sci. 50(12):1861–1871.Link, Google Scholar
• Frohner N, Raidl GR (2019a) Merging quality estimation for binary decision diagrams with binary classifiers. Nicosia G, Pardalos P, Umeton R, Giuffrida G, Sciacca V, eds. Proc. Internat. Conf. on Machine Learn., Optim., and Data Sci. (Springer, Berlin, Heidelberg), 445–457.Google Scholar
• Frohner N, Raidl GR (2019b) Toward improving merging heuristics for binary decision diagrams. Matsatsinis NF, Marinakis Y, Pardalos P, eds. Proc. Internat. Conf. on Learn. and Intelligent Optim. (Springer, Berlin, Heidelberg), 30–45.Google Scholar
• Gange G, Stuckey PJ, Szymanek R (2011) MDD propagators with explanation. Constraints 16(4):407.Crossref, Google Scholar
• Gange G, Stuckey PJ, Van Hentenryck P (2013) Explaining propagators for edge-valued decision diagrams. Schulte C, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 340–355.Google Scholar
• Gentzel R, Michel L, van Hoeve WJ (2020) Haddock: A language and architecture for decision diagram compilation. Simonis H, ed. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 531–547.Google Scholar
• Gillard X, Coppé V, Schaus P, Cire AA (2021) Improving the filtering of branch-and-bound MDD solver. Stuckey PJ, ed. Proc. Internat. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (Springer, Berlin, Heidelberg), 231–247.Google Scholar
• González JE, Cire AA, Lodi A, Rousseau LM (2020) Integrated integer programming and decision diagram search tree with an application to the maximum independent set problem. Constraints 25(1-2):23–46.Crossref, Google Scholar
• González JE, Cire AA, Lodi A, Rousseau LM (2022) BDD-based optimization for the quadratic stable set problem. Discrete Optim., Forthcoming.Crossref, Google Scholar
• Guo C, Bodur M, Aleman DM, Urbach DR (2021) Logic-based Benders decomposition and binary decision diagram based approaches for stochastic distributed operating room scheduling. INFORMS J. Comput. 33(4):1551–1569.Abstract, Google Scholar
• Hadžić T, Hooker JN (2006) Postoptimality analysis for integer programming using binary decision diagrams. Technical report, Carnegie Mellon University, Pittsburgh, PA.Google Scholar
• Hadžić T, Hooker JN (2007) Cost-bounded binary decision diagrams for 0-1 programming. Van Hentenryck P, Wolsey L, eds. Proc. Internat. Conf. on Integration of AI and OR Techniques in Constraint Programming (Springer, Berlin, Heidelberg), 84–98.Google Scholar
• Hadžić T, Hooker JN, Tiedemann P (2008a) Propagating separable equalities in an MDD store. Perron L, Trick MA, eds. Proc. Internat. Conf. on Integration of AI and OR Techniques in Constraint Programming (Springer, Berlin, Heidelberg), 318–322.Google Scholar
• Hadžić T, Hooker JN, O’Sullivan B, Tiedemann P (2008b) Approximate compilation of constraints into multivalued decision diagrams. Stuckey PJ, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 448–462.Google Scholar
• Hadžić T, O’Mahony E, O’Sullivan B, Sellmann M (2009) Enhanced inference for the market split problem. Chung SM, Ziavras SG, eds. Proc. IEEE Internat. Conf. on Tools with Artificial Intelligence (IEEE, New York), 716–723.Google Scholar
• Hadžić T, Subbarayan S, Jensen RM, Andersen HR, Møller J, Hulgaard H (2004) Fast backtrack-free product configuration using a precompiled solution space representation. Proc. Internat. Conf. on Econom., Tech. and Organ. Aspects of Product Configuration Systems 131–138.Google Scholar
• Haus UU, Michini C (2017) Compact representations of all members of an independence system. Ann. Math. Artificial Intelligence 79(1-3):145–162.Crossref, Google Scholar
• Haus UU, Michini C, Laumanns M (2017) Scenario aggregation using binary decision diagrams for stochastic programs with endogenous uncertainty. Preprint, submitted January 17, https://arxiv.org/abs/1401.0212.Google Scholar
• Hoda S, Van Hoeve WJ, Hooker JN (2010) A systematic approach to MDD-based constraint programming. Cohen D, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 266–280.Google Scholar
• Hooker JN (2013) Decision diagrams and dynamic programming. Gomes C, Sellmann M, eds. Proc. Internat. Conf. on AI and OR Techniques in Constraint Programming for Combinatorial Optim. Problems (Springer, Berlin, Heidelberg), 94–110.Google Scholar
• Hooker JN (2017) Job sequencing bounds from decision diagrams. Beck JC, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 565–578.Google Scholar
• Hooker JN (2019) Improved job sequencing bounds from decision diagrams. Schiex T, de Givry S, eds. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 268–283.Google Scholar
• Horn M, Raidl GR (2019) Decision diagram based limited discrepancy search for a job sequencing problem. Moreno-Díaz R, Pichler F, Quesada-Arencibia A, eds. Computer Aided Systems Theory (Springer, Berlin, Heidelberg), 344–351.Google Scholar
• Horn M, Raidl GR (2021) A*-based compilation of relaxed decision diagrams for the longest common subsequence problem. Stuckey PJ, ed. Proc. Internat. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (Springer, Berlin, Heidelberg), 72–88.Google Scholar
• Horn M, Maschler J, Raidl GR, Rönnberg E (2021) A*-based construction of decision diagrams for a prize-collecting scheduling problem. Comput. Oper. Res. 126:105–125.Crossref, Google Scholar
• Hosseininasab A, van Hoeve WJ (2021) Exact multiple sequence alignment by synchronized decision diagrams. INFORMS J. Comput. 33(2):721–738.Abstract, Google Scholar
• Jung V, Régin JC (2021) Checking constraint satisfaction. Stuckey PJ, ed. Proc. Internat. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (Springer, Berlin, Heidelberg), 332–347.Google Scholar
• Karahalios A, van Hoeve WJ (2021) Variable ordering for decision diagrams: A portfolio approach. Technical report, Carnegie Mellon University, Pittsburgh, PA.Google Scholar
• Kell B, Van Hoeve WJ (2013) An MDD approach to multidimensional bin packing. Gomes C, Sellmann M, eds. Proc. Internat. Conf. on AI and OR Techniques in Constraint Programming for Combinatorial Optim. Problems (Springer, Berlin, Heidelberg), 128–143.Google Scholar
• Kell B, Sabharwal A, van Hoeve WJ (2015) BDD-guided clause generation. Michel L, ed. Proc. Integration of AI and OR Techniques in Constraint Programming (Springer, Berlin, Heidelberg), 215–230.Google Scholar
• Kinable J, Cire AA, van Hoeve WJ (2017) Hybrid optimization methods for time-dependent sequencing problems. Eur. J. Oper. Res. 259(3):887–897.Crossref, Google Scholar
• Kowalczyk D, Leus R (2018) A branch-and-price algorithm for parallel machine scheduling using ZDDs and generic branching. INFORMS J. Comput. 30(4):768–782.Link, Google Scholar
• Lange JH, Swoboda P (2021) Efficient message passing for 0–1 ILPs with binary decision diagrams. Meila M, Zhang T, eds. Proc. Internat. Conf. on Machine Learn. (PMLR), 6000–6010.Google Scholar
• Latour ALD, Babaki B, Nijssen S (2019) Stochastic constraint propagation for mining probabilistic networks. Kraus S, ed. Proc. Internat. Joint Conf. on Artificial Intelligence (International Joint Conferences on Artificial Intelligence, CA), 1137–1145.Google Scholar
• Latour AL, Babaki B, Dries A, Kimmig A, Van den Broeck G, Nijssen S (2017) Combining stochastic constraint optimization and probabilistic programming. Beck JC, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 495–511.Google Scholar
• Lozano L, Smith JC (2022) A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs. Math. Programming, 191(1):381–404.Crossref, Google Scholar
• Lozano L, Bergman D, Smith JC (2020a) On the consistent path problem. Oper. Res. 68(6):1913–1931.Link, Google Scholar
• Lozano L, Magazine MJ, Polak GG (2020b) Decision diagram-based integer programming for the paired job scheduling problem. IISE Trans. 53(6):671–684.Crossref, Google Scholar
• Mogali JK (2021) Heuristics for routing and scheduling of spatio-temporal type problems in industrial environments. PhD Thesis, Carnegie Mellon University, Pittsburgh.Google Scholar
• Martin RK (1987) Generating alternative mixed-integer programming models using variable redefinition. Oper. Res. 35(6):820–831.Link, Google Scholar
• Maschler J, Raidl GR (2018) Multivalued decision diagrams for a prize-collecting sequencing problem. Burke EK, Di Gaspero L, McCollum B, Musliu N, Ozcan E, eds. Proc. Internat. Conf. on the Practice and Theory of Automated Timetabling (International Conference of the Practice and Theory of Automated Timetabling, Vienna, Austria), 375–397.Google Scholar
• Mehrani S, Cardonha C, Bergman D (2021) Models and algorithms for the bin-packing problem with minimum color fragmentation. INFORMS J. Comput., ePub ahead of print December 17, https://doi.org/10.1287/ijoc.2021/1120.Link, Google Scholar
• Minato S (1993) Zero-suppressed BDDs for set manipulation in combinatorial problems. Preas BT, ed. Proc. Internat. Design Automation Conf. (IEEE, New York), 272–277.Google Scholar
• Morrison DR, Sewell EC, Jacobson SH (2016) Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams. INFORMS J. Comput. 28(1):67–82.Link, Google Scholar
• Nadarajah S, Cire AA (2020) Network-based approximate linear programming for discrete optimization. Oper. Res. 68(6):1767–1786.Link, Google Scholar
• Nishino M, Yasuda N, Minato S, Nagata M (2015) BDD-constrained search: A unified approach to constrained shortest path problems. Bonet B, Koenig S, eds. Proc. AAAI Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA), 1219–1225.Google Scholar
• O’Neil RJ, Hoffman K (2019) Decision diagrams for solving traveling salesman problems with pickup and delivery in real time. Oper. Res. Lett. 47(3):197–201.Crossref, Google Scholar
• Parjadis A, Cappart Q, Rousseau LM, Bergman D (2021) Improving branch-and-bound using decision diagrams and reinforcement learning. Stuckey PJ, ed. Proc. Internat. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (Springer, Berlin, Heidelberg), 446–455.Google Scholar
• Perez G, Régin JC (2014) Improving GAC-4 for table and MDD constraints. O’Sullivan B, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 606–621.Google Scholar
• Perez G, Régin JC (2015a) Efficient operations on MDDs for building constraint programming models. Yang Q, Wooldridge M, ed. Proc. Internat. Joint Conf. on Artificial Intelligence (International Joint Conference on Artificial Intelligence, CA).Google Scholar
• Perez G, Régin JC (2015b) Relations between MDDs and tuples and dynamic modifications of MDDs based constraints. Preprint, submitted May 11, https://arxiv.org/abs/1505.02552.Google Scholar
• Perez G, Régin JC (2016) Constructions and in-place operations for MDDs based constraints. Quimper C-G, ed. Proc. Internat. Conf. on AI and OR Techniques in Constraint Programming for Combinatorial Optim. Problems (Springer, Berlin, Heidelberg), 279–293.Google Scholar
• Perez G, Régin JC (2017a) MDDs are efficient modeling tools: An application to some statistical constraints. Salvagnin D, Lombardi M, eds. Proc. Internat. Conf. on AI and OR Techniques in Constraint Programming for Combinatorial Optim. Problems (Springer, Berlin, Heidelberg), 30–40.Google Scholar
• Perez G, Régin JC (2017b) MDDs: Sampling and probability constraints. Beck JC, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 226–242.Google Scholar
• Perez G, Régin JC (2017c) Soft and cost MDD propagators. Singh S, Markovitch S, eds. Proc. AAAI Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA), 3922–3928.Google Scholar
• Perez G, Régin JC (2018) Parallel algorithms for operations on multi-valued decision diagrams. McIlraith S, Weinberger K, eds. Proc. AAAI Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA), 6625–6632.Google Scholar
• Ploskas N, Laughman C, Raghunathan AU, Sahinidis NV (2019) Heat exchanger circuitry design by decision diagrams. Rousseau L-M, Stergiou K, eds. Proc. Internat. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (Springer, Berlin, Heidelberg), 461–471.Google Scholar
• Raghunathan AU, Bergman D, Hooker JN, Serra T, Kobori S (2018) Seamless multimodal transportation scheduling. Preprint, submitted July 25, https://arxiv.org/abs/1807.09676.Google Scholar
• Riascos-Álvarez LC, Bodur M, Aleman DM (2020) A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem. Preprint, submitted October 5, https://arxiv.org/abs/2009.13715.Google Scholar
• Römer M, Cire AA, Rousseau LM (2018) A local search framework for compiling relaxed decision diagrams. van Hoeve W-J, ed. Proc. Internat. Conf. on the Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (Springer, Berlin, Heidelberg), 512–520.Google Scholar
• Rossi F, Van Beek P, Walsh T (2006) Handbook of Constraint Programming, 1st ed. (Elsevier, New York).Google Scholar
• Roy P, Perez G, Régin JC, Papadopoulos A, Pachet F, Marchini M(2016) Enforcing structure on temporal sequences: The Allen constraint. Rueher M, ed. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin, Heidelberg), 786–801.Google Scholar
• Salemi H, Davarnia D (2021) On the Structure of Decision Diagram-Representable Mixed Integer Programs with Application to Unit Commitment (Optimization Online).Google Scholar
• Schiex T, Verfaillie G (1994) Nogood recording for static and dynamic constraint satisfaction problems. Internat. J. Artificial Intelligence Tools 3(02):187–207.Crossref, Google Scholar
• Serra T (2020) Enumerative branching with less repetition. Hebrard E, Musliu N, eds. Proc Integration Constraint Programming Artificial Intelligence Oper. Res. (Springer, Berlin, Heidelberg), 399–416.Google Scholar
• Serra T, Hooker J (2020) Compact representation of near-optimal integer programming solutions. Math. Programming 182(1):199–232.Crossref, Google Scholar
• Serra T, Raghunathan AU, Bergman D, Hooker JN, Kobori S (2019) Last-mile scheduling under uncertainty. Rousseau L-M, Stergiou K, eds. Proc. Internat. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (Springer, Berlin, Heidelberg), 519–528.Google Scholar
• Subbarayan S (2008) Efficient reasoning for nogoods in constraint solvers with BDDs. Hudak P, Warren DS, eds. Proc. Internat. Sympos. on Practical Aspects of Declarative Languages (Springer, Berlin, Heidelberg), 53–67.Google Scholar
• Suzuki H, Minato S (2018) Fast enumeration of all pareto-optimal solutions for 0-1 multi-objective knapsack problems using ZDDs. IEICE Trans. Fundamental Electron. Comm. Comput. Sci. 101(9):1375–1382.Crossref, Google Scholar
• Suzuki H, Ishihata M, Minato S (2018) Exact computation of strongly connected reliability by binary decision diagrams. Kim D, Uma RN, Zelikovsky A, eds. Internat. Conf. on Combinatorial Optim. and Applications (Springer, Berlin, Heidelberg), 281–295.Google Scholar
• Tjandraatmadja C, van Hoeve WJ (2019) Target cuts from relaxed decision diagrams. INFORMS J. Comput. 31(2):285–301.Link, Google Scholar
• Tjandraatmadja C, van Hoeve WJ (2020) Incorporating bounds from decision diagrams into integer programming. Math. Programming Comput. 13:225–256.Crossref, Google Scholar
• van den Bogaerdt P, de Weerdt M (2018) Multi-machine scheduling lower bounds using decision diagrams. Oper. Res. Lett. 46(6):616–621.Crossref, Google Scholar
• van Hoeve WJ (2020) Graph coloring lower bounds from decision diagrams. Bienstock D, Zambelli G, eds. Proc. Internat. Conf. on Integer Programming and Combinatorial Optim. (Springer, Berlin, Heidelberg), 405–418.Google Scholar
• van Hoeve WJ (2022) Graph coloring with decision diagrams. Math. Programming 192(1):631–674.Crossref, Google Scholar
• Verhaeghe H, Lecoutre C, Schaus P (2018) Compact-MDD: Efficiently filtering (s)MDD constraints with reversible sparse bit-sets. Lang J, ed. Proc. Internat. Joint Conf. on Artificial Intelligence (International Joint Conferences on Artificial Intelligence, CA), 1383–1389.Google Scholar
• Verhaeghe H, Lecoutre C, Schaus P (2019) Extending compact-diagram to basic smart multi-valued variable diagrams. Rousseau L-M, Stergiou K, eds. Proc. Internat. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (Springer, Berlin, Heidelberg), 581–598.Google Scholar
• Vion J, Piechowiak S (2018) From mdd to bdd and arc consistency. Constraints 23(4):451–480.Crossref, Google Scholar
• Wegener I (2000) Branching Programs and Binary Decision Diagrams: Theory and Applications, 1st ed. (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Wolsey LA, Nemhauser GL (1999) Integer and Combinatorial Optimization, 1st ed. (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Xue Y, van Hoeve WJ (2019) Embedding decision diagrams into generative adversarial networks. Rousseau L-M, Stergiou K, eds. Proc. Internat. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Oper. Res. (Springer, Berlin, Heidelberg), 616–632.Google Scholar