What works best when? A systematic evaluation of heuristics for max-cut and QUBO. (English) Zbl 1528.90288
Summary: Though empirical testing is broadly used to evaluate heuristics, there are shortcomings with how it is often applied in practice. In a systematic review of Max-Cut and quadratic unconstrained binary optimization (QUBO) heuristics papers, we found only 4% publish source code, only 14% compare heuristics with identical termination criteria, and most experiments are performed with an artificial, homogeneous set of problem instances. To address these limitations, we implement and release as open-source a code-base of 10 Max-Cut and 27 QUBO heuristics. We perform heuristic evaluation using cloud computing on a library of 3,296 instances. This large-scale evaluation provides insight into the types of problem instances for which each heuristic performs well or poorly. Because no single heuristic outperforms all others across all problem instances, we use machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners.
The online supplement is available at https://doi.org/10.1287/ijoc.2017.0798.
The online supplement is available at https://doi.org/10.1287/ijoc.2017.0798.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90-04 | Software, source code, etc. for problems pertaining to operations research and mathematical programming |
Keywords:
computational testing; reproducible research; heuristics; quadratic unconstrained binary optimization; max-cut; hyper-heuristics; test bed; interpretable machine learningReferences:
| [1] | Ali S, Smith KA (2006) On learning algorithm selection for classification. Appl. Soft Comput. 6(2):119-138.Crossref, Google Scholar · doi:10.1016/j.asoc.2004.12.002 |
| [2] | Barabási A-L, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509-512.Crossref, Google Scholar · Zbl 1226.05223 · doi:10.1126/science.286.5439.509 |
| [3] | Barahona F (1996) Network design using cut inequalities. SIAM J. Optim. 6(3):823-837.Crossref, Google Scholar · Zbl 0856.90112 · doi:10.1137/S1052623494279134 |
| [4] | 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 · Zbl 0646.90084 |
| [5] | 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 · Zbl 0853.68154 · doi:10.1007/BF02430363 |
| [6] | Bartz-Beielstein T (2006) Experimental Research in Evolutionary Computation: The New Experimentalism (Springer-Verlag, Berlin).Google Scholar · Zbl 1106.68037 |
| [7] | Beasley JE (1990) OR-Library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069-1072.Crossref, Google Scholar · doi:10.1057/jors.1990.166 |
| [8] | Boros E, Hammer PL, Tavares G (2016) Psuedo-boolean optimization web-project. Accessed July 4, 2018, http://rutcor.rutgers.edu/∼pbo/.Google Scholar |
| [9] | 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 · Zbl 1033.68082 · doi:10.1023/A:1021713901879 |
| [10] | Breiman L (2001) Random forests. Machine Learn. 45(1):5-32.Crossref, Google Scholar · Zbl 1007.68152 · doi:10.1023/A:1010933404324 |
| [11] | Breiman L, Friedman J, Olshen RA, Stone CJ (1994) Classification and Regression Trees (Chapman & Hall, New York).Google Scholar |
| [12] | 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 · doi:10.1007/978-1-4419-1665-5_15 |
| [13] | 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 · Zbl 0747.68064 |
| [14] | 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 |
| [15] | 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 · Zbl 1382.68235 · doi:10.1007/978-3-642-38221-5_26 |
| [16] | 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 |
| [17] | 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 · doi:10.1073/pnas.0912671107 |
| [18] | Gent IP, Walsh T (1996) The TSP phase transition. Artificial Intelligence 88(1):349-358.Crossref, Google Scholar · Zbl 0907.68177 · doi:10.1016/S0004-3702(96)00030-6 |
| [19] | Hammer PL (1965) Some network flow problems solved with pseudo-boolean programming. Oper. Res. 13(3):388-399.Link, Google Scholar · Zbl 0132.13804 |
| [20] | Hartmann AK, Weigt M (2003) Statistical mechanics of the vertex-cover problem. J. Physics A: Math. General 36(43):11069-11094.Crossref, Google Scholar · Zbl 1077.68073 · doi:10.1088/0305-4470/36/43/028 |
| [21] | Hartmann AK, Weigt M (2006) Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics (John Wiley & Sons, Hoboken, NJ).Google Scholar |
| [22] | 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 · Zbl 1231.90323 |
| [23] | Hooker JN (1995) Testing heuristics: We have it all wrong. J. Heuristics 1(1):33-42.Crossref, Google Scholar · Zbl 0853.68155 · doi:10.1007/BF02430364 |
| [24] | 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 |
| [25] | 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 · doi:10.1007/10720246_5 |
| [26] | 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 |
| [27] | 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 · Zbl 1103.68997 · doi:10.1090/dimacs/059/11 |
| [28] | 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 · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9 |
| [29] | 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 · doi:10.1016/j.infsof.2008.09.009 |
| [30] | 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 |
| [31] | 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 |
| [32] | Leyton-Brown K, Nudelman E, Andrew G, McFadden J, Shoham Y (2003) A portfolio approach to algorithm selection. IJCAI, Vol. 1543.Google Scholar |
| [33] | 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 |
| [34] | 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 · Zbl 1243.90227 |
| [35] | 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 |
| [36] | McGeoch CC (2012) A Guide to Experimental Algorithmics (Cambridge University Press, New York).Google Scholar |
| [37] | Merz P, Freisleben B (2002) Greedy and local search heuristics for unconstrained binary quadratic programming. J. Heuristics 8(2):197-213.Crossref, Google Scholar · Zbl 1013.90100 · doi:10.1023/A:1017912624016 |
| [38] | 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 · doi:10.1103/PhysRevE.64.026118 |
| [39] | 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 · Zbl 1114.91362 · doi:10.1073/pnas.012582999 |
| [40] | Nikolić M, Marić F, Janičić P (2013) Simple algorithm portfolio for SAT. Artificial Intelligence Rev. 40(4):457-465.Crossref, Google Scholar · doi:10.1007/s10462-011-9290-2 |
| [41] | 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 |
| [42] | Pulina L, Tacchella A (2009) A self-adaptive multi-engine solver for quantified boolean formulas. Constraints 14(1):80-116.Crossref, Google Scholar · Zbl 1183.68589 · doi:10.1007/s10601-008-9051-2 |
| [43] | Rardin RL, Uzsoy R (2001) Experimental evaluation of heuristic optimization algorithms: A tutorial. J. Heuristics 7(3):261-304.Crossref, Google Scholar · Zbl 0972.68634 · doi:10.1023/A:1011319115230 |
| [44] | 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 · Zbl 1184.90118 · doi:10.1007/s10107-008-0235-8 |
| [45] | Rice JR (1976) The algorithm selection problem. Adv. Comput. 15:65-118.Crossref, Google Scholar · doi:10.1016/S0065-2458(08)60520-3 |
| [46] | Silberholz J, Golden B (2010) Comparison of metaheuristics. Gendreau M, Potvin J-Y, eds. Handbook of Metaheuristics (Springer, Boston), 625-640.Crossref, Google Scholar · doi:10.1007/978-1-4419-1665-5_21 |
| [47] | 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 |
| [48] | 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 |
| [49] | 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 |
| [50] | Smith-Miles K, Lopes L (2012) Measuring instance difficulty for combinatorial optimization problems. Comput. Oper. Res. 39(5):875-889.Crossref, Google Scholar · Zbl 1251.90339 · doi:10.1016/j.cor.2011.07.006 |
| [51] | 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 · Zbl 1236.49008 · doi:10.1007/s10472-011-9230-5 |
| [52] | 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 |
| [53] | 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 · Zbl 1348.90646 · doi:10.1016/j.cor.2013.11.015 |
| [54] | 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 |
| [55] | Stadler PF, Schnabl W (1992) The landscape of the traveling salesman problem. Phys. Lett. A 161(4):337-344.Crossref, Google Scholar · Zbl 0979.90509 · doi:10.1016/0375-9601(92)90557-3 |
| [56] | 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 · Zbl 1177.90424 |
| [57] | 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 |
| [58] | Vilalta R, Drissi Y (2002) A perspective view and survey of meta-learning. Artificial Intelligence Rev. 18(2):77-95.Crossref, Google Scholar · doi:10.1023/A:1019956318069 |
| [59] | Vollmann TE, Buffa ES (1966) The facilities layout problem in perspective. Management Sci. 12(10):B-450-B-468.Link, Google Scholar |
| [60] | 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 |
| [61] | Watts DJ, Strogatz SH (1998) Collective dynamics of “small-world” networks. Nature 393(6684):440-442.Crossref, Google Scholar · Zbl 1368.05139 · doi:10.1038/30918 |
| [62] | 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 · doi:10.1103/PhysRevLett.84.6118 |
| [63] | Xu L, · Zbl 1182.68272 · doi:10.1613/jair.2490 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
