BDD-based heuristics for binary optimization

• Aarts, E., Lenstra, J.K.: Local Search in Combinatorial Optimization. Wiley, New York (1997)

  MATH  Google Scholar 

• Akers, S.B.: Binary decision diagrams. IEEE Trans. Comput. C–27, 509–516 (1978)

  Article  Google Scholar 

• Andersen, H.R., Hadzic, T., Hooker, J.N., Tiedemann, P.: A constraint store based on multivalued decision diagrams. In: Bessière, C. (ed.) Principles and Practice of Constraint Programming (CP 2007). Lecture Notes in Computer Science, vol. 4741, pp 118–132. Springer, New York (2007)

• Becker, B., Behle, M., Eisenbrand, F., Wimmer, R.: BDDs in a branch and cut framework. In: Nikoletseas, S. (ed.) Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA 05). Lecture Notes in Computer Science, vol. 3503, pp 452–463. Springer, New York (2005)

• Behle, M., Eisenbrand, F.: 0/1 vertex and facet enumeration with BDDs. In: Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), pp 158–165. SIAM, Philadelphia (2007)

• Bergman, D., van Hoeve, W.J., Hooker, J.N.: Manipulating MDD relaxations for combinatorial optimization. In: Achterberg, T., Beck, J. (eds.) CPAIOR. Lecture Notes in Computer Science, vol. 6697, pp 20–35. Springer, New York (2011)

• Bergman, D., Cire, A.A., van Hoeve, W.J., Hooker, J.N.: Variable ordering for the application of BDDs to the maximum independent set problem. In: Beldiceanu, N., Jussien, N., Pinson, E. (eds.) 9th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR’12). Lectures Notes in Computer Science, vol. 7298, pp 34–49. Springer, Nantes (2012)

• Berthold, T.: Primal heuristics for mixed integer programs. Master’s thesis, Zuze Institute, Berlin (2006)

• Bertsimas, D., Iancu, D.A., Katz, D.: A new local search algorithm for binary optimization. INFORMS J. Comput. 25(2), 208–221 (2013)

  Article  MathSciNet  Google Scholar 

• Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C–35, 677–691 (1986)

  Article  Google Scholar 

• Caprara, A., Fischetti, M., Toth, P.: Algorithms for the set covering problem. Ann. Oper. Res. 98, 2000 (1998)

  MathSciNet  Google Scholar 

• Corso, G.M.D., Manzini, G.: Finding exact solutions to the bandwidth minimization problem. Computing 62(3), 189–203 (1999)

  Article  MATH  MathSciNet  Google Scholar 

• Eckstein, J., Nediak, M.: Pivot, cut, and dive: a heuristic for 0–1 mixed integer programming. J. Heuristics 13(5), 471–503 (2007)

  Article  Google Scholar 

• Feige, U.: Approximating the bandwidth via volume respecting embeddings. J. Comput. Syst. Sci. 60(3), 510–539 (2000)

  Article  MATH  MathSciNet  Google Scholar 

• Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program 104(1), 91–104 (2005)

  Article  MATH  MathSciNet  Google Scholar 

• Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15, 835–855 (1965)

  Article  MATH  MathSciNet  Google Scholar 

• Glover, F., Laguna, M.: General purpose heuristics for integer programming—part I. J. Heuristics 2(4), 343–358 (1997a)

  Article  MATH  Google Scholar 

• Glover, F., Laguna, M.: General purpose heuristics for integer programming—part II. J. Heuristics 3(2), 161–179 (1997b)

  Article  MATH  Google Scholar 

• Grosso, A., Locatelli, M., Pullan, W.: Simple ingredients leading to very efficient heuristics for the maximum clique problem. J. Heuristics 14(6), 587–612 (2008)

  Article  Google Scholar 

• Gurari, E.M., Sudborough, I.H.: Improved dynamic programming algorithms for bandwidth minimization and the mincut linear arrangement problem. J. Algorithms 5, 531–546 (1984)

  Article  MATH  MathSciNet  Google Scholar 

• Hadzic, T., Hooker, J.N.: Postoptimality analysis for integer programming using binary decision diagrams. In: Presented at GICOLAG Workshop (Global Optimization: Integrating Convexity, Optimization, Logic Programming, and Computational Algebraic Geometry). Technical Report. Carnegie Mellon University, Vienna (2006)

• Hadzic, T., Hooker, J.N.: Cost-bounded binary decision diagrams for 0–1 programming. In: Loute, E., Wolsey, L. (eds.) Proceedings of the International Workshop on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2007). Lecture Notes in Computer Science, vol. 4510, pp 84–98. Springer, New York (2007)

• Hadzic, T., Hooker, J.N., O’Sullivan, B., Tiedemann, P.: Approximate compilation of constraints into multivalued decision diagrams. In: Stuckey, P.J. (ed.) Principles and Practice of Constraint Programming (CP 2008). Lecture Notes in Computer Science, vol. 5202, pp 448–462. Springer, New York (2008)

• Hoda, S., Hoeve, W.J., Hooker, J.N.: A systematic approach to MDD-based constraint programming. In: Proceedings of the 16th International Conference on Principles and Practices of Constraint Programming. Lecture Notes in Computer Science, vol. 6308, pp 266–280. Springer, New York (2010)

• Hu, A.J.: Techniques for efficient formal verification using binary decision diagrams. Thesis CS-TR-95-1561, Department of Computer Science, Stanford University (1995)

• Lee, C.Y.: Representation of switching circuits by binary-decision programs. Bell Syst. Tech. J. 38, 985–999 (1959)

  Article  Google Scholar 

• Martí, R., Laguna, M., Glover, F., Campos, V.: Reducing the bandwidth of a sparse matrix with tabu search. Eur. J. Oper. Res. 135(2), 450–459 (2001)

  Article  MATH  Google Scholar 

• Martí, R., Campos, V., Piñana, E.: A branch and bound algorithm for the matrix bandwidth minimization. Eur. J. Oper. Res. 186(2), 513–528 (2008)

  Article  MATH  Google Scholar 

• Piñana, E., Plana, I., Campos, V., Martí, R.: GRASP and path relinking for the matrix bandwidth minimization. Eur. J. Oper. Res. 153(1), 200–210 (2004)

  Article  MATH  Google Scholar 

• Pullan, W., Mascia, F., Brunato, M.: Cooperating local search for the maximum clique problem. J. Heuristics 17(2), 181–199 (2011)

  Article  Google Scholar 

• Saxe, J.: Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Algebraic Discrete Methods 1, 363–369 (1980)

  Article  MATH  MathSciNet  Google Scholar 

• Wegener, I.: Branching programs and binary decision diagrams: theory and applications. In: SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2000)

Download references