The Cunningham-Geelen Method in Practice: Branch-Decompositions and Integer Programming

References

• Aardal K, Bixby RE, Hurkens CAJ, Lenstra AK, Smeltink JW (1999) Market split and basis reduction: Towards a solution of the Cornuéjols-Dawande instances. Cornuéjols G, Burkard R, Woeginger G, eds. Integer Programming and Combinatorial Optimization, Lecture Notes Computer Science, Vol. 1610 (Springer, Berlin), 1–16.Crossref, Google Scholar
• Arnborg S, Lagergren J, Seese D (1991) Easy problems for tree-decomposable graphs. J. Algorithms 12(2):308–340.Crossref, Google Scholar
• Bixby R, Gu Z, Rothberg E (2010) Gurobi optimization. Accessed April 2011, http://gurobi.com.Google Scholar
• Cook W, Seymour P (1994) An algorithm for the ring-routing problem. Technical report, Bellcore Technical Memorandum.Google Scholar
• Cook W, Seymour P (2003) Tour merging via branch-decomposition. INFORMS J. Comput. 15(3):233–248.Link, Google Scholar
• Courcelle B (1990) The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. Comput. 85(1):12–75.Crossref, Google Scholar
• Cummingham WH, Geelen J (2007) On integer programming and the branch-width of the constraint matrix. Fischetti M, Williamson D, eds. Integer Programming and Combinatorial Optimation. Lecture Notes Computer Science, Vol. 4513 (Springer, Berlin), 158–166.Crossref, Google Scholar
• Golub G, Van Loan C (1996) Matrix Computations, 3rd ed. (Johns Hopkins University Press, Baltimore).Google Scholar
• Hicks IV (2004) Branch decompositions and minor containment. Networks 43(1):1–9.Crossref, Google Scholar
• Hicks IV (2005) Graphs, branchwidth, and tangles! Oh my! Networks 45(2):55–60.Crossref, Google Scholar
• Hicks IV, McMurray N (2007) The branchwidth of graphs and their cycle matroids. J. Combin. Theory Ser. B 97(5):681–692.Crossref, Google Scholar
• Ma J, Margulies S, Hicks IV, Goins E (2013) Branch-decomposition heuristics for linear matroids. Discrete Optim. 10(2):102–119.Crossref, Google Scholar
• Mittelmann H (2012) Mixed integer linear programming benchmark (parallel codes). Accessed April 2012, http://plato.asu.edu/ftp/milpc.html.Google Scholar
• Mizuno K, Nishihara S (2008) Constructive generation of very hard 3-colorability instances. Discrete Appl. Math. 156(2):218–229.Crossref, Google Scholar
• Pataki G, Krishnamoorthy B (2009) Column basis reduction and decomposable knapsack problems. Discrete Optim. 6(3):242–270.Crossref, Google Scholar
• Pataki G, Tural M, Wong EB (2010) Basis reduction and the complexity of branch-and-bound. SODA '10 Proc. Twenty-First Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1254–1261.Crossref, Google Scholar
• Seymour PD, Thomas R (1994) Call routing and the ratcatcher. Combinatorica 14(2):217–241.Crossref, Google Scholar