MATILDA is an online tool which makes available our new methodology known as Instance Space Analysis. It provides:

• visualisations of the instance space for a problem
  • showing the location of benchmark test instances across the instance space
  • showing the strengths (“footprints”) and weaknesses of algorithms across the instance space
  • summarising the properties of the instances that an algorithm finds easy or hard
• objective (unbiased) metrics of algorithmic power via footprint analysis
• synthetic generation of new test instances at specific locations in the instance space (e.g. real-world-like instances, or instances with controllable properties)
• automated algorithm selection tools to assist deployment of the best algorithm for a given instance.

Our efforts thus far have created instance space analyses for the following problem classes:

1. Optimisation
   • Combinatorial Optimisation Problems
     • Graph Colouring
     • Travelling Salesman Problem
     • Knapsack Problem
     • Timetabling
   • Mathematical Programming
     • Linear Programming
     • Mixed Integer Programming
   • Continuous Optimisation
     • Black-box Single Objective
     • Black-box Multi-Objective
     • Job Shop Scheduling
2. Learning and Model Fitting
   • Machine Learning
     • Classification
     • Regression
     • Clustering
   • Time Series Analysis
     • Time Series Forecasting
   • Image Analysis
     • Facial Age Estimation

If you have additional problems you would like to make available in MATILDA, please contact us (matilda-team@unimelb.edu.au)

USING MATILDA

The engine behind MATILDA is powered by MATLAB code, also available to download and run offline. MATILDA's online platform enables researchers to:

• Download benchmark datasets for various library problems, including existing algorithm performance results, instance features, and our existing instance space visualisations;
• Upload a new algorithm's performance metrics and visualize its comparative strength and weaknesses across our constructed instance space;
• Create instance spaces for new problems to examine the diversity and adequacy of existing benchmarks;
• Generate objective metrics and visualisations of algorithm performance and problem instance distributions across the instance space, to support insightful analysis of algorithmic strengths and weaknesses;
• Use machine learning methods to make recommendations about which algorithm is predicted to perform best in certain regions of the instance space.

Use of MATILDA can be cited as:
Smith-Miles, K., Muñoz, M.A., Neelofar, 2020. Melbourne Algorithm Test Instance Library with Data Analytics (MATILDA). Available at https://matilda.unimelb.edu.au.

Research Publications

The methodology used by MATILDA for visualizing and understanding the strengths and weaknesses of different algorithms is summarised in the following paper:

• Smith-Miles, K. and Muñoz, M. A., "Instance Space Analysis for Algorithm Testing: Methodology and Software Tools", ACM Computing Surveys, vol. 55, no, 12, 2023.

The ISA methodology was developed through a series of three papers focusing on graph colouring as a case study:

• Smith-Miles, K. A., and Lopes, L. B., “Measuring Instance Difficulty for Combinatorial Optimization Problems”, Computers & Operations Research, vol. 39, no. 5, pp. 875-889, 2012.
• Smith-Miles, K. A., Baatar, D., Wreford, B. and Lewis, R., “Towards Objective Measures of Algorithm Performance across Instance Space”, Computers & Operations Research, vol. 45, pp. 12-24, 2014.
• Smith-Miles, K. A. and Bowly, S., "Generating New Test Instances by Evolving in Instance Space", Computers & Operations Research, vol. 63, pp. 102-113, 2015.

The early ideas for the instance space analysis methodology are summarised in three earlier papers:

• Smith-Miles, K. A., “Cross-disciplinary perspectives on meta-learning for algorithm selection”, ACM Computing Surveys, vol. 41, no. 1, article 6, 2008.
• Smith-Miles, K. A., "Towards insightful algorithm selection for optimisation using meta-learning concepts", International Joint Conference on Neural Networks, Workshop on Hybrid Systems, Ensembles, and Meta-Learning Algorithms, pp. 4118-4124, 2008.
• Smith-Miles, K.A. “Generalising meta-learning concepts: from machine learning to meta-heuristics”, in Proceedings of the 7th Meta-heuristics International Conference (MIC’07), Montreal, June 25-29th, 2007.

Additional publications from the MATILDA team have applied this methodology to a wide variety of other problem domains, including:

