Optimization Bounds from Binary Decision Diagrams

References

• Akers SB (1978) Binary decision diagrams. IEEE Trans. Comput. C-27:509–516.Crossref, Google Scholar
• Andersen HR, Hadzic T, Hooker JN, Tiedemann P (2007) A constraint store based on multivalued decision diagrams. Bessière C, ed. Principles and Practice of Constraint Programming, CP, Lecture Notes in Computer Science, Vol. 4741 (Springer, Berlin), 118–132.Crossref, Google Scholar
• Becker B, Behle M, Eisenbrand F, Wimmer R (2005) BDDs in a branch and cut framework. Nikoletseas S, ed. Experiment. Efficient Algorithms, 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. Proc. Workshop Algorithm Engrg. Experiment. (ALENEX), New Orleans, 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. CPAIOR, Lecture Notes in Computer Science, Vol. 6697 (Springer, 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. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR (Springer, Berlin), 34–49.Crossref, Google Scholar
• Bollig B, Wegener I (1996) Improving the variable ordering of OBDDs is NP-complete. IEEE Trans. Comput. 45:993–1002.Crossref, Google Scholar
• Bryant RE (1986) Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35:677–691.Crossref, Google Scholar
• Ebendt R, Gunther W, Drechsler R (2003) An improved branch and bound algorithm for exact BDD minimization. IEEE Trans. CAD Integrated Circuits Systems 22:1657–1663.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimization, Vol. 2 (Springer, Berlin).Crossref, Google Scholar
• Hadzic T, Hooker JN (2006) Postoptimality analysis for integer programming using binary decision diagrams, presented at GICOLAG workshop (Global Optimization: Integrating Convexity, Optimization, Logic Programming, and Computational Algebraic Geometry), Vienna. Technical report, Carnegie Mellon University, Pittsburgh.Google Scholar
• Hadzic T, Hooker JN (2007) Cost-bounded binary decision diagrams for 0-1 programming. Loute E, Wolsey L, eds. Proc. Internat. Workshop Integration Artificial Intelligence Oper. Res. Techniques Constraint Programming Combin. Optim. Problems (CPAIOR 2007), Lecture Notes in Computer Science, Vol. 4510 (Springer, Berlin), 84–98.Crossref, Google Scholar
• Hadzic T, Hooker JN, O'Sullivan B, Tiedemann P (2008) Approximate compilation of constraints into multivalued decision diagrams. Stuckey PJ, ed. Principles and Practice of Constraint Programming, CP, Lecture Notes in Computer Science, Vol. 5202 (Springer, Berlin), 448–462.Crossref, Google Scholar
• Hoda S, van Hoeve W-J, Hooker JN (2010) A systematic approach to MDD-based constraint programming. Lodi A, Milano M, Toth P, eds. Proc. 16th Internat. Conf. Principles and Practices of Constraint Programming, Lecture Notes in Computer Science, Vol. 6308 (Springer, Berlin), 266–280.Crossref, Google Scholar
• Hooker JN (2013) Decision diagrams and dynamic programming. Gomes C, Sellmann M, eds. CPAIOR 2013 Proc. (Springer-Verlag, Berlin/Heidelberg), 94–110.Crossref, Google Scholar
• Hu AJ (1995) Techniques for efficient formal verification using binary decision diagrams. Thesis CS-TR-95-1561, Stanford University, Department of Computer Science, Stanford, CA.Google Scholar
• Jordan C (1869) Sur les assemblages de lignes. J. Reine Angew Math 70:185–190.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. 30th Conf. Design Automation (ACM, New York), 272–277.Crossref, Google Scholar
• Rebennack S, Reinelt G, Pardalos P (2012) A tutorial on branch and cut algorithms for the maximum stable set problem. Internat. Trans. Oper. Res. 19:161–199.Crossref, Google Scholar
• Rebennack S, Oswald M, Theis D, Seitz H, Reinelt G, Pardalos P (2011) A branch and cut solver for the maximum stable set problem. J. Combin. Optim. 21:434–457.Crossref, Google Scholar
• Rossi F, Smriglio S (2001) A branch-and-cut algorithm for the maximum cardinality stable set problem. Oper. Res. Lett. 28:63–74.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. 111:95–111.Google Scholar
• Wegener I (2000) Branching Programs and Binary Decision Diagrams: Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar