×

zbMATH — the first resource for mathematics

Measuring instance difficulty for combinatorial optimization problems. (English) Zbl 1251.90339
Summary: Discovering the conditions under which an optimization algorithm or search heuristic will succeed or fail is critical for understanding the strengths and weaknesses of different algorithms, and for automated algorithm selection. Large scale experimental studies – studying the performance of a variety of optimization algorithms across a large collection of diverse problem instances – provide the resources to derive these conditions. Data mining techniques can be used to learn the relationships between the critical features of the instances and the performance of algorithms. This paper discusses how we can adequately characterize the features of a problem instance that have impact on difficulty in terms of algorithmic performance, and how such features can be defined and measured for various optimization problems. We provide a comprehensive survey of the research field with a focus on six combinatorial optimization problems: assignment, traveling salesman, and knapsack problems, bin-packing, graph coloring, and timetabling. For these problems – which are important abstractions of many real-world problems – we review hardness-revealing features as developed over decades of research, and we discuss the suitability of more problem-independent landscape metrics. We discuss how the features developed for one problem may be transferred to study related problems exhibiting similar structures.

MSC:
90C27 Combinatorial optimization
68W99 Algorithms in computer science
90C60 Abstract computational complexity for mathematical programming problems
PDF BibTeX Cite
Full Text: DOI
References:
[1] Achlioptas, D.; Naor, A.; Peres, Y., Rigorous location of phase transitions in hard optimization problems, Nature, 435, 7043, 759-764, (2005)
[2] Ali, S.; Smith, K.A., On learning algorithm selection for classification, Applied soft computing journal, 6, 2, 119-138, (2006)
[3] Alon, N.; Fischer, E.; Krivelevich, M.; Szegedy, M., Efficient testing of large graphs, Combinatorica, 20, 4, 451-476, (2000) · Zbl 1052.68096
[4] Alon, N.; Fischer, E.; Newman, I.; Shapira, A., A combinatorial characterization of the testable graph properties: It’s all about regularity, (), 251-260 · Zbl 1301.05354
[5] Angel, E.; Zissimopoulos, V., On the classification of NP-complete problems in terms of their correlation coefficient, Discrete applied mathematics, 99, 1-3, 261-277, (2000) · Zbl 0987.90092
[6] Angel, E.; Zissimopoulos, V., On the hardness of the quadratic assignment problem with metaheuristics, Journal of heuristics, 8, 4, 399-414, (2002)
[7] Anstreicher, K.; Brixius, N.; Goux, J.P.; Linderoth, J., Solving large quadratic assignment problems on computational grids, Mathematical programming, 91, 3, 563-588, (2002) · Zbl 1030.90105
[8] Anstreicher, K.M.; Brixius, N.W., A new bound for the quadratic assignment problem based on convex quadratic programming, Mathematical programming, 89, 3, 341-357, (2001) · Zbl 0986.90042
[9] Avis, D., A note on some computationally difficult set covering problems, Mathematical programming, 18, 1, 138-145, (1980) · Zbl 0429.90047
[10] Bachelet V. Métaheuristiques parallèles hybrides: application au problème d’affectation quadratique. PhD thesis, Universite des Sciences et Technologies de Lille; 1999.
[11] Balas, E.; Zemel, E., An algorithm for large zero – one knapsack problems, Operations research, 1130-1154, (1980) · Zbl 0449.90064
[12] Barr, R.S.; Golden, B.L.; Kelly, J.P.; Resende, M.G.C.; Stewart, W.R., Designing and reporting on computational experiments with heuristic methods, Journal of heuristics, 1, 1, 9-32, (1995) · Zbl 0853.68154
[13] Barthel, W.; Hartmann, A.K., Clustering analysis of the ground-state structure of the vertex-cover problem, Physical review E, 70, 6, 66120, (2004)
[14] Battiti, R., Reactive self-search: toward tuning heuristics, (), 61-83
[15] Battiti, R.; Protasi, M., Reactive local search for the maximum clique problem 1, Algorithmica, 29, 4, 610-637, (2001) · Zbl 0985.68016
[16] Beasley, J.E., OR-library: distributing test problems by electronic mail, Journal of the operational research society, 1069-1072, (1990)
[17] 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.
[18] Bierwirth, C.; Mattfeld, D.C.; Watson, J.P., Landscape regularity and random walks for the job-shop scheduling problem, (), 21-30 · Zbl 1177.90144
[19] Birattari, M.; Balaprakash, P.; Dorigo, M., The ACO/F-RACE algorithm for combinatorial optimization under uncertainty, (), 189-203 · Zbl 1173.90587
[20] Bollobas, B., Modern graph theory, (1998), Springer Verlag · Zbl 0902.05016
[21] Bomze, I.M., Evolution towards the maximum clique, Journal of global optimization, 10, 2, 143-164, (1997) · Zbl 0880.90110
[22] Bomze, I.M.; Budinich, M.; Pardalos, P.M.; Pelillo, M., The maximum clique problem, (), 1-74 · Zbl 1253.90188
[23] Borenstein, Y.; Poli, R., Kolmogorov complexity, optimization and hardness, (), 112-119
[24] Boukeas, G.; Halatsis, C.; Zissimopoulos, V.; Stamatopoulos, P., Measures of intrinsic hardness for constraint satisfaction problem instances, (), 184-195 · Zbl 1202.68206
[25] Brandstädt, A.; Spinrad, J.P., Graph classes: a survey, (1999), Society for Industrial Mathematics · Zbl 0919.05001
[26] Brazdil, P.B.; Soares, C.; Da Costa, J.P., Ranking learning algorithms: using IBL and meta-learning on accuracy and time results, Machine learning, 50, 3, 251-277, (2003) · Zbl 1033.68082
[27] Burer, S.; Vandenbussche, D., Solving lift-and-project relaxations of binary integer programs, SIAM journal on optimization, 16, 3, 726-750, (2006) · Zbl 1113.90100
[28] Burke, E.; Kendall, G.; Newall, J.; Hart, E.; Ross, P.; Schulenburg, S., Hyper-heuristics: an emerging direction in modern search technology, (), 457-474 · Zbl 1102.90377
[29] Cario, M.C.; Clifford, J.J.; Hill, R.R.; Yang, I.; Yang, K.; Reilly, C.H., An investigation of the relationship between problem characteristics and algorithm performance: a case study of the GAP, IIE transactions, 34, 3, 297-312, (2002)
[30] Cheeseman, P.; Kanefsky, B.; Taylor, W.M., Where the really hard problems are, (), 331-337 · Zbl 0747.68064
[31] Chiarandini M, Stutzle T. Experimental evaluation of course timetabling algorithms. Technical Report, Technical Report AIDA-02-05, FG Intellektik, TU Darmstadt; 2002.
[32] Cho, Y.K.; Moore, J.T.; Hill, R.R.; Reilly, C.H., Exploiting empirical knowledge for bi-dimensional knapsack problem heuristics, International journal of industrial and systems engineering, 3, 5, 530-548, (2008)
[33] 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.
[34] Chung, C.S.; Hung, M.S.; Rom, W.O., A hard knapsack problem, Naval research logistics, 35, 1, (1988) · Zbl 0638.90073
[35] Chung, F.R.K., Spectral graph theory, (1997), American Mathematical Society · Zbl 0872.05052
[36] Chvatal, V., Hard knapsack problems, Operations research, 1402-1411, (1980) · Zbl 0447.90063
[37] Clearwater, S.H.; Hogg, T., Problem structure heuristics and scaling behavior for genetic algorithms, Artificial intelligence, 81, 1-2, 327-347, (1996)
[38] Coffman, E.G.; Garey, M.R.; Johnson, D.S., Approximation algorithms for bin packing: a survey, (), 46-93, ISBN 0534949681
[39] Corne, D.W.; Reynolds, A.P., Optimisation and generalisation: footprints in instance space, (), 22-31, ISBN 3642158439
[40] Crescenzi, P.; Kann, V., Approximation on the web: a compendium of NP optimization problems, Randomization and approximation techniques in computer science, 111-118, (1997)
[41] Culberson, J.C., On the futility of blind search: an algorithmic view of “no free lunch”, Evolutionary computation, 6, 2, 109-127, (1998)
[42] Culberson, J.C.; Luo, F., Exploring the k-colorable landscape with iterated greedy, (), 245 · Zbl 0864.90117
[43] de Werra, D., An introduction to timetabling, European journal of operational research, 19, 2, 151-162, (1985) · Zbl 0553.90059
[44] Deb, K., Multi-objective genetic algorithms: problem difficulties and construction of test problems, Evolutionary computation, 7, 3, 205-230, (1999)
[45] Drezner, Z.; Hahn, P.M.; Taillard, É.D., Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods, Annals of operations research, 139, 1, 65-94, (2005) · Zbl 1091.90033
[46] Eiben, A.E.; Van Der Hauw, J.K.; Van Hemert, J.I., Graph coloring with adaptive evolutionary algorithms, Journal of heuristics, 4, 1, 25-46, (1998) · Zbl 0912.68150
[47] Erdős, P.; Rényi, A., On random graphs I, Publicationes mathematicae debrecen, 6, 290-297, (1959) · Zbl 0092.15705
[48] Falkenauer, E., Tapping the full power of genetic algorithm through suitable representation and local optimization: application to bin packing, Evolutionary algorithms in management applications, 167-182, (1995) · Zbl 0862.90112
[49] Frieze, A.; Sorkin, G.B., The probabilistic relationship between the assignment and asymmetric traveling salesman problems, (), 652-660 · Zbl 1041.90044
[50] Fulkerson, D.R.; Trotter, L.E.; Nemhouser, G.L., Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems, Mathematical programming study, 2, 72-84, (1974) · Zbl 0353.90060
[51] Gagliolo, M.; Schmidhuber, J., Learning dynamic algorithm portfolios, Annals of mathematics and artificial intelligence, 47, 3, 295-328, (2006) · Zbl 1113.68101
[52] Gent, I.P., Heuristic solution of open bin packing problems, Journal of heuristics, 3, 4, 299-304, (1998) · Zbl 1071.90576
[53] Gent, I.P.; Walsh, T., Phase transitions from real computational problems, ()
[54] Gent, I.P.; Walsh, T., The TSP phase transition, Artificial intelligence, 88, 1-2, 349-358, (1996) · Zbl 0907.68177
[55] 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.
[56] Goldberg, D.E., ()
[57] Goldreich, O., Combinatorial property testing (a survey), (), 45 · Zbl 0912.68071
[58] Goldreich, O.; Ron, D., Property testing in bounded degree graphs, Algorithmica, 32, 2, 302-343, (2008) · Zbl 0990.68103
[59] Gomes, C.P.; Selman, B., Algorithm portfolio design: theory vs. practice, (), 190-197
[60] Gotsman, C., On graph partitioning, spectral analysis, and digital mesh processing, (), 165
[61] Gras, R., How efficient are genetic algorithms to solve high epistasis deceptive problems?, (), 242-249
[62] Gross, J.L.; Yellen, J., Graph theory and its applications, (2006), CRC Press · Zbl 1082.05001
[63] Guyon, I.; Elisseeff, A., An introduction to variable and feature selection, The journal of machine learning research, 3, 1157-1182, (2003) · Zbl 1102.68556
[64] Hall, N.G.; Posner, M.E., Generating experimental data for computational testing with machine scheduling applications, Operations research, 854-865, (2001) · Zbl 1163.90490
[65] Hall, N.G.; Posner, M.E., Performance prediction and preselection for optimization and heuristic solution procedures, Operations research, 55, 4, 703, (2007) · Zbl 1167.90689
[66] Hartmann, A.K.; Weigt, M., Statistical mechanics of the vertex-cover problem, Journal of physics A—mathematical and general, 36, 43, 11069-11094, (2003) · Zbl 1077.68073
[67] Hartmann, A.K.; Weigt, M., Phase transitions in combinatorial optimization problems: basics, algorithms and statistical mechanics, (2005), VCH Verlagsgesellschaft Mbh · Zbl 1094.82002
[68] Hill, R.R.; Reilly, C.H., The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance, Management science, 302-317, (2000) · Zbl 1231.90323
[69] Hooker, J.N., Testing heuristics: we have it all wrong, Journal of heuristics, 1, 1, 33-42, (1995) · Zbl 0853.68155
[70] Hoos, H.H.; Stutzle, T., Towards a characterisation of the behaviour of stochastic local search algorithms for SAT, Artificial intelligence, 112, 1-2, 213-232, (1999) · Zbl 0996.68069
[71] Horvitz, E.; Ruan, Y.; Gomes, C.; Kautz, H.; Selman, B.; Chickering, M., A Bayesian approach to tackling hard computational problems, () · Zbl 0991.68564
[72] Hutter, F.; Hoos, H.H.; Leyton-Brown, K.; Murphy, K.P., An experimental investigation of model-based parameter optimisation: SPO and beyond, (), 271-278
[73] Hutter, F.; Hoos, H.H.; Leyton-Brown, K.; Stuetzle, T., Paramils: an automatic algorithm configuration framework, Journal of artificial intelligence research, 36, 1, 267-306, (2009) · Zbl 1192.68831
[74] Johnson, D.; Gutin, G.; McGeoch, L.; Yeo, A.; Zhang, W.; Zverovitch, A., Experimental analysis of heuristics for the ATSP, The traveling salesman problem and its variations, (2004), p. 445-87 · Zbl 1113.90355
[75] Jones, T.; Forrest, S., Fitness distance correlation as a measure of problem difficulty for genetic algorithms, ()
[76] Kilby, P.; Slaney, J.; Walsh, T., The backbone of the travelling sales person, (), 175
[77] Knowles, J.; Corne, D., Towards landscape analyses to inform the design of a hybrid local search for the multiobjective quadratic assignment problem, Soft computing systems: design, management and applications, vol. 12, (2002), p. 271-9
[78] Komlos J, Simonovits M. Szemerédi’s regularity lemma and its applications in graph theory. Technical Report, Center for Discrete Mathematics & Theoretical Computer Science; 1995. · Zbl 0851.05065
[79] Kostuch, P.; Socha, K., Hardness prediction for the university course timetabling problem, (), 135-144 · Zbl 1177.68191
[80] Krza¸kaŁa, F.; Pagnani, A.; Weigt, M., Threshold values stability analysis and high-q asymptotics for the coloring problem on random graphs, Physical review E, 70, 4, 46705, (2004)
[81] Kulanoot A. Algorithms for some hard knapsack problems. PhD thesis, Curtin University of Technology; 2000. · Zbl 0990.90101
[82] Lawler, E.L., The quadratic assignment problem, Management science, 586-599, (1963) · Zbl 0995.90579
[83] Lewis, R.; Paechter, B., Application of the grouping genetic algorithm to university course timetabling, (), 144-153 · Zbl 1119.68440
[84] Leyton-Brown, K.; Nudelman, E.; Shoham, Y., Learning the empirical hardness of optimization problems: the case of combinatorial auctions, (), 556-572
[85] Leyton-Brown, K.; Nudelman, E.; Andrew, G.; McFadden, J.; Shoham, Y., A portfolio approach to algorithm selection, (), 1542-1543
[86] Lin, S.; Kernighan, B.W., An efficient heuristic algorithm for the traveling salesman problem, Operations research, 21, 2, (1973) · Zbl 0256.90038
[87] Locatelli, M.; Wood, G.R., Objective function features providing barriers to rapid global optimization, Journal of global optimization, 31, 4, 549-565, (2005) · Zbl 1093.90093
[88] Lopes L, Smith-Miles KA. Generating applicable synthetic instances for branch problems. Operations Research, under review. · Zbl 1273.90243
[89] Macready, W.G.; Wolpert, D.H., What makes an optimization problem hard, Complexity, 5, 40-46, (1996)
[90] Maia de Abreu, N.M.; Netto, P.O.B.; Querido, T.M.; Gouvea, E.F., Classes of quadratic assignment problem instances: isomorphism and difficulty measure using a statistical approach, Discrete applied mathematics, 124, 1-3, 103-116, (2002) · Zbl 1005.90042
[91] Maron, O.; Moore, A.W., The racing algorithm: model selection for lazy learners, Artificial intelligence review, 11, 1, 193-225, (1997)
[92] Martello, S.; Pisinger, D.; Toth, P., Dynamic programming and strong bounds for the 0-1 knapsack problem, Management science, 414-424, (1999) · Zbl 1231.90338
[93] McCollum, B.; Schaerf, A.; Paechter, B.; McMullan, P.; Lewis, R.; Parkes, A.J., Setting the research agenda in automated timetabling: the second international timetabling competition, INFORMS journal on computing, 22, 1, 120-130, (2010) · Zbl 1243.90007
[94] Merz, P., Advanced fitness landscape analysis and the performance of memetic algorithms, Evolutionary computation, 12, 3, 303-325, (2004)
[95] Merz, P.; Freisleben, B., Fitness landscape analysis and memetic algorithms for the quadratic assignment problem, IEEE transactions on evolutionary computation, 4, 4, 337-352, (2000)
[96] Monasson, R.; Zecchina, R.; Kirkpatrick, S.; Selman, B.; Troyansky, L., Determining computational complexity from characteristic’phase transitions, Nature, 400, 6740, 133-137, (1999), ISSN 0028-0836 · Zbl 1369.68244
[97] Nudelman, E.; Leyton-Brown, K.; Hoos, H.H.; Devkar, A.; Shoham, Y., Understanding random SAT: beyond the clauses-to-variables ratio, (), 438-452 · Zbl 1152.68569
[98] Oshikiri, G., Cheeger constant and connectivity of graphs, Interdisciplinary information sciences, 8, 2, 147-150, (2002) · Zbl 1016.05050
[99] Ou, J., Edge cuts leaving components of order at least m, Discrete mathematics, 305, 1-3, 365-371, (2005) · Zbl 1078.05052
[100] Papadimitriou, C.H.; Steiglitz, K., Some examples of difficult traveling salesman problems, Operations research, 434-443, (1978) · Zbl 0383.90105
[101] Pfahringer, B.; Bensusan, H.; Giraud-Carrier, C.G., Meta-learning by landmarking various learning algorithms, (), 743-750
[102] Pisinger, D., Where are the hard knapsack problems?, Computers and operations research, 32, 9, 2271-2284, (2005) · Zbl 1116.90089
[103] Povh, J.; Rendl, F., Compositive and semidefinite relaxations of the quadratic assignment problem, Discrete optimization, 6, 3, 231-241, (2009) · Zbl 1167.90597
[104] Pudil, P.; Novovičová, J.; Kittler, J., Floating search methods in feature selection, Pattern recognition letters, 15, 11, 1119-1125, (1994), ISSN 0167-8655
[105] Quick, R.J.; Rayward-Smith, V.J.; Smith, G.D., Fitness distance correlation and ridge functions, (), 77-86
[106] Ramakrishnan, K.G.; Resende, M.; Ramachandran, B.; Pekny, J.F., Tight QAP bounds via linear programming, Series on applied mathematics, 14, 297-304, (2002) · Zbl 1012.90030
[107] Ramakrishnan, N.; Rice, J.R.; Houstis, E.N., GAUSS: an online algorithm selection system for numerical quadrature, Advances in engineering software, 33, 1, 27-36, (2002) · Zbl 1003.68581
[108] Reeves, C.R., Landscapes, operators and heuristic search, Annals of operations research, 86, 473-490, (1999) · Zbl 0921.90095
[109] Reilly, C.H., Synthetic optimization problem generation: show us the correlations, INFORMS journal on computing, 21, 3, 458-467, (2009), ISSN 1526-5528. doi: http://dx.doi.org/10.1287/ijoc.1090.0330 · Zbl 1243.90132
[110] Rice, J.R., The algorithm selection problem, Advances in computers, 65-118, (1976)
[111] Rice, J.R., Methodology for the algorithm selection problem, () · Zbl 0089.04204
[112] Ridge, E.; Kudenko, D., An analysis of problem difficulty for a class of optimisation heuristics, (), 198
[113] Ron, D., Property testing, Combinatorial optimization, 9, 2, 597-643, (2001) · Zbl 1048.68064
[114] Rose, H.; Ebeling, W.; Asselmeyer, T., The density of states—a measure of the difficulty of optimisation problems, (), 208
[115] Ross, P.; Corne, D.; Terashima-Marín, H., The phase-transition niche for evolutionary algorithms in timetabling, (), 309
[116] Ross, P.; Hart, E.; Corne, D., Some observations about GA-based exam timetabling, (), 115-129
[117] Ross, P.; Marin-Blazquez, J.G.; Schulenburg, S.; Hart, E., Learning a procedure that can solve hard bin-packing problems: a new ga-based approach to hyper-heuristics, (), 1295-1306 · Zbl 1038.68841
[118] Rossi-Doria, O.; Sampels, M.; Birattari, M.; Chiarandini, M.; Dorigo, M.; Gambardella, L.M., A comparison of the performance of different metaheuristics on the timetabling problem, (), 329-354
[119] Samulowitz, H.; Memisevic, R., Learning to solve QBF, (), 255, [2007]
[120] Sassano, A., On the facial structure of the set covering polytope, Mathematical programming, 44, 1, 181-202, (1989) · Zbl 0675.90059
[121] Schiavinotto, T.; Stützle, T., A review of metrics on permutations for search landscape analysis, Computers & operations research, 34, 10, 3143-3153, (2007), ISSN 0305-0548 · Zbl 1185.90115
[122] Schwerin, P.; Wascher, G., The bin-packing problem: a problem generator and some numerical experiments with FFD packing and MTP, International transactions in operational research, 4, 5-6, 377-389, (1997) · Zbl 0906.90151
[123] Selman, B.; Mitchell, D.G.; Levesque, H.J., Generating hard satisfiability problems, Artificial intelligence, 81, 1-2, 17-29, (1996)
[124] Slaney, J.; Walsh, T., Backbones in optimization and approximation, (), 254-259
[125] Smith, K., An argument for abandoning the travelling salesman problem as aneural-network benchmark, IEEE transactions on neural networks, 7, 6, 1542-1544, (1996)
[126] 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. · Zbl 1236.49008
[127] Smith-Miles, K.A., Cross-disciplinary perspectives on meta-learning for algorithm selection, ACM computing surveys, 41, 1, (2008)
[128] Smith-Miles, K.A., Towards insightful algorithm selection for optimisation using meta-learning concepts, (), 4118-4124
[129] 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-39.
[130] Smith-Miles, K.A.; van Hemert, J., Understanding TSP difficulty by learning from evolved instances, (), 266-280
[131] Smith-Miles, K.A.; James, R.J.W.; Giffin, J.W.; Tu, Y., Understanding the relationship between scheduling problem structure and heuristic performance using knowledge discovery, (), 89-103
[132] Stadler, P.F.; Schnabl, W., The landscape of the traveling salesman problem, Physics letters A, 161, 4, 337-344, (1992) · Zbl 0979.90509
[133] Streeter, M.; Golovin, D.; Smith, S.F., Combining multiple heuristics online, (), 1197, [2007]
[134] Stutzle, T.; Fernandes, S., New benchmark instances for the QAP and the experimental analysis of algorithms, (), 199-209 · Zbl 1177.90424
[135] Taillard, E.D., Comparison of iterative searches for the quadratic assignment problem, Location science, 3, 2, 87-105, (1995) · Zbl 0916.90235
[136] Tavares, J.; Pereira, F.B.; Costa, E., Multidimensional knapsack problem: a fitness landscape analysis, IEEE transactions on systems, man, and cybernetics, part B, 38, 3, 604-616, (2008)
[137] Ten Eikelder, H.M.M.; Willemen, R.J., Some complexity aspects of secondary school timetabling problems, (), 18-29 · Zbl 0982.68769
[138] Thiebaux, S.; Slaney, J.; Kilby, P., Estimating the hardness of optimisation, (), 123-130
[139] Trick, M., Formulations and reformulations in integer programming, (), 366-379 · Zbl 1133.90372
[140] Tsymbal A, Pechenizkiy M, Cunningham P. Diversity in ensemble feature selection. Technical Report TCD-CS-2003-44, The University of Dublin; 2003.
[141] van Hemert, J.I., Property analysis of symmetric travelling salesman problem instances acquired through evolution, () · Zbl 1119.90368
[142] van Hemert, J.I., Evolving combinatorial problem instances that are difficult to solve, Evolutionary computation, 14, 4, 433-462, (2006)
[143] van Hemert, J.I.; Urquhart, N.B., Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation, (), 151-160
[144] Vasconcelos, N., Feature selection by maximum marginal diversity: optimality and implications for visual recognition, ()
[145] Venkatesan, R.; Levin, L., Random instances of a graph coloring problem are hard, (), 217-222
[146] Vilalta, R.; Drissi, Y., A perspective view and survey of meta-learning, Artificial intelligence review, 18, 2, 77-95, (2002)
[147] Vollmann, T.E.; Buffa, E.S., The facilities layout problem in perspective, Management science, 450-468, (1966)
[148] Watson, R.A.; Hornby, G.S.; Pollack, J.B., Modeling building-block interdependency, (), 97-108
[149] Weerawarana, S.; Houstis, E.N.; Rice, J.R.; Joshi, A.; Houstis, C.E., Pythia: a knowledge-based system to select scientific algorithms, ACM transactions on mathematical software, 22, 4, 447-468, (1996), ISSN 0098-3500 · Zbl 0884.65123
[150] Weigt, M.; Hartmann, A.K., Number of guards needed by a museum: a phase transition in vertex covering of random graphs, Physical review letters, 84, 26, 6118-6121, (2000)
[151] Weinberger, E.D., Local properties of Kauffman’s NK model: a tunably rugged energy landscape, Physical review A, 44, 10, 6399-6413, (1991)
[152] White, D.R.; Harary, F., The cohesiveness of blocks in social networks: node connectivity and conditional density, Sociological methodology, 305-359, (2001)
[153] Wolpert, D.H.; Macready, W.G., No free lunch theorems for optimization, IEEE transactions on evolutionary computation, 1, 1, 67-82, (1997)
[154] Xin, B.; Chen, J.; Pan, F., Problem difficulty analysis for particle swarm optimization: deception and modality, (), 623-630
[155] Xu, L.; Hutter, F.; Hoos, H.H.; Leyton-Brown, K., Satzilla-07: the design and analysis of an algorithm portfolio for SAT, (), 712
[156] Yusta, S.C., Different metaheuristic strategies to solve the feature selection problem, Pattern recognition letters, 30, 5, 525-534, (2009), ISSN 0167-8655
[157] Zhang, W., Phase transitions and backbones of the asymmetric traveling salesman problem, Journal of artificial intelligence research, 21, 471-497, (2004) · Zbl 1081.90055
[158] Zhang, W.; Korf, R.E., A study of complexity transitions on the asymmetric traveling salesman problem, Artificial intelligence, 81, 1-2, 223-239, (1996)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.