What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO

References

• Ali S, Smith KA (2006) On learning algorithm selection for classification. Appl. Soft Comput. 6(2):119–138.Crossref, Google Scholar
• Barabási A-L, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512.Crossref, Google Scholar
• Barahona F (1996) Network design using cut inequalities. SIAM J. Optim. 6(3):823–837.Crossref, Google Scholar
• Barahona F, Grötschel M, Jünger M, Reinelt G (1988) An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3):493–513.Link, Google Scholar
• Barr RS, Golden BL, Kelly JP, Resende MGC, Stewart WR Jr (1995) Designing and reporting on computational experiments with heuristic methods. J. Heuristics 1(1):9–32.Crossref, Google Scholar
• Bartz-Beielstein T (2006) Experimental Research in Evolutionary Computation: The New Experimentalism (Springer-Verlag, Berlin).Google Scholar
• Beasley JE (1990) OR-Library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Boros E, Hammer PL, Tavares G (2016) Psuedo-boolean optimization web-project. Accessed July 4, 2018, http://rutcor.rutgers.edu/∼pbo/.Google Scholar
• Brazdil PB, Soares C, Da Costa JP (2003) Ranking learning algorithms: Using IBL and meta-learning on accuracy and time results. Machine Learn. 50(3):251–277.Crossref, Google Scholar
• Breiman L (2001) Random forests. Machine Learn. 45(1):5–32.Crossref, Google Scholar
• Breiman L, Friedman J, Olshen RA, Stone CJ (1994) Classification and Regression Trees (Chapman & Hall, New York).Google Scholar
• Burke E, Hyde M, Kendall G, Ochoa G, Özcan E, Woodward JR (2010) A classification of hyper-heuristic approaches. Gendreau M, Potvin J-Y, eds. Handbook of Metaheuristics (Springer, Boston), 449–468.Crossref, Google Scholar
• Cheeseman P, Kanefsky B, Taylor WM (1991) Where the really hard problems are. Proc. Twelfth Internat. Conf. Artificial Intelligence, Sydney, Australia, Vol. 91, 331–337.Google Scholar
• Corne DW, Reynolds AP (2010) Optimisation and generalisation: Footprints in instance space. Internat. Conf. Parallel Problem Solving from Nature (Springer, Berlin), 22–31.Google Scholar
• de Sousa S, Haxhimusa Y, Kropatsch WG (2013) Estimation of distribution algorithm for the Max-Cut problem. Kropatsch WG, Artner NM, Haxhimusa Y, Jiang X, eds. Graph-Based Representations in Pattern Recognition. Lecture Notes in Computer Science, Vol. 7877 (Springer, Berlin), 244–253.Crossref, Google Scholar
• Eiben AE, Jelasity M (2002) A critical note on experimental research in EC. Proc. 2002 Congress on Evolutionary Comput. (IEEE Press, Piscataway, NJ), 582–587.Google Scholar
• Foster JG, Foster DV, Grassberger P, Paczuski M (2010) Edge direction and the structure of networks. Proc. Natl. Acad. Sci. 107(24):10815–10820.Crossref, Google Scholar
• Gent IP, Walsh T (1996) The TSP phase transition. Artificial Intelligence 88(1):349–358.Crossref, Google Scholar
• Hammer PL (1965) Some network flow problems solved with pseudo-boolean programming. Oper. Res. 13(3):388–399.Link, Google Scholar
• Hartmann AK, Weigt M (2003) Statistical mechanics of the vertex-cover problem. J. Physics A: Math. General 36(43):11069–11094.Crossref, Google Scholar
• Hartmann AK, Weigt M (2006) Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Hill RR, Reilly CH (2000) The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance. Management Sci. 46(2):302–317.Link, Google Scholar
• Hooker JN (1995) Testing heuristics: We have it all wrong. J. Heuristics 1(1):33–42.Crossref, Google Scholar
• Horvitz E, Ruan Y, Gomes C, Kautz H, Selman B, Chickering M (2001) A Bayesian approach to tackling hard computational problems. Proc. Seventeenth Conf. Uncertainty in Artificial Intelligence (Morgan Kaufmann Publishers, Inc., San Francisco),235–244.Google Scholar
• Howe AE, Dahlman E, Hansen C, Scheetz M, Von Mayrhauser A (2000) Exploiting competitive planner performance. Recent Advances in AI Planning (Springer, Berlin), 62–72.Crossref, Google Scholar
• Insani N, Smith-Miles K, Baatar D (2013) Selecting suitable solution strategies for classes of graph coloring instances using data mining. Inform. Tech. Electrical Engrg. (ICITEE), 2013 Internat. Conf. (IEEE, Piscataway, NJ), 208–215.Google Scholar
• Johnson DS (2002) A theoretician’s guide to the experimental evaluation of algorithms. Goldwasser MH, Johnson DS, McGeoch CC, eds. Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges (American Mathematical Society, Providence, RI), 215–250.Crossref, Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, Bohlinger JD, eds. Complexity of Computer Computations. The IBM Research Symposia (Springer, New York), 85–103.Crossref, Google Scholar
• Kitchenham B, Brereton OP, Budgen D, Turner M, Bailey J, Linkman S (2009) Systematic literature reviews in software engineering—A systematic literature review. Inform. Software Tech. 51(1):7–15.Crossref, Google Scholar
• Krzkakała F, Pagnani A, Weigt M (2004) Threshold values, stability analysis, and high-q asymptotics for the coloring problem on random graphs. Phys. Rev. E 70(4):046705-1–046705-17.Google Scholar
• Leyton-Brown K, Nudelman E, Shoham Y (2002) Learning the empirical hardness of optimization problems: The case of combinatorial auctions. Internat. Conf. Principles Practice Constraint Programming (Springer, Berlin), 556–572.Google Scholar
• Leyton-Brown K, Nudelman E, Andrew G, McFadden J, Shoham Y (2003) A portfolio approach to algorithm selection. IJCAI, Vol. 1543.Google Scholar
• Liaw A, Wiener M (2002) Classification and regression by randomForest. R News 2(3):18–22. Accessed July 4, 2018, http://CRAN.R-project.org/doc/Rnews/.Google Scholar
• Martí R, Duarte A, Laguna M (2009) Advanced scatter search for the max-cut problem. INFORMS J. Comput. 21(1):26–38.Link, Google Scholar
• Martin D, Fowlkes C, Tal D, Malik J (2001) A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. Eighth IEEE Internat. Conf. Comput. Vision, Vancouver, BC, Canada, Vol. 2, 416–423.Google Scholar
• McGeoch CC (2012) A Guide to Experimental Algorithmics (Cambridge University Press, New York).Crossref, Google Scholar
• Merz P, Freisleben B (2002) Greedy and local search heuristics for unconstrained binary quadratic programming. J. Heuristics 8(2):197–213.Crossref, Google Scholar
• Newman MEJ, Strogatz SH, Watts DJ (2001) Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64(2):026118-1–026118-17.Crossref, Google Scholar
• Newman MEJ, Watts DJ, Strogatz SH (2002) Random graph models of social networks. Proc. Natl. Acad. Sci. 99(Suppl. 1):2566–2572.Crossref, Google Scholar
• Nikolić M, Marić F, Janičić P (2013) Simple algorithm portfolio for SAT. Artificial Intelligence Rev. 40(4):457–465.Crossref, Google Scholar
• O’Mahony E, Hebrard E, Holland A, Nugent C, O’Sullivan B (2008) Using case-based reasoning in an algorithm portfolio for constraint solving. 19th Irish Conf. Artificial Intelligence Cognitive Sci., Cork, Ireland, 210–216.Google Scholar
• Pulina L, Tacchella A (2009) A self-adaptive multi-engine solver for quantified boolean formulas. Constraints 14(1):80–116.Crossref, Google Scholar
• Rardin RL, Uzsoy R (2001) Experimental evaluation of heuristic optimization algorithms: A tutorial. J. Heuristics 7(3):261–304.Crossref, Google Scholar
• Rendl F, Rinaldi G, Wiegele A (2010) Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Programming 121(2):307–335.Crossref, Google Scholar
• Rice JR (1976) The algorithm selection problem. Adv. Comput. 15:65–118.Crossref, Google Scholar
• Silberholz J, Golden B (2010) Comparison of metaheuristics. Gendreau M, Potvin J-Y, eds. Handbook of Metaheuristics (Springer, Boston), 625–640.Crossref, Google Scholar
• Smith KA, Woo F, Ciesielski V, Ibrahim R (2001) Modelling the relationship between problem characteristics and data mining algorithm performance using neural networks. Dagli C, Akay E, Chen CLP, Fernandez BR, Ghosh JY, eds. Intelligent Engineering Systems Through Artificial Neural Networks (ASME Press, New York), 356–362.Google Scholar
• Smith-Miles K (2008) Towards insightful algorithm selection for optimization using meta-learning concepts. WCCI 2008: IEEE World Congress Comput. Intelligence (IEEE, Piscataway, NJ),4118–4124.Google Scholar
• Smith-Miles K, Lopes L (2011) Generalising algorithm performance in instance space: A timetabling case study. Internat. Conf. Learn. Intelligent Optim. (Springer, Berlin), 524–538.Google Scholar
• Smith-Miles K, Lopes L (2012) Measuring instance difficulty for combinatorial optimization problems. Comput. Oper. Res. 39(5):875–889.Crossref, Google Scholar
• Smith-Miles K, van Hemert J (2011) Discovering the suitability of optimisation algorithms by learning from evolved instances. Ann. Math. Artificial Intelligence 61(2):87–104.Crossref, Google Scholar
• Smith-Miles K, van Hemert J, Lim XY (2010) Understanding TSP difficulty by learning from evolved instances. Internat. Conf. Learn. Intelligent Optim. (Springer, Berlin), 266–280.Google Scholar
• Smith-Miles K, Baatar D, Wreford B, Lewis R (2014) Towards objective measures of algorithm performance across instance space. Comput. Oper. Res. 45:12–24.Crossref, Google Scholar
• Smith-Miles KA, James RJW, Giffin JW, Tu Y (2009) A knowledge discovery approach to understanding relationships between scheduling problem structure and heuristic performance. LION 3, Third Internat. Conf. Learning Intelligent Optim., Trento, Italy.Google Scholar
• Stadler PF, Schnabl W (1992) The landscape of the traveling salesman problem. Phys. Lett. A 161(4):337–344.Crossref, Google Scholar
• Stützle T, Fernandes S (2004) New benchmark instances for the QAP and the experimental analysis of algorithms. Eur. Conf. Evolutionary Comput. Combinatorial Optim. (Springer, Berlin),199–209.Google Scholar
• Therneau T, Atkinson B, Ripley B (2015) rpart: Recursive partitioning and regression trees. Accessed July 7, 2018, https://cran.r-project.org/web/packages/rpart/rpart.pdf.Google Scholar
• Vilalta R, Drissi Y (2002) A perspective view and survey of meta-learning. Artificial Intelligence Rev. 18(2):77–95.Crossref, Google Scholar
• Vollmann TE, Buffa ES (1966) The facilities layout problem in perspective. Management Sci. 12(10):B-450–B-468.Link, Google Scholar
• Wang Z, Zhang T, Zhang Y (2013) Distinguish hard instances of an np-hard problem using machine learning. Accessed July 7, 2018, http://cs229.stanford.edu/proj2013/WangZhangZhang-DistinguishHardInstancesOfAnNPHardProblem.pdf.Google Scholar
• Watts DJ, Strogatz SH (1998) Collective dynamics of “small-world” networks. Nature 393(6684):440–442.Crossref, Google Scholar
• Weigt M, Hartmann AK (2000) Number of guards needed by a museum: A phase transition in vertex covering of random graphs. Phys. Rev. Lett. 84(26):6118–6121.Crossref, Google Scholar
• Xu L, Hutter F, Hoos HH, Leyton-Brown K (2008) SATzilla: Portfolio-based algorithm selection for SAT. J. Artificial Intelligence Res. 32(1):565–606.Crossref, Google Scholar