Generating Applicable Synthetic Instances for Branch Problems

References

• Achlioptas D, Naor A, Peres Y. Rigorous location of phase transitions in hard optimization problems. Nature (2005) 435(7043):759–764Crossref, Google Scholar
• Anderson R, Goldwasser MH, Johnson DS, McGeoch CC. The role of experiment in the theory of algorithms. Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges (2002) 59(American Mathematical Society, Providence, RI) 191–196Crossref, Google Scholar
• Ariyawansa KA, Felt AJ. On a new collection of stochastic linear programming test problems. INFORMS J. Comput. (2004) 16(3):291–299Link, Google Scholar
• Bartz-Beielstein T, Parsopoulos KE, Vrahatis MN. Design and analysis of optimization algorithms using computational statistics. Appl. Numer. Anal. Comput. Math. (2004) 1(2):413–433Crossref, Google Scholar
• Bartz-Beielstein T, Chiarandini M, Paquete L, Preuss M. Experimental Methods for the Analysis of Optimization Algorithms (2010) (Springer, Berlin) Crossref, Google Scholar
• Beasley JE. OR-Library: Distributing test problems by electronic mail. J. Oper. Res. Soc. (1990) 41(11):1069–1072Crossref, Google Scholar
• Beyrouthy C, Burke EK, McCollum B, McMullan P, Parkes AJ. Enrollment generators, clustering and chromatic numbers. Proc. 7th Internat. Conf. Practice and Theory of Automated Timetabling (PATAT 2008) (2008) (University of Nottingham, Nottingham, UK) Google Scholar
• Breiman L. Classification and Regression Trees (1984) (Chapman & Hall/CRC, Boca Raton, FL) Google Scholar
• Brélaz D. New methods to color the vertices of a graph. Commun. ACM (1979) 22:251–256Crossref, Google Scholar
• Burke EK, Marecek J, Parkes AJ, Rudová H. Decomposition, reformulation, and diving in university course timetabling. Comput. Oper. Res. (2010a) 37(3):582–597Crossref, Google Scholar
• Burke EK, Marecek J, Parkes AJ, Rudová H. A supernodal formulation of vertex colouring with applications in course timetabling. Ann. Oper. Res. (2010b) 179(1):105–130Crossref, Google Scholar
• Corne D, Reynolds A. Optimisation and generalisation: Footprints in instance space. Parallel Problem Solving from Nature–PPSN XI (2011) (Springer, Berlin) 22–31Lecture Notes in Computer Science, Vol. 6239Google Scholar
• Culberson J, Hoos H, Stuëtzle T. Hidden solutions, tell-tales, heuristics and anti-heuristics. IJCAI-01 Workshop on Empirical Methods in Artificial Intelligence (2001) (Morgan Kaufmann Publishers, Palo Alto, CA) 9–14Google Scholar
• Erdos P, Rényi A, Sós VT. On a problem of graph theory. Studia Sci. Math. Hungarica (1966) 1(215–235Google Scholar
• Gaspero LD, McCollum B, Schaerf A. The Second International Timetabling Competition (ITC-2007): Curriculum-based course timetabling (Track 3). (2007) . Technical report, University of Udine, Udine, Italy. http://www.cs.qub.ac.uk/itc2007/curriculmcourse/report/curriculumtechreport.pdfGoogle Scholar
• Gehrke J. The Handbook of Data Mining (2003) (Lawrence Erlbaum, Hillsdale, NJ) 3–24Google Scholar
• Hall N, Posner M, Bartz-Beielstein T, Chiarandini M, Paquete L, Preuss M. The generation of experimental data for computational testing in optimization. Experimental Methods for the Analysis of Optimization Algorithms (2010) (Springer, Berlin) 73–101Crossref, Google Scholar
• Hall NG, Posner ME. Generating experimental data for computational testing with machine scheduling applications. Oper. Res. (2001) 49(6):854–865Link, Google Scholar
• Hall NG, Posner ME. Performance prediction and preselection for optimization and heuristic solution procedures. Oper. Res. (2007) 55(4):703–716Link, Google Scholar
• Hill RR, Reilly CH. The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance. Management Sci. (2000) 46(2):302–317Link, Google Scholar
• Hooker JN. Testing heuristics: We have it all wrong. J. Heuristics (1995) 1(1):33–42Crossref, Google Scholar
• Johnson DS, Goldwasser MH, Johnson DS, McGeoch CC. A theoretician's guide to the experimental analysis of algorithms. Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges (2002) 59(American Mathematical Society, Providence, RI) 215–250Crossref, Google Scholar
• Koehler GJ. Conditions that obviate the no-free-lunch theorems for optimization. INFORMS J. Comput. (2007) 19(2):273–279Link, Google Scholar
• Kohonen T. The self-organizing map. Proc. IEEE (2002) 78(9):1464–1480Crossref, Google Scholar
• Kostuch P, Socha K, Gottlieb J, Raidl GR. Hardness prediction for the university course timetabling problem. Evolutionary Computation in Combinatorial Optimization (2004) (Springer, Berlin) 135–144Lecture Notes in Computer Science, Vol. 3004Crossref, Google Scholar
• Leyton-Brown K, Nudelman E, Shoham Y. Empirical hardness models: Methodology and a case study on combinatorial auctions. J. ACM (2009) 56(4):1–52Crossref, Google Scholar
• Lopes L. The O.R. tree. OR/MS Today (2010) 37(5):18–20Google Scholar
• Lougee-Heimer R. The common optimization interface for operations research. IBM J. Res. Development (2000) 47(1):57–66Crossref, Google Scholar
• McGeoch CC, Amherst MA, Goldwasser MH, Johnson DS, McGeoch CC. A bibliography of algorithm experimentation. Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges (2002) 59(American Mathematical Society, Providence, RI) 251–257Crossref, Google Scholar
• Monasson R, Zecchina R, Kirkpatrick S, Selman B, Troyansky L. Determining computational complexity from characteristic “phase transitions”. Nature (1999) 400(6740):133–137Crossref, Google Scholar
• Moret BME, Goldwasser MH, Johnson DS, McGeoch CC. Towards a discipline of experimental algorithmics. Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges (2002) 59(American Mathematical Society, Providence, RI) 197–214Crossref, Google Scholar
• Müller T. ITC2007 solver description: A hybrid approach. Ann. Oper. Res. (2009) 172(1):429–446Crossref, Google Scholar
• Nonobe K, Ibaraki T. An improved tabu search method for the weighted constraint satisfaction problem. INFOR: Inform. Systems Oper. Res. (2001) 39(2):131–151Crossref, Google Scholar
• Quinlan JR. C4.5: Programs for Machine Learning (2003) (Morgan Kaufmann, San Francisco) Google Scholar
• R Development Core Team R: A language and environment for statistical computing. (2010) . R Foundation for Statistical Computing. http://www.R-project.orgGoogle Scholar
• Reilly CH. Synthetic optimization problem generation: Show us the correlations! INFORMS J. Comput. (2009) 21(3):458–467Link, Google Scholar
• Shawe-Taylor J, Cristianini N. Support Vector Machines (2000) (Cambridge University Press, Cambridge, UK) Google Scholar
• Smith-Miles K, Lopes L, Coello Coello CA. Generalising algorithm performance in instance space: A timetabling case study. Learning and Intelligent Optimization (2011) (Springer, Berlin) 524–539Lecture Notes in Computer Science, Vol. 6683Crossref, Google Scholar
• Smith-Miles K, Lopes L. Measuring instance difficulty for combinatorial optimization problems. Comput. Oper. Res. (2012) 39(5):875–889Crossref, Google Scholar
• Smith-Miles K, Tan TT. Measuring algorithm footprints in instance space. Conf. Evolutionary Comput. (2012) (IEEE Press, Piscataway, NJ) 1–8Crossref, Google Scholar
• Smith-Miles KA, van Hemert J. Discovering the suitability of optimisation algorithms by learning from evolved instances. Ann. Math. Artificial Intelligence (2011) 61(2):87–104Crossref, Google Scholar
• Taillard ED. Comparison of iterative searches for the quadratic assignment problem. Location Sci. (1995) 3(2):87–105Crossref, Google Scholar
• Thain D, Tannenbaum T, Livny M. Distributed computing in practice: the Condor experience. Concurrency—Practice and Experience (2005) 17(2–4):323–356Crossref, Google Scholar
• Tuson AL, Harrison SA. Problem difficulty of real instances of convoy planning. J. Oper. Res. Soc. (2005) 56:763–775Crossref, Google Scholar
• Wolpert DH, Macready WG. No free lunch theorems for optimization. IEEE Trans. Evolutionary Comput. (1997) 1(1):67–82Crossref, Google Scholar
• Wood DR. An algorithm for finding a maximum clique in a graph. Oper. Res. Lett. (1997) 21(5):211–217Crossref, Google Scholar