Help
Cart
Skip main navigation

Available Issues

April 12, 2013 - April 13, 2026

Available Issues

April 12, 2013 - April 13, 2026

Discrete Optimization with Decision Diagrams

Published Online:21 Jan 2016https://doi.org/10.1287/ijoc.2015.0648

References

  • Akers SB (1978) Binary decision diagrams. IEEE Trans. Comput. C-27:509–516.Crossref, Google Scholar
  • Andersen HR, Hadžić T, Hooker JN, Tiedemann P (2007) A con-straint store based on multivalued decision diagrams. Bessière C, ed. Principles Practice Constraint Programming (CP 2007), Lecture Notes in Computer Science, Vol. 4741 (Springer, Berlin), 118–132.Crossref, Google Scholar
  • Baker KR, Keller B (2010) Solving the single-machine sequencing problem using integer programming. Comput. Indust. Engrg. 59:730–735.Crossref, Google Scholar
  • Balasundaram B, Butenko S, Hicks IV (2011) Clique relaxations in social network analysis: The maximum k-plex problem. Oper. Res. 59:133–142.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:356–371.Link, Google Scholar
  • Becker B, Behle M, Eisenbrand F, Wimmer R (2005) BDDs in a branch and cut framework. Nikoletseas S, ed. Proc. 4th Internat. Workshop Efficient Experiment. Algorithms (WEA 05), Lecture Notes in Computer Science, Vol. 3503 (Springer, Berlin), 452–463.Crossref, Google Scholar
  • Behle M, Eisenbrand F (2007) 0/1 vertex and facet enumeration with BDDs. Applegate D, Brodal GS, eds. Proc. Workshop Algorithm Engrg. Experiments (ALENEX) (SIAM, Philadelphia),158–165.Crossref, Google Scholar
  • Bergman D, van Hoeve W-J, Hooker JN (2011) Manipulating MDD relaxations for combinatorial optimization. Achterberg T, Beck JC, eds. Proc. Integration AI OR Techniques Constraint Programming Combinatorial Optim. Problems (CPAIOR 2011), Lecture Notes in Computer Science, Vol. 6697 (Springer-Verlag, Berlin), 20–35.Crossref, Google Scholar
  • Bergman D, Cire AA, van Hoeve W-J, Hooker JN (2012) Variable ordering for the application of BDDs to the maximum independent set problem. Beldiceanu N, Jussien N, Pinson E, eds. Proc. Integration AI OR Techniques Constraint Programming Combinatorial Optim. Problems (CPAIOR 2012), Lecture Notes in Computer Science, Vol. 7298 (Springer-Verlag, Berlin), 34–49.Crossref, Google Scholar
  • Bergman D, Cire AA, van Hoeve W-J, Hooker JN (2014a) Optimization bounds from binary decision diagrams. INFORMS J. Comput. 26:253–268.Link, Google Scholar
  • Bergman D, Cire AA, van Hoeve W-J, Yunes T (2014b) BDD-based heuristics for binary optimization. J. Heuristics 20:211–234.Crossref, Google Scholar
  • Bryant RE (1986) Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35:677–691.Crossref, Google Scholar
  • Caprara A, Letchford AN, Salazar-González J-J (2011) Decorous lower bounds for minimum linear arrangement. INFORMS J. Comput. 23:26–40.Link, Google Scholar
  • Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9:375–382.Crossref, Google Scholar
  • Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11:145–164.Crossref, Google Scholar
  • Cire AA, van Hoeve W-J (2013) Multivalued decision diagrams for sequencing problems. Oper. Res. 61:1411–1428.Link, Google Scholar
  • Eblen JD, Phillips CA, Rogers GL, Langston MA (2011) The maximum clique enumeration problem: Algorithms, applications and implementations. Chen J, Wang J, Zelikovsky A, eds. Proc. 7th Internat. Conf. Bioinformatics Res. Appl. ISBRA’11 (Springer-Verlag, Berlin), 306–319.Crossref, Google Scholar
  • Edachery J, Sen A, Brandenburg FJ (1999) Graph clustering using distance-k cliques. Kratochvil J, ed. Proc. Graph Drawing, Lecture Notes in Computer Science, Vol. 1731 (Springer-Verlag, Berlin), 98–106.Crossref, Google Scholar
  • Festa P, Pardalos PM, Resende MGC, Ribeiro CC (2002) Randomized heuristics for the max-cut problem. Optim. Methods Software 7:1033–1058.Crossref, Google Scholar
  • Fischetti M, Salvagnin D (2010) Pruning moves. INFORMS J. Comput. 22:108–119.Link, Google Scholar
  • Hadžić T, Hooker JN (2006) Postoptimality analysis for integer programming using binary decision diagrams. Technical report, Carnegie Mellon University, Pittsburgh.Google Scholar
  • Hadžić T, Hooker JN (2007) Cost-bounded binary decision diagrams for 0–1 programming. Loute E, Wolsey L, eds. Proc. Integration AI OR Techniques Constraint Programming Combinatorial Optim. Problems (CPAIOR 2007), Lecture Notes in Computer Science, Vol. 4510 (Springer, Berlin), 84–98.Crossref, Google Scholar
  • Hadžić T, Hooker JN, Tiedemann P (2008a) Propagating separable equalities in an MDD store. Perron L, Trick MA, eds. Proc. Integration AI OR Techniques Constraint Programming Combinatorial Optim. Problems (CPAIOR 2008), Lecture Notes in Computer Science, Vol. 5015 (Springer, Berlin), 318–322.Crossref, 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. Principles Practice Constraint Programming (CP 2008), Lecture Notes in Computer Science, Vol. 5202 (Springer, Berlin), 448–462.Crossref, Google Scholar
  • Hager WW, Krylyuk Y (1999) Graph partitioning and continuous quadratic programming. SIAM J. Discrete Math. 12:500–523.Crossref, Google Scholar
  • Helmberg C, Rendl F (2000) A spectral bundle method for semidefinite programming. SIAM J. Optim. 10:673–696.Crossref, Google Scholar
  • Hoda S, van Hoeve W-J, Hooker JN (2010) A systematic approach to MDD-based constraint programming. Cohen D, ed. Proc. 16th Internat. Conf. Principles Practices Constraint Programming, Lecture Notes in Computer Science, Vol. 6308 (Springer-Verlag, Berlin), 266–280.Crossref, Google Scholar
  • Hooker JN (2006) Discrete global optimization with binary decision diagrams. GICOLAG 2006 (ESI, Vienna).Google Scholar
  • Hooker JN (2013) Decision diagrams and dynamic programming. Gomes C, Sellman M, eds. Proc. Integration AI OR Techniques Constraint Programming Combinatorial Optim. Problems (CPAIOR 2013), Lecture Notes in Computer Science, Vol.7874 (Springer, Berlin), 94–110.Crossref, Google Scholar
  • Hu AJ (1995) Techniques for efficient formal verification using binary decision diagrams. Technical report no. TR-95-1561, Stanford University, Stanford, CA.Google Scholar
  • Ibaraki T (1977) The power of dominance relations in branch-and-bound algorithms. J. ACM 24:264–279.Crossref, Google Scholar
  • Kam T, Villa T, Brayton RK, Sangiovanni-Vincentelli AL (1998) Multi-valued decision diagrams: Theory and applications. Internat. J. Multiple-Valued Logic 4:9–62.Google Scholar
  • Kell B, van Hoeve W-J (2013) An MDD approach to multidimensional bin packing. Gomes C, Sellman M, eds. Proc. Integration AI OR Techniques Constraint Programming Combinatorial Optim. Problems (CPAIOR 2013), Lecture Notes in Computer Science, Vol. 7874 (Springer, Berlin), 128–143.Crossref, Google Scholar
  • Krislock N, Malick J, Roupin F (2014) Improved semidefinite bounding procedure for solving max-cut problems to optimality. Math. Programming 143:61–86.Crossref, Google Scholar
  • Lee CY (1959) Representation of switching circuits by binary-decision programs. Bell Systems Tech. J. 38:985–999.Crossref, Google Scholar
  • Loekito E, Bailey J, Pei J (2010) A binary decision diagram based approach for mining frequent subsequences. Knowledge Inform. Systems 24:235–268.Crossref, Google Scholar
  • Minato S (1993) Zero-suppressed BDDs for set manipulation in combinatorial problems. Dunlop AE, ed. 30th Conf. Design Automation (ACM, New York), 272–277.Crossref, Google Scholar
  • Mingozzi A (2002) State space relaxation and search strategies in dynamic programming. Koenig S, Holte RC, eds. Proc. Abstraction, Reformulation, Approximation, Lecture Notes in Computer Science, Vol. 2371 (Springer, Berlin), 51.Crossref, Google Scholar
  • Morgado A, Heras F, Liffiton M, Planes J, Marques-Silva J (2013) Iterative and core-guided maxsat solving: A survey and assessment. Constraints 18:478–534.Crossref, Google Scholar
  • Östergärd PRJ (2002) A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120:197–207.Crossref, Google Scholar
  • Rendl F, Rinaldi G, Wiegele A (2010) Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Programming 121:307–335.Crossref, Google Scholar
  • Righini G, Salani M (2008) New dynamic programming algorithms for the resource constrained shortest path problem. Networks 51:155–170.Crossref, Google Scholar
  • Sanner S, McAllester D (2005) Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference. Giunchiglia G, Kaelbling LP, eds. Proc. 19th Internat. Joint Conf. Artificial Intelligence (IJCAI 2005) (Morgan Kaufmann Publishers, San Francisco), 1384–1390.Google Scholar
  • Shylo VP, Shylo OV, Roschyn V (2012) Solving weighted max-cut problem by global equilibrium search. Cybernetics Systems Anal. 48:563–567.Crossref, Google Scholar
  • Tomita E, Kameda T (2007) An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Global Optim. 37:95–111.Crossref, Google Scholar
  • Wegener I (2000) Branching Programs and Binary Decision Diagrams: Theory and Applications. Discrete Mathematics and Applications (SIAM, Philadelphia).Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree