Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams

References

• Akers SB (1978) Binary decision diagrams. IEEE Trans. Comput. 100:509–516.Crossref, Google Scholar
• Andersen HR (1997) An introduction to binary decision diagrams. Lecture notes for 49285 Advanced Algorithms E97, Department of Information Technology, Technical University of Denmark. Accessed January 15, 2016, www.itu.dk/courses/AVA/E2005/bdd-eap.pdf.Google Scholar
• Barnhart C, Hane CA, Vance PH (2000) Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper. Res. 48:318–326.Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46:316–329.Link, Google Scholar
• Behle M (2007) Binary decision diagrams and integer programming. Ph.D. thesis, Universistät des Saarlands, Saarbrucken, Germany.Google Scholar
• Behle M, Eisenbrand F (2007) 0/1 vertex and facet enumeration with BDDs. Applegate D, Brodal G, eds. Workshop on Algorithm Engineering and Experiments (ALENEX) (SIAM, Philadelphia), 158–165.Crossref, Google Scholar
• Bergman D, Cire A, Van Hoeve W, Hooker J (2012a) Optimization bounds from binary decision diagrams. Technical Report 1378, Tepper School of Business, Pittsburgh.Google Scholar
• Bergman D, Cire AA, Van Hoeve W, Hooker JN (2012b) 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 Contraint Programming for Combinatorial Optimzation Problems, Lecture Notes in Computer Science, Vol. 7298 (Springer, Berlin), 34–49.Crossref, Google Scholar
• Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization (Athena Scientific, Nashua, NH).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 R (1986) Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35:677–691.Crossref, Google Scholar
• Bryant RE (1992) Symbolic Boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surveys (CSUR) 24:293–318.Crossref, Google Scholar
• Cire A, Bergman D, Hooker JN, Hoeve WV (2012) A branch and bound algorithm based on approximate binary decision diagrams. Presentation, INFORMS Annual Meeting, Phoenix.Google Scholar
• Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8:101–111.Link, Google Scholar
• de Aragão MP, Uchoa E (2003) Integer program reformulation for robust branch-and-cut-and-price algorithms. Math. Program Rio: A Conf. Honour Nelson Maculan, 56–61.Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Aragão MPD, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106:491–511.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Freeman WH, ed. Computers and Intractability: A Guide to the Theory of NP-Completeness, First ed. (W. H. Freeman and Company, New York).Google Scholar
• Gualandi S, Malucelli F (2012) Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24:81–100.Link, Google Scholar
• Hadžić T, Hooker J (2008) Postoptimality analysis for integer programming using binary decision diagrams. Technical Report 167, Tepper School of Business, Pittsburgh.Google Scholar
• Harvey WD, Ginsberg ML (1995) Limited discrepancy search. Mellish CS, ed. Proc. 14th Internat. Joint Conf. Artificial Intelligence, Vol. 1 (Morgan Kaufmann, San Mateo, CA), 607–615.Google Scholar
• Held S, Cook W, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4:363–381.Crossref, Google Scholar
• Johnson DS, Trick MA (1996) Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Kao GK, Sewell EC, Jacobson SH (2009) A branch, bound, and remember algorithm for the 1|ri| ∑ti scheduling problem. J. Scheduling 12:163–175.Crossref, Google Scholar
• Knuth D (2008) Fun with zero-suppressed binary decision diagrams. Accessed January 15, 2016, http://myvideos.stanford.edu/player/slplayer.aspx?coll=ea60314a-53b3-4be2-8552-dcf190ca0c0b&co=af52aca1-9c60-4a7b-a10b-0e543f4f3451&o=true.Google Scholar
• Korf RE (1985) Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence 27:97–109.Crossref, Google Scholar
• Korf RE (1996) Improved limited discrepancy search. Shrobe H, Senator T, eds. Association for the Advancement of Artificial Intelligence/Innovative Applications of Artificial Intelligence, Vol. 1 (AAAI Press, Palo Alto, CA), 286–291.Google Scholar
• Lee C (1959) Representation of switching circuits by binary-decision programs. Bell System Tech. J. 38:985–999.Crossref, Google Scholar
• Maenhout B, Vanhoucke M (2010) Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem. J. Scheduling 13:77–93.Crossref, Google Scholar
• Malaguti E, Monaci M, Toth P (2008) A metaheuristic approach for the vertex coloring problem. INFORMS J. Comput. 20:302–316.Link, Google Scholar
• Malaguti E, Monaci M, Toth P (2011) An exact approach for the vertex coloring problem. Discrete Optim. 8:174–190.Crossref, Google Scholar
• Mehrotra A, Trick MA (1996) A column generation approach for graph coloring. INFORMS J. Comput. 8:344–354.Link, Google Scholar
• Méndez-Díaz I, Zabala P (2006) A branch-and-cut algorithm for graph coloring. Discrete Appl. Math. 154:826–847.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
• Morrison DR (2014) New methods for branch-and-bound algorithms. Ph.D. thesis, University of Illinois, Urbana–Champaign.Google Scholar
• Morrison DR, Sewell EC, Jacobson SH (2014b) An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset. Eur. J. Oper. Res. 236:403–409.Crossref, Google Scholar
• Morrison DR, Sewell EC, Jacobson SH (2014c) Characteristics of the maximal independent set ZDD. J. Combinatorial Optim. 28:121–139.Crossref, Google Scholar
• Morrison DR, Sauppe JJ, Sewell EC, Jacobson SH (2014a) A wide branching strategy for the graph coloring problem. INFORMS J. Comput. 26:704–717.Link, Google Scholar
• Pessoa A, de Aragao MP, Uchoa E (2008) Robust branch-cut-and-price algorithms for vehicle routing problems. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges (Springer, New York), 297–325.Crossref, Google Scholar
• Pisinger D, Sigurd M (2007) Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS J. Comput. 19:36–51.Link, Google Scholar
• Savelsbergh M (1997) A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45:831–841.Link, Google Scholar
• Sedgewick R, Wayne K (2011) Algorithms (Addison-Wesley Professional, Boston).Google Scholar
• Sewell EC, Sauppe JJ, Morrison DR, Jacobson SH, Kao G (2012) A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times. J. Global Optim. 54:791–812.Crossref, Google Scholar
• Trick MA (2005) Computational series: Graph coloring and its generalizations. Accessed January 15, 2016, http://mat.gsia.cmu.edu/COLOR02/.Google Scholar
• Uchoa E, Fukasawa R, Lysgaard J, Pessoa A, de Aragão MP, Andrade D (2008) Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. Math. Programming 112:443–472.Crossref, Google Scholar
• Vance PH (1998) Branch-and-price algorithms for the one-dimensional cutting stock problem. Comput. Optim. Appl. 9:211–228.Crossref, Google Scholar
• Vanderbeck F (2011) Branching in branch-and-price: A generic scheme. Math. Programming 130:249–294.Crossref, Google Scholar