Structure Detection in Mixed-Integer Programs

References

• Achterberg T, Koch T, Martin A (2006) Miplib 2003. Oper. Res. Lett. 34(4):361–372.Crossref, Google Scholar
• Aykanat C, Pinar A, Çatalyürek ÜV (2004) Permuting sparse rectangular matrices into block-diagonal form. SIAM J. Sci. Comput. 25(6):1860–1879.Crossref, Google Scholar
• Bergner M, Caprara A, Ceselli A, Furini F, Lübbecke ME, Malaguti E, Traversi E (2015) Automatic Dantzig-Wolfe reformulation of mixed integer programs. Math. Programming 149(1–2):391–424.Crossref, Google Scholar
• Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J. Statist. Mech.: Theory and Experiment 2008(10):Article no. P10008.Crossref, Google Scholar
• Borndörfer R, Ferreira CE, Martin A (1998) Decomposing matrices into blocks. SIAM J. Optim. 9(1):236–269.Crossref, Google Scholar
• Brandes U, Delling D, Gaertler M, Gorke R, Hoefer M, Nikoloski Z, Wagner D (2008) On modularity clustering. IEEE Trans. Knowledge Data Engrg. 20(2):172–188.Crossref, Google Scholar
• Bui TN, Jones C (1992) Finding good approximate vertex and edge partitions is NP-hard. Inform. Processing Lett. 42(3):153–159.Crossref, Google Scholar
• Catalyurek UV, Aykanat C (1999) Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication. IEEE Trans. Parallel Distributed Systems 10(7):673–693.Crossref, Google Scholar
• Clauset A, Newman MEJ, Moore C (2004) Finding community structure in very large networks. Physical Rev. E 70(6):Article no. 066111.Crossref, Google Scholar
• Cordella LP, Foggia P, Sansone C, Vento M (2001) An improved algorithm for matching large graphs. Jolion JM, Kropatsch W, Vento M, eds. 3rd IAPR-TC15 Workshop Graph-Based Representations Pattern Recognition (C.U.E.N., Napoli, Italy), 149–159.Google Scholar
• Ferris MC, Horn JD (1998) Partitioning mathematical programs for parallel solution. Math. Programming 80(1):35–61.Crossref, Google Scholar
• Fortunato S (2010) Community detection in graphs. Phys. Rep. 486(3):75–174.Crossref, Google Scholar
• Gamrath G, Lübbecke ME (2010) Experiments with a generic Dantzig-Wolfe decomposition for integer programs. Experimental Algorithms (Springer, Berlin), 239–252.Crossref, Google Scholar
• Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12):7821–7826.Crossref, Google Scholar
• Good BH, de Montjoye Y-A, Clauset A (2010) Performance of modularity maximization in practical contexts. Physical Rev. E 81(4):Article no. 046106.Crossref, Google Scholar
• Hopcroft J, Tarjan R (1973) Algorithm 447: Efficient algorithms for graph manipulation. Comm. ACM 16(6):372–378.Crossref, Google Scholar
• Karypis G, Kumar V (1998a) hMETIS—Hypergraph & circuit partitioning. Accessed May 18, 2018, http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview.Google Scholar
• Karypis G, Kumar V (1998b) METIS—Serial graph partitioning and fill-reducing matrix ordering. Accessed May 18, 2018, http://glaros.dtc.umn.edu/gkhome/metis/metis/overview.Google Scholar
• Kernighan BW, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell System Tech. J. 49(2):291–307.Crossref, Google Scholar
• Koch T, Achterberg T, Andersen E, Bastert O, Berthold T, Bixby RE, Danna E, Gamrath G, Gleixner AM, Heinz Set al. (2011) MIPLIB 2010. Math. Programming Comput. 3(2):103–163.Crossref, Google Scholar
• Lancichinetti A, Fortunato S (2009) Community detection algorithms: A comparative analysis. Physical Rev. E 80(5):Article no. 056117.Crossref, Google Scholar
• Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Physical Rev. E 78(4):Article no. 046110.Crossref, Google Scholar
• Leskovec J, Lang KJ, Mahoney M (2010) Empirical comparison of algorithms for network community detection. Proc. 19th Internat. Conf. World Wide Web (ACM, New York), 631–640.Google Scholar
• Lyaudet L (2010) NP-hard and linear variants of hypergraph partitioning. Theoret. Comput. Sci. 411(1):10–21.Crossref, Google Scholar
• Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Physical Rev. E 69(2):Article no. 026113.Crossref, Google Scholar
• Pons P, Latapy M (2006) Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10(2):191–218.Crossref, Google Scholar
• Porter MA, Onnela J-P, Mucha PJ (2009) Communities in networks. Notices AMS 56(9):1082–1097.Google Scholar
• Puchinger J, Stuckey PJ, Wallace MG, Brand S (2011) Dantzig-Wolfe decomposition and branch-and-price solving in G12. Constraints 16(1):77–99.Crossref, Google Scholar
• Ralphs TK, Galati MV (2009) DIP–decomposition for integer programming. Accessed May 18, 2018, https://projects.coin-or.org/Dip.Google Scholar
• Ronhovde P, Nussinov Z (2009) Multiresolution community detection for megascale networks by information-based replica correlations. Physical Rev. E 80(1):Article no. 016109.Crossref, Google Scholar
• Rosvall M, Bergstrom CT (2007) An information-theoretic framework for resolving community structure in complex networks. Proc. Natl. Acad. Sci. 104(18):7327–7331.Crossref, Google Scholar
• Suresh Kumar C, Chandrasekharan MP (1990) Grouping efficacy: A quantitative criterion for goodness of block diagonal forms of binary matrices in group technology. Internat. J. Production Res. 28(2):233–243.Crossref, Google Scholar
• Vanderbeck F (2005) BaPCod–a generic branch-and-price code. Accessed May 18, 2018, https://realopt.bordeaux.inria.fr/.Google Scholar
• Vanderbeck F, Wolsey LA (2010) Reformulation and decomposition of integer programs. Jünger M, Liebling ThM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958–2008 (Springer, Berlin), 431–502.Crossref, Google Scholar
• Wang J, Ralphs TK (2013) Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization. Gomes C, Sellmann M, eds. CPAIOR (Springer, Berlin).Crossref, Google Scholar
• Weil RL, Kettler PC (1971) Rearranging matrices to block-angular form for decomposition (and other) algorithms. Management Sci. 18(1):98–108.Link, Google Scholar
• Witt JT, Lübbecke ME (2015) Dantzig-Wolfe reformulations for the stable set problem. Technical Report 2015–029, Operations Research, RWTH Aachen University, http://www.or.rwth-aachen.de/research/publications/2015-DW-stable.pdf.Google Scholar