• Yap, E., Muñoz, M. A. and Smith-Miles, K., "Informing multi-objective optimisation benchmark construction through Instance Space Analysis", IEEE Transactions on Evolutionary Computation, vol. 26, no. 6, pp. 1246-1260, 2022.
• Alipour, H., Muñoz, M. A. and Smith-Miles, K., "Enhanced Instance Space Analysis for the Maximum Flow Problem", European Journal of Operational Research, vol. 304, no. 2, pp. 411-428, 2022.
• De Coster, A. Musliu, N., Schaerf, A., Schoisswohl, J. and Smith-Miles, K., "Algorithm Selection and Instance Space Analysis for Curriculum-based Course Timetabling", Journal of Scheduling, vol. 25, pp. 35–58, 2022.
• Smith-Miles, K. A. and Geng, X., “Revisiting Facial Age Estimation with New Insights from Instance Space Analysis” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 5, pp. 2689-2697, 2022.
• Neelofar, N., Smith-Miles, K., Muñoz, M. A., & Aleti, A. (2022). Instance Space Analysis of Search-Based Software Testing. IEEE Transactions on Software Engineering, 49(4), 2642-2660.
• Aleti, A., & Martinez, M. (2021). E-APR: mapping the effectiveness of automated program repair techniques. Empirical Software Engineering, 26, 1-30.
• dos Santos Fernandes, L. H. , Lorena, A. C. and Smith-Miles, K. "Towards Understanding Clustering Problems and Algorithms: an Instance Space Analysis", Algorithms, vol. 13, no. 3, article 95, 2021.
• Smith-Miles, K., Christiansen, J. and Muñoz, M. ., "Revisiting "Where are the Hard Knapsack Problems?" via Instance Space Analysis", Computers and Operations Research, vol. 128, article 105184, 2021.
• Muñoz, M. A., Yan, T., Leal, M. R., Smith-Miles, K., Lorena, A. C., Pappa, G. L. and Rodrigues, R. M., "An Instance Space Analysis of Regression Problems", ACM Transactions on Knowledge Discovery from Data, vol. 15, no. 2, article 28, 2021.
• Kletzander, L., Musliu, N. and Smith-Miles, K., "Instance Space Analysis for a Personnel Scheduling Problem", Annals of Mathematics and Artificial Intelligence, vol. 89, pp. 617–637, 2021.
• Kandanaarachchi, S., Muñoz, M. A., Hyndman, R. and Smith-Miles, K., "On normalization and algorithm selection for unsupervised outlier detection" , Data Mining and Knowledge Discovery, vol. 34, pp. 309-354, 2020.
• Muñoz, M. A. and Smith-Miles, K. A., "Generating New Space-Filling Test Instances for Continuous Black-Box Optimization", Evolutionary Computation, vol. 28, no. 3, pp. 379-404, 2020.
• Guimares, C., Aleti, Al, Grunske, L. and Smith-Miles, K., "Mapping the Effectiveness of Automated Test Suite Generation Techniques", IEEE Transactions on Reliability, vol. 67, no. 3, pp. 771-785, 2018.
• ​Muñoz, M. A., Villanova, L., Baatar, D. and Smith-Miles, K. A., "Instance Spaces for Machine Learning Classification", Machine Learning, vol. 107, no. 1, pp. 109-147, 2018.
• Kang, Y., Hyndman, R. and Smith-Miles, K., "Visualising Forecasting Algorithm Performance using Time Series Instance Spaces", International Journal of Forecasting, vol. 33, no. 2, pp. 345-358, 2017.
• ​Muñoz, M. A. and Smith-Miles, K. A., "Performance analysis of continuous black-box optimization algorithms via footprints in instance space", Evolutionary Computation, vol. 25. no. 4, pp. 529-554, 2017.
• Smith-Miles, K. and Tan, T. “Measuring Algorithm Footprints in Instance Space”, in Proceedings of the 2012 IEEE Congress on Evolutionary Computation, pp. 3446-3453, 2012. 
• Smith-Miles, K. A., and Lopes, L. B., “Generalising Algorithm Performance in Instance Space: A timetabling case study”, Selected papers of the 5th International Conference on Learning and Intelligent Optimization, Lecture Notes in Computer Science, vol. 6683, pp. 524-539, Springer, 2011. 
• Smith-Miles, K. A., van Hemert, J., Lim, Y., “Understanding TSP Difficulty by Learning from Evolved Instances”, Selected papers of the 4th International Conference on Learning and Intelligent Optimization, Lecture Notes in Computer Science, vol. 6073, pp. 266-280, 2010.
• Lopes, L. B. and Smith-Miles, K. A., “Pitfalls in Instance Generation for Udine Timetabling”, Selected papers of the 4th International Conference on Learning and Intelligent Optimization, Lecture Notes in Computer Science, vol. 6073, pp. 299-302, 2010.
• Smith-Miles, K. A., James, R. J. W., Giffin, J. W. and Tu, Y., “A Knowledge Discovery Approach to Understanding Relationships between Scheduling Problem Structure and Heuristic Performance”, Selected papers of the 3rd International Conference on Learning and Intelligent Optimization, Lecture Notes in Computer Science, vol. 5851, pp. 89-103, 2009.