{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T15:34:04Z","timestamp":1743089644661},"reference-count":158,"publisher":"Elsevier BV","issue":"5","license":[{"start":{"date-parts":[[2012,5,1]],"date-time":"2012-05-01T00:00:00Z","timestamp":1335830400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computers & Operations Research"],"published-print":{"date-parts":[[2012,5]]},"DOI":"10.1016\/j.cor.2011.07.006","type":"journal-article","created":{"date-parts":[[2011,7,16]],"date-time":"2011-07-16T06:33:32Z","timestamp":1310798012000},"page":"875-889","source":"Crossref","is-referenced-by-count":161,"title":["Measuring instance difficulty for combinatorial optimization problems"],"prefix":"10.1016","volume":"39","author":[{"given":"Kate","family":"Smith-Miles","sequence":"first","affiliation":[]},{"given":"Leo","family":"Lopes","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"7043","key":"10.1016\/j.cor.2011.07.006_bib1","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1038\/nature03602","article-title":"Rigorous location of phase transitions in hard optimization problems","volume":"435","author":"Achlioptas","year":"2005","journal-title":"Nature"},{"issue":"2","key":"10.1016\/j.cor.2011.07.006_bib2","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.asoc.2004.12.002","article-title":"On learning algorithm selection for classification","volume":"6","author":"Ali","year":"2006","journal-title":"Applied Soft Computing Journal"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib3","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s004930070001","article-title":"Efficient testing of large graphs","volume":"20","author":"Alon","year":"2000","journal-title":"Combinatorica"},{"key":"10.1016\/j.cor.2011.07.006_bib4","series-title":"Proceedings of the 38th annual ACM symposium on theory of computing","first-page":"251","article-title":"A combinatorial characterization of the testable graph properties: it's all about regularity","author":"Alon","year":"2006"},{"issue":"1\u20133","key":"10.1016\/j.cor.2011.07.006_bib5","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0166-218X(99)00138-9","article-title":"On the classification of NP-complete problems in terms of their correlation coefficient","volume":"99","author":"Angel","year":"2000","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib6","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1023\/A:1015454612213","article-title":"On the hardness of the quadratic assignment problem with metaheuristics","volume":"8","author":"Angel","year":"2002","journal-title":"Journal of Heuristics"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib7","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/s101070100255","article-title":"Solving large quadratic assignment problems on computational grids","volume":"91","author":"Anstreicher","year":"2002","journal-title":"Mathematical Programming"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib8","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/PL00011402","article-title":"A new bound for the quadratic assignment problem based on convex quadratic programming","volume":"89","author":"Anstreicher","year":"2001","journal-title":"Mathematical Programming"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib9","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/BF01588309","article-title":"A note on some computationally difficult set covering problems","volume":"18","author":"Avis","year":"1980","journal-title":"Mathematical Programming"},{"key":"10.1016\/j.cor.2011.07.006_bib10","unstructured":"Bachelet V. M\u00e9taheuristiques parall\u00e8les hybrides: application au probl\u00e8me d'affectation quadratique. PhD thesis, Universite des Sciences et Technologies de Lille; 1999."},{"key":"10.1016\/j.cor.2011.07.006_bib11","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1287\/opre.28.5.1130","article-title":"An algorithm for large zero\u2013one knapsack problems","author":"Balas","year":"1980","journal-title":"Operations Research"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib12","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF02430363","article-title":"Designing and reporting on computational experiments with heuristic methods","volume":"1","author":"Barr","year":"1995","journal-title":"Journal of Heuristics"},{"issue":"6","key":"10.1016\/j.cor.2011.07.006_bib13","doi-asserted-by":"crossref","first-page":"66120","DOI":"10.1103\/PhysRevE.70.066120","article-title":"Clustering analysis of the ground-state structure of the vertex-cover problem","volume":"70","author":"Barthel","year":"2004","journal-title":"Physical Review E"},{"key":"10.1016\/j.cor.2011.07.006_bib14","series-title":"Modern heuristic search methods","first-page":"61","article-title":"Reactive self-search: toward tuning heuristics","author":"Battiti","year":"1996"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib15","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/s004530010074","article-title":"Reactive local search for the maximum clique problem 1","volume":"29","author":"Battiti","year":"2001","journal-title":"Algorithmica"},{"key":"10.1016\/j.cor.2011.07.006_bib16","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1057\/jors.1990.166","article-title":"OR-library: distributing test problems by electronic mail","author":"Beasley","year":"1990","journal-title":"Journal of the Operational Research Society"},{"key":"10.1016\/j.cor.2011.07.006_bib17","unstructured":"Beyrouthy C, Burke EK, McCollum B, McMullan P, Parkes AJ. Enrollment generators, clustering and chromatic numbers. In: Proceedings of the 7th international conference on the practice and theory of automated timetabling (PATAT 2008), Montreal, Canada; 2008."},{"key":"10.1016\/j.cor.2011.07.006_bib18","first-page":"21","article-title":"Landscape regularity and random walks for the job-shop scheduling problem","volume":"vol. 3004","author":"Bierwirth","year":"2004"},{"key":"10.1016\/j.cor.2011.07.006_bib19","series-title":"Metaheuristics-progress in complex systems optimization. Operations research\/computer science interfaces series","first-page":"189","article-title":"The ACO\/F-RACE algorithm for combinatorial optimization under uncertainty","author":"Birattari","year":"2006"},{"year":"1998","series-title":"Modern graph theory","author":"Bollobas","key":"10.1016\/j.cor.2011.07.006_bib20"},{"issue":"2","key":"10.1016\/j.cor.2011.07.006_bib21","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1023\/A:1008230200610","article-title":"Evolution towards the maximum clique","volume":"10","author":"Bomze","year":"1997","journal-title":"Journal of Global Optimization"},{"key":"10.1016\/j.cor.2011.07.006_bib22","first-page":"1","article-title":"The maximum clique problem","volume":"vol. 4(1)","author":"Bomze","year":"1999"},{"key":"10.1016\/j.cor.2011.07.006_bib23","series-title":"IEEE congress on evolutionary computation, 2006. CEC 2006","first-page":"112","article-title":"Kolmogorov complexity, optimization and hardness","author":"Borenstein","year":"2006"},{"key":"10.1016\/j.cor.2011.07.006_bib24","first-page":"184","article-title":"Measures of intrinsic hardness for constraint satisfaction problem instances","volume":"vol. 2932","author":"Boukeas","year":"2004"},{"year":"1999","series-title":"Graph classes: a survey","author":"Brandst\u00e4dt","key":"10.1016\/j.cor.2011.07.006_bib25"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib26","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1023\/A:1021713901879","article-title":"Ranking learning algorithms: using IBL and meta-learning on accuracy and time results","volume":"50","author":"Brazdil","year":"2003","journal-title":"Machine Learning"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib27","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1137\/040609574","article-title":"Solving lift-and-project relaxations of binary integer programs","volume":"16","author":"Burer","year":"2006","journal-title":"SIAM Journal on Optimization"},{"key":"10.1016\/j.cor.2011.07.006_bib28","series-title":"International series in operations research and management science","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/0-306-48056-5_16","article-title":"Hyper-heuristics: an emerging direction in modern search technology","author":"Burke","year":"2003"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib29","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1080\/07408170208928871","article-title":"An investigation of the relationship between problem characteristics and algorithm performance: a case study of the GAP","volume":"34","author":"Cario","year":"2002","journal-title":"IIE Transactions"},{"key":"10.1016\/j.cor.2011.07.006_bib30","series-title":"Proceedings of the 12th IJCAI","first-page":"331","article-title":"Where the really hard problems are","author":"Cheeseman","year":"1991"},{"key":"10.1016\/j.cor.2011.07.006_bib31","unstructured":"Chiarandini M, Stutzle T. Experimental evaluation of course timetabling algorithms. Technical Report, Technical Report AIDA-02-05, FG Intellektik, TU Darmstadt; 2002."},{"issue":"5","key":"10.1016\/j.cor.2011.07.006_bib32","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1504\/IJISE.2008.018231","article-title":"Exploiting empirical knowledge for bi-dimensional knapsack problem heuristics","volume":"3","author":"Cho","year":"2008","journal-title":"International Journal of Industrial and Systems Engineering"},{"key":"10.1016\/j.cor.2011.07.006_bib33","unstructured":"Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem, Technical Report, Report 388, Graduate School of Industrial Administration, Carnegie Mellon University; 1976."},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib34","doi-asserted-by":"crossref","DOI":"10.1002\/1520-6750(198802)35:1<85::AID-NAV3220350108>3.0.CO;2-D","article-title":"A hard knapsack problem","volume":"35","author":"Chung","year":"1988","journal-title":"Naval Research Logistics"},{"year":"1997","series-title":"Spectral graph theory","author":"Chung","key":"10.1016\/j.cor.2011.07.006_bib35"},{"key":"10.1016\/j.cor.2011.07.006_bib36","doi-asserted-by":"crossref","first-page":"1402","DOI":"10.1287\/opre.28.6.1402","article-title":"Hard knapsack problems","author":"Chvatal","year":"1980","journal-title":"Operations Research"},{"issue":"1\u20132","key":"10.1016\/j.cor.2011.07.006_bib37","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0004-3702(95)00058-5","article-title":"Problem structure heuristics and scaling behavior for genetic algorithms","volume":"81","author":"Clearwater","year":"1996","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.cor.2011.07.006_bib38","series-title":"Approximation algorithms for NP-hard problems","first-page":"46","article-title":"Approximation algorithms for bin packing: a survey","author":"Coffman","year":"1996"},{"key":"10.1016\/j.cor.2011.07.006_bib39","series-title":"Proceedings of the 11th international conference on parallel problem solving from nature: part I","first-page":"22","article-title":"Optimisation and generalisation: footprints in instance space","author":"Corne","year":"2010"},{"key":"10.1016\/j.cor.2011.07.006_bib40","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/3-540-63248-4_10","article-title":"Approximation on the web: a compendium of NP optimization problems","author":"Crescenzi","year":"1997","journal-title":"Randomization and Approximation Techniques in Computer Science"},{"issue":"2","key":"10.1016\/j.cor.2011.07.006_bib41","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1162\/evco.1998.6.2.109","article-title":"On the futility of blind search: an algorithmic view of \u201cno free lunch\u201d","volume":"6","author":"Culberson","year":"1998","journal-title":"Evolutionary Computation"},{"key":"10.1016\/j.cor.2011.07.006_bib42","series-title":"Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11\u201313, 1993","first-page":"245","article-title":"Exploring the k-colorable landscape with iterated greedy","author":"Culberson","year":"1996"},{"issue":"2","key":"10.1016\/j.cor.2011.07.006_bib43","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0377-2217(85)90167-5","article-title":"An introduction to timetabling","volume":"19","author":"de Werra","year":"1985","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib44","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1162\/evco.1999.7.3.205","article-title":"Multi-objective genetic algorithms: problem difficulties and construction of test problems","volume":"7","author":"Deb","year":"1999","journal-title":"Evolutionary Computation"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib45","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s10479-005-3444-z","article-title":"Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods","volume":"139","author":"Drezner","year":"2005","journal-title":"Annals of Operations Research"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib46","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1023\/A:1009638304510","article-title":"Graph coloring with adaptive evolutionary algorithms","volume":"4","author":"Eiben","year":"1998","journal-title":"Journal of Heuristics"},{"key":"10.1016\/j.cor.2011.07.006_bib47","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs I","volume":"6","author":"Erd\u0151s","year":"1959","journal-title":"Publicationes Mathematicae Debrecen"},{"key":"10.1016\/j.cor.2011.07.006_bib48","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/978-3-642-61217-6_8","article-title":"Tapping the full power of genetic algorithm through suitable representation and local optimization: application to bin packing","author":"Falkenauer","year":"1995","journal-title":"Evolutionary Algorithms in Management Applications"},{"key":"10.1016\/j.cor.2011.07.006_bib49","series-title":"Proceedings of the 12th annual ACM\u2013SIAM symposium on discrete algorithms","first-page":"652","article-title":"The probabilistic relationship between the assignment and asymmetric traveling salesman problems","author":"Frieze","year":"2001"},{"key":"10.1016\/j.cor.2011.07.006_bib50","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/BFb0120689","article-title":"Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems","volume":"2","author":"Fulkerson","year":"1974","journal-title":"Mathematical Programming Study"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib51","first-page":"295","article-title":"Learning dynamic algorithm portfolios","volume":"47","author":"Gagliolo","year":"2006","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib52","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1023\/A:1009678411503","article-title":"Heuristic solution of open bin packing problems","volume":"3","author":"Gent","year":"1998","journal-title":"Journal of Heuristics"},{"key":"10.1016\/j.cor.2011.07.006_bib53","series-title":"Proceedings of the 8th international symposium on artificial intelligence","article-title":"Phase transitions from real computational problems","author":"Gent","year":"1995"},{"issue":"1\u20132","key":"10.1016\/j.cor.2011.07.006_bib54","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0004-3702(96)00030-6","article-title":"The TSP phase transition","volume":"88","author":"Gent","year":"1996","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.cor.2011.07.006_bib55","unstructured":"Ghosh D, Tathagata B, Ghosh D, Tathagata B. Spotting difficult weakly correlated binary knapsack problems. Technical Report, Indian Institute of Management Ahmedabad, (IIMA) Working Papers 2006-01-04; 2006."},{"year":"1989","series-title":"Genetic algorithms in search and optimization","author":"Goldberg","key":"10.1016\/j.cor.2011.07.006_bib56"},{"key":"10.1016\/j.cor.2011.07.006_bib57","series-title":"Randomization methods in algorithm design: DIMACS Workshop, December 12\u201314, 1997","first-page":"45","article-title":"Combinatorial property testing (a survey)","author":"Goldreich","year":"1998"},{"issue":"2","key":"10.1016\/j.cor.2011.07.006_bib58","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","article-title":"Property testing in bounded degree graphs","volume":"32","author":"Goldreich","year":"2008","journal-title":"Algorithmica"},{"key":"10.1016\/j.cor.2011.07.006_bib59","series-title":"Proceedings of UAI-97","first-page":"190","article-title":"Algorithm portfolio design: theory vs. practice","author":"Gomes","year":"1997"},{"key":"10.1016\/j.cor.2011.07.006_bib60","series-title":"Proceedings of the shape modeling international","first-page":"165","article-title":"On graph partitioning, spectral analysis, and digital mesh processing","author":"Gotsman","year":"2003"},{"key":"10.1016\/j.cor.2011.07.006_bib61","series-title":"IEEE congress on evolutionary computation, 2008. CEC 2008. (IEEE world congress on computational intelligence)","first-page":"242","article-title":"How efficient are genetic algorithms to solve high epistasis deceptive problems?","author":"Gras","year":"2008"},{"year":"2006","series-title":"Graph theory and its applications","author":"Gross","key":"10.1016\/j.cor.2011.07.006_bib62"},{"key":"10.1016\/j.cor.2011.07.006_bib63","first-page":"1157","article-title":"An introduction to variable and feature selection","volume":"3","author":"Guyon","year":"2003","journal-title":"The Journal of Machine Learning Research"},{"key":"10.1016\/j.cor.2011.07.006_bib64","doi-asserted-by":"crossref","first-page":"854","DOI":"10.1287\/opre.49.6.854.10014","article-title":"Generating experimental data for computational testing with machine scheduling applications","author":"Hall","year":"2001","journal-title":"Operations Research"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib65","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1287\/opre.1070.0398","article-title":"Performance prediction and preselection for optimization and heuristic solution procedures","volume":"55","author":"Hall","year":"2007","journal-title":"Operations Research"},{"issue":"43","key":"10.1016\/j.cor.2011.07.006_bib66","doi-asserted-by":"crossref","first-page":"11069","DOI":"10.1088\/0305-4470\/36\/43\/028","article-title":"Statistical mechanics of the vertex-cover problem","volume":"36","author":"Hartmann","year":"2003","journal-title":"Journal of Physics A\u2014Mathematical and General"},{"year":"2005","series-title":"Phase transitions in combinatorial optimization problems: basics, algorithms and statistical mechanics","author":"Hartmann","key":"10.1016\/j.cor.2011.07.006_bib67"},{"key":"10.1016\/j.cor.2011.07.006_bib68","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1287\/mnsc.46.2.302.11930","article-title":"The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance","author":"Hill","year":"2000","journal-title":"Management Science"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib69","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF02430364","article-title":"Testing heuristics: we have it all wrong","volume":"1","author":"Hooker","year":"1995","journal-title":"Journal of Heuristics"},{"issue":"1\u20132","key":"10.1016\/j.cor.2011.07.006_bib70","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0004-3702(99)00048-X","article-title":"Towards a characterisation of the behaviour of stochastic local search algorithms for SAT","volume":"112","author":"Hoos","year":"1999","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.cor.2011.07.006_bib71","article-title":"A Bayesian approach to tackling hard computational problems","volume":"vol. 216","author":"Horvitz","year":"2001"},{"key":"10.1016\/j.cor.2011.07.006_bib72","series-title":"Proceedings of the 11th annual conference on genetic and evolutionary computation","first-page":"271","article-title":"An experimental investigation of model-based parameter optimisation: SPO and beyond","author":"Hutter","year":"2009"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib73","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1613\/jair.2861","article-title":"ParamILS: an automatic algorithm configuration framework","volume":"36","author":"Hutter","year":"2009","journal-title":"Journal of Artificial Intelligence Research"},{"key":"10.1016\/j.cor.2011.07.006_bib74","series-title":"The traveling salesman problem and its variations","article-title":"Experimental analysis of heuristics for the ATSP","author":"Johnson","year":"2004"},{"key":"10.1016\/j.cor.2011.07.006_bib75","series-title":"Proceedings of the 6th international conference on genetic algorithms","article-title":"Fitness distance correlation as a measure of problem difficulty for genetic algorithms","author":"Jones","year":"1995"},{"key":"10.1016\/j.cor.2011.07.006_bib76","first-page":"175","article-title":"The backbone of the travelling sales person","volume":"vol. 19","author":"Kilby","year":"2005"},{"key":"10.1016\/j.cor.2011.07.006_bib77","series-title":"Soft computing systems: design, management and applications, vol. 12","article-title":"Towards landscape analyses to inform the design of a hybrid local search for the multiobjective quadratic assignment problem","author":"Knowles","year":"2002"},{"key":"10.1016\/j.cor.2011.07.006_bib78","unstructured":"Komlos J, Simonovits M. Szemer\u00e9di's regularity lemma and its applications in graph theory. Technical Report, Center for Discrete Mathematics & Theoretical Computer Science; 1995."},{"key":"10.1016\/j.cor.2011.07.006_bib79","first-page":"135","article-title":"Hardness prediction for the university course timetabling problem","volume":"vol. 3004","author":"Kostuch","year":"2004"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib80","doi-asserted-by":"crossref","first-page":"46705","DOI":"10.1103\/PhysRevE.70.046705","article-title":"Threshold values stability analysis and high-q asymptotics for the coloring problem on random graphs","volume":"70","author":"Krza\u00b8ka\u0141a","year":"2004","journal-title":"Physical Review E"},{"key":"10.1016\/j.cor.2011.07.006_bib81","unstructured":"Kulanoot A. Algorithms for some hard knapsack problems. PhD thesis, Curtin University of Technology; 2000."},{"key":"10.1016\/j.cor.2011.07.006_bib82","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","article-title":"The quadratic assignment problem","author":"Lawler","year":"1963","journal-title":"Management Science"},{"key":"10.1016\/j.cor.2011.07.006_bib83","first-page":"144","article-title":"Application of the grouping genetic algorithm to university course timetabling","volume":"vol. 3448","author":"Lewis","year":"2005"},{"key":"10.1016\/j.cor.2011.07.006_bib84","first-page":"556","article-title":"Learning the empirical hardness of optimization problems: the case of combinatorial auctions","volume":"vol. 2470","author":"Leyton-Brown","year":"2002"},{"key":"10.1016\/j.cor.2011.07.006_bib85","first-page":"1542","article-title":"A portfolio approach to algorithm selection","volume":"vol. 18","author":"Leyton-Brown","year":"2003"},{"issue":"2","key":"10.1016\/j.cor.2011.07.006_bib86","doi-asserted-by":"crossref","DOI":"10.1287\/opre.21.2.498","article-title":"An efficient heuristic algorithm for the traveling salesman problem","volume":"21","author":"Lin","year":"1973","journal-title":"Operations Research"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib87","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/s10898-004-9965-1","article-title":"Objective function features providing barriers to rapid global optimization","volume":"31","author":"Locatelli","year":"2005","journal-title":"Journal of Global Optimization"},{"key":"10.1016\/j.cor.2011.07.006_bib88","doi-asserted-by":"crossref","unstructured":"Lopes L, Smith-Miles KA. Generating applicable synthetic instances for branch problems. Operations Research, under review.","DOI":"10.1287\/opre.2013.1169"},{"key":"10.1016\/j.cor.2011.07.006_bib89","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1002\/cplx.6130010511","article-title":"What makes an optimization problem hard","volume":"5","author":"Macready","year":"1996","journal-title":"Complexity"},{"issue":"1\u20133","key":"10.1016\/j.cor.2011.07.006_bib90","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0166-218X(01)00333-X","article-title":"Classes of quadratic assignment problem instances: isomorphism and difficulty measure using a statistical approach","volume":"124","author":"Maia de Abreu","year":"2002","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib91","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1023\/A:1006556606079","article-title":"The racing algorithm: model selection for lazy learners","volume":"11","author":"Maron","year":"1997","journal-title":"Artificial Intelligence Review"},{"key":"10.1016\/j.cor.2011.07.006_bib92","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/mnsc.45.3.414","article-title":"Dynamic programming and strong bounds for the 0\u20131 knapsack problem","author":"Martello","year":"1999","journal-title":"Management Science"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib93","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1287\/ijoc.1090.0320","article-title":"Setting the research agenda in automated timetabling: the second international timetabling competition","volume":"22","author":"McCollum","year":"2010","journal-title":"INFORMS Journal on Computing"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib94","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1162\/1063656041774956","article-title":"Advanced fitness landscape analysis and the performance of memetic algorithms","volume":"12","author":"Merz","year":"2004","journal-title":"Evolutionary Computation"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib95","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/4235.887234","article-title":"Fitness landscape analysis and memetic algorithms for the quadratic assignment problem","volume":"4","author":"Merz","year":"2000","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"6740","key":"10.1016\/j.cor.2011.07.006_bib96","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","article-title":"Determining computational complexity from characteristic'phase transitions","volume":"400","author":"Monasson","year":"1999","journal-title":"Nature"},{"key":"10.1016\/j.cor.2011.07.006_bib97","first-page":"438","article-title":"Understanding random SAT: beyond the clauses-to-variables ratio","volume":"vol. 3258","author":"Nudelman","year":"2004"},{"issue":"2","key":"10.1016\/j.cor.2011.07.006_bib98","doi-asserted-by":"crossref","first-page":"147","DOI":"10.4036\/iis.2002.147","article-title":"Cheeger constant and connectivity of graphs","volume":"8","author":"Oshikiri","year":"2002","journal-title":"Interdisciplinary Information Sciences"},{"issue":"1\u20133","key":"10.1016\/j.cor.2011.07.006_bib99","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/j.disc.2005.10.012","article-title":"Edge cuts leaving components of order at least m","volume":"305","author":"Ou","year":"2005","journal-title":"Discrete Mathematics"},{"key":"10.1016\/j.cor.2011.07.006_bib100","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1287\/opre.26.3.434","article-title":"Some examples of difficult traveling salesman problems","author":"Papadimitriou","year":"1978","journal-title":"Operations Research"},{"key":"10.1016\/j.cor.2011.07.006_bib101","series-title":"Proceedings of the 17th international conference on machine learning table of contents","first-page":"743","article-title":"Meta-learning by landmarking various learning algorithms","author":"Pfahringer","year":"2000"},{"issue":"9","key":"10.1016\/j.cor.2011.07.006_bib102","doi-asserted-by":"crossref","first-page":"2271","DOI":"10.1016\/j.cor.2004.03.002","article-title":"Where are the hard knapsack problems?","volume":"32","author":"Pisinger","year":"2005","journal-title":"Computers and Operations Research"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib103","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.disopt.2009.01.002","article-title":"Compositive and semidefinite relaxations of the quadratic assignment problem","volume":"6","author":"Povh","year":"2009","journal-title":"Discrete Optimization"},{"issue":"11","key":"10.1016\/j.cor.2011.07.006_bib104","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1016\/0167-8655(94)90127-9","article-title":"Floating search methods in feature selection","volume":"15","author":"Pudil","year":"1994","journal-title":"Pattern Recognition Letters"},{"key":"10.1016\/j.cor.2011.07.006_bib105","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BFb0056851","article-title":"Fitness distance correlation and ridge functions","author":"Quick","year":"1998"},{"key":"10.1016\/j.cor.2011.07.006_bib106","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1142\/9789812778215_0019","article-title":"Tight QAP bounds via linear programming","volume":"14","author":"Ramakrishnan","year":"2002","journal-title":"Series on Applied Mathematics"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib107","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0965-9978(01)00046-1","article-title":"GAUSS: an online algorithm selection system for numerical quadrature","volume":"33","author":"Ramakrishnan","year":"2002","journal-title":"Advances in Engineering Software"},{"key":"10.1016\/j.cor.2011.07.006_bib108","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1023\/A:1018983524911","article-title":"Landscapes, operators and heuristic search","volume":"86","author":"Reeves","year":"1999","journal-title":"Annals of Operations Research"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib109","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1287\/ijoc.1090.0330","article-title":"Synthetic optimization problem generation: show us the correlations","volume":"21","author":"Reilly","year":"2009","journal-title":"INFORMS Journal on Computing"},{"key":"10.1016\/j.cor.2011.07.006_bib110","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0065-2458(08)60520-3","article-title":"The algorithm selection problem","author":"Rice","year":"1976","journal-title":"Advances in Computers"},{"key":"10.1016\/j.cor.2011.07.006_bib111","article-title":"Methodology for the algorithm selection problem","volume":"vol. 301","author":"Rice","year":"1979"},{"key":"10.1016\/j.cor.2011.07.006_bib112","first-page":"198","article-title":"An analysis of problem difficulty for a class of optimisation heuristics","volume":"vol. 4446","author":"Ridge","year":"2007"},{"issue":"2","key":"10.1016\/j.cor.2011.07.006_bib113","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/978-1-4615-0013-1_15","article-title":"Property testing","volume":"9","author":"Ron","year":"2001","journal-title":"Combinatorial Optimization"},{"key":"10.1016\/j.cor.2011.07.006_bib114","series-title":"Parallel problem solving from nature\u2014PPSN IV: international conference on evolutionary computation, the 4th international conference on parallel problem solving from nature, Berlin, Germany, September 22\u201326, 1996: proceedings","first-page":"208","article-title":"The density of states\u2014a measure of the difficulty of optimisation problems","author":"Rose","year":"1996"},{"key":"10.1016\/j.cor.2011.07.006_bib115","series-title":"Practice and theory of automated timetabling: first international conference, Edinburgh, UK, August 29\u2013Septmber 1, 1995: selected papers","first-page":"309","article-title":"The phase-transition niche for evolutionary algorithms in timetabling","author":"Ross","year":"1996"},{"key":"10.1016\/j.cor.2011.07.006_bib116","first-page":"115","article-title":"Some observations about GA-based exam timetabling","volume":"vol. 1408","author":"Ross","year":"1997"},{"key":"10.1016\/j.cor.2011.07.006_bib117","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"1295","DOI":"10.1007\/3-540-45110-2_5","article-title":"Learning a procedure that can solve hard bin-packing problems: a new ga-based approach to hyper-heuristics","author":"Ross","year":"2003"},{"key":"10.1016\/j.cor.2011.07.006_bib118","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/978-3-540-45157-0_22","article-title":"A comparison of the performance of different metaheuristics on the timetabling problem","author":"Rossi-Doria","year":"2003"},{"key":"10.1016\/j.cor.2011.07.006_bib119","first-page":"255","article-title":"Learning to solve QBF","volume":"vol. 22","author":"Samulowitz","year":"1999"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib120","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01587087","article-title":"On the facial structure of the set covering polytope","volume":"44","author":"Sassano","year":"1989","journal-title":"Mathematical Programming"},{"issue":"10","key":"10.1016\/j.cor.2011.07.006_bib121","doi-asserted-by":"crossref","first-page":"3143","DOI":"10.1016\/j.cor.2005.11.022","article-title":"A review of metrics on permutations for search landscape analysis","volume":"34","author":"Schiavinotto","year":"2007","journal-title":"Computers & Operations Research"},{"issue":"5\u20136","key":"10.1016\/j.cor.2011.07.006_bib122","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1111\/j.1475-3995.1997.tb00093.x","article-title":"The bin-packing problem: a problem generator and some numerical experiments with FFD packing and MTP","volume":"4","author":"Schwerin","year":"1997","journal-title":"International Transactions in Operational Research"},{"issue":"1\u20132","key":"10.1016\/j.cor.2011.07.006_bib123","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0004-3702(95)00045-3","article-title":"Generating hard satisfiability problems","volume":"81","author":"Selman","year":"1996","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.cor.2011.07.006_bib124","first-page":"254","article-title":"Backbones in optimization and approximation","volume":"vol. 17","author":"Slaney","year":"2001"},{"issue":"6","key":"10.1016\/j.cor.2011.07.006_bib125","doi-asserted-by":"crossref","first-page":"1542","DOI":"10.1109\/72.548187","article-title":"An argument for abandoning the travelling salesman problem as aneural-network benchmark","volume":"7","author":"Smith","year":"1996","journal-title":"IEEE Transactions on Neural Networks"},{"key":"10.1016\/j.cor.2011.07.006_bib126","doi-asserted-by":"crossref","unstructured":"Smith-Miles KA, van Hemert J. Discovering the suitability of optimisation algorithms by learning from evolved instances. Annals of Mathematics and Artificial Intelligence, doi: 10.1007\/s10472-011-9230-5; published online 19th April 2011.","DOI":"10.1007\/s10472-011-9230-5"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib127","doi-asserted-by":"crossref","DOI":"10.1145\/1456650.1456656","article-title":"Cross-disciplinary perspectives on meta-learning for algorithm selection","volume":"41","author":"Smith-Miles","year":"2008","journal-title":"ACM Computing Surveys"},{"key":"10.1016\/j.cor.2011.07.006_bib128","series-title":"IEEE international joint conference on neural networks","first-page":"4118","article-title":"Towards insightful algorithm selection for optimisation using meta-learning concepts","author":"Smith-Miles","year":"2008"},{"key":"10.1016\/j.cor.2011.07.006_bib129","doi-asserted-by":"crossref","unstructured":"Smith-Miles KA, Lopes L. Generalising algorithm performance in instance space: a timetabling case study. In: Lecture notes in computer science, vol. 6683; 2011. p. 524\u201339.","DOI":"10.1007\/978-3-642-25566-3_41"},{"key":"10.1016\/j.cor.2011.07.006_bib130","first-page":"266","article-title":"Understanding TSP difficulty by learning from evolved instances","volume":"vol. 6073","author":"Smith-Miles","year":"2010"},{"key":"10.1016\/j.cor.2011.07.006_bib131","first-page":"89","article-title":"Understanding the relationship between scheduling problem structure and heuristic performance using knowledge discovery","volume":"vol. 5851","author":"Smith-Miles","year":"2009"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib132","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0375-9601(92)90557-3","article-title":"The landscape of the traveling salesman problem","volume":"161","author":"Stadler","year":"1992","journal-title":"Physics Letters A"},{"key":"10.1016\/j.cor.2011.07.006_bib133","first-page":"1197","article-title":"Combining multiple heuristics online","volume":"vol. 22","author":"Streeter","year":"1999"},{"key":"10.1016\/j.cor.2011.07.006_bib134","first-page":"199","article-title":"New benchmark instances for the QAP and the experimental analysis of algorithms","volume":"vol. 3004","author":"Stutzle","year":"2004"},{"issue":"2","key":"10.1016\/j.cor.2011.07.006_bib135","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0966-8349(95)00008-6","article-title":"Comparison of iterative searches for the quadratic assignment problem","volume":"3","author":"Taillard","year":"1995","journal-title":"Location Science"},{"issue":"3","key":"10.1016\/j.cor.2011.07.006_bib136","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1109\/TSMCB.2008.915539","article-title":"Multidimensional knapsack problem: a fitness landscape analysis","volume":"38","author":"Tavares","year":"2008","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics, Part B"},{"key":"10.1016\/j.cor.2011.07.006_bib137","first-page":"18","article-title":"Some complexity aspects of secondary school timetabling problems","volume":"vol. 2079","author":"Ten Eikelder","year":"2000"},{"key":"10.1016\/j.cor.2011.07.006_bib138","series-title":"ECAI","first-page":"123","article-title":"Estimating the hardness of optimisation","author":"Thiebaux","year":"2000"},{"key":"10.1016\/j.cor.2011.07.006_bib139","first-page":"366","article-title":"Formulations and reformulations in integer programming","volume":"vol. 3524","author":"Trick","year":"2005"},{"key":"10.1016\/j.cor.2011.07.006_bib140","unstructured":"Tsymbal A, Pechenizkiy M, Cunningham P. Diversity in ensemble feature selection. Technical Report TCD-CS-2003-44, The University of Dublin; 2003."},{"key":"10.1016\/j.cor.2011.07.006_bib141","series-title":"Proceedings of the European conference on evolutionary computation in combinatorial optimization (EvoCop 2005)","article-title":"Property analysis of symmetric travelling salesman problem instances acquired through evolution","author":"van Hemert","year":"2005"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib142","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1162\/evco.2006.14.4.433","article-title":"Evolving combinatorial problem instances that are difficult to solve","volume":"14","author":"van Hemert","year":"2006","journal-title":"Evolutionary Computation"},{"key":"10.1016\/j.cor.2011.07.006_bib143","first-page":"151","article-title":"Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation","volume":"vol. 3242","author":"van Hemert","year":"2004"},{"key":"10.1016\/j.cor.2011.07.006_bib144","article-title":"Feature selection by maximum marginal diversity: optimality and implications for visual recognition","volume":"vol. 1","author":"Vasconcelos","year":"2003"},{"key":"10.1016\/j.cor.2011.07.006_bib145","series-title":"Proceedings of the 20th annual ACM symposium on theory of computing","first-page":"217","article-title":"Random instances of a graph coloring problem are hard","author":"Venkatesan","year":"1988"},{"issue":"2","key":"10.1016\/j.cor.2011.07.006_bib146","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1023\/A:1019956318069","article-title":"A perspective view and survey of meta-learning","volume":"18","author":"Vilalta","year":"2002","journal-title":"Artificial Intelligence Review"},{"key":"10.1016\/j.cor.2011.07.006_bib147","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1287\/mnsc.12.10.B450","article-title":"The facilities layout problem in perspective","author":"Vollmann","year":"1966","journal-title":"Management Science"},{"key":"10.1016\/j.cor.2011.07.006_bib148","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BFb0056853","article-title":"Modeling building-block interdependency","author":"Watson","year":"1998"},{"issue":"4","key":"10.1016\/j.cor.2011.07.006_bib149","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1145\/235815.235820","article-title":"Pythia: a knowledge-based system to select scientific algorithms","volume":"22","author":"Weerawarana","year":"1996","journal-title":"ACM Transactions on Mathematical Software"},{"issue":"26","key":"10.1016\/j.cor.2011.07.006_bib150","doi-asserted-by":"crossref","first-page":"6118","DOI":"10.1103\/PhysRevLett.84.6118","article-title":"Number of guards needed by a museum: a phase transition in vertex covering of random graphs","volume":"84","author":"Weigt","year":"2000","journal-title":"Physical Review Letters"},{"issue":"10","key":"10.1016\/j.cor.2011.07.006_bib151","doi-asserted-by":"crossref","first-page":"6399","DOI":"10.1103\/PhysRevA.44.6399","article-title":"Local properties of Kauffman's NK model: a tunably rugged energy landscape","volume":"44","author":"Weinberger","year":"1991","journal-title":"Physical Review A"},{"key":"10.1016\/j.cor.2011.07.006_bib152","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1111\/0081-1750.00098","article-title":"The cohesiveness of blocks in social networks: node connectivity and conditional density","author":"White","year":"2001","journal-title":"Sociological Methodology"},{"issue":"1","key":"10.1016\/j.cor.2011.07.006_bib153","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1109\/4235.585893","article-title":"No free lunch theorems for optimization","volume":"1","author":"Wolpert","year":"1997","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"10.1016\/j.cor.2011.07.006_bib154","series-title":"Proceedings of the first ACM\/SIGEVO summit on genetic and evolutionary computation","first-page":"623","article-title":"Problem difficulty analysis for particle swarm optimization: deception and modality","author":"Xin","year":"2009"},{"key":"10.1016\/j.cor.2011.07.006_bib155","first-page":"712","article-title":"SATzilla-07: the design and analysis of an algorithm portfolio for SAT","volume":"vol. 4741","author":"Xu","year":"2007"},{"issue":"5","key":"10.1016\/j.cor.2011.07.006_bib156","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1016\/j.patrec.2008.11.012","article-title":"Different metaheuristic strategies to solve the feature selection problem","volume":"30","author":"Yusta","year":"2009","journal-title":"Pattern Recognition Letters"},{"key":"10.1016\/j.cor.2011.07.006_bib157","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1613\/jair.1389","article-title":"Phase transitions and backbones of the asymmetric traveling salesman problem","volume":"21","author":"Zhang","year":"2004","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1\u20132","key":"10.1016\/j.cor.2011.07.006_bib158","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0004-3702(95)00054-2","article-title":"A study of complexity transitions on the asymmetric traveling salesman problem","volume":"81","author":"Zhang","year":"1996","journal-title":"Artificial Intelligence"}],"container-title":["Computers & Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0305054811001997?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0305054811001997?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T04:37:33Z","timestamp":1686199053000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0305054811001997"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5]]},"references-count":158,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["S0305054811001997"],"URL":"https:\/\/doi.org\/10.1016\/j.cor.2011.07.006","relation":{},"ISSN":["0305-0548"],"issn-type":[{"type":"print","value":"0305-0548"}],"subject":[],"published":{"date-parts":[[2012,5]]}}}