Instance Space Analysis: A toolkit for the assessment of algorithmic power

Instance Space Analysis is a methodology for assessing the strengths and weaknesses of an algorithm and for objectively comparing algorithmic power without bias introduced by a restricted choice of test instances. At its core, it models the relationship between an instance's structural properties and the performance of a group of algorithms. Instance Space Analysis allows the construction of footprints for each algorithm, defined as regions in the instance space where we statistically infer good performance. Other insights that can be gathered from Instance Space Analysis include:

• Objective metrics of each algorithm’s footprint across the instance space as a measure of algorithmic power;
• Explanation through visualisation of how instance features correlate with algorithm performance in various regions of the instance space;
• Visualisation of the distribution and diversity of existing benchmark and real-world instances;
• Assessment of the adequacy of the features used to characterise an instance;
• Partitioning of the instance space into recommended regions for automated algorithm selection;
• Distinguishing areas of the instance space where it may be useful to generate additional instances to gain further insights.

The unique advantage of visualising algorithm performance in the instance space, rather than as a small set of summary statistics averaged across a selected collection of instances, is the nuanced analysis that becomes possible, enabling explanation of strengths and weaknesses and examination of interesting variations in performance that tables of summary statistics may hide.

This repository provides a set of Python tools for conducting a comprehensive Instance Space Analysis within an automated pipeline. We expect it to become the computational engine that powers the Melbourne Algorithm Test Instance Library with Data Analytics (MATILDA) web tools for online analysis. If you would like more information on the Instance Space Analysis methodology, you can refer to here.

If you follow the Instance Space Analysis methodology, please cite as follows:

K. Smith-Miles and M.A. Muñoz. Instance Space Analysis for Algorithm Testing: Methodology and Software Tools. ACM Comput. Surv. 55(12:255),1-31 DOI:10.1145/3572895, 2023.

Also, if you specifically use this code, please cite as follows:

M.A. Muñoz and K. Smith-Miles. Instance Space Analysis: A Python toolkit for the assessment of algorithmic power. andremun/pyInstanceSpace on GitHub. Zenodo, DOI:10.5281/zenodo.15562567, 2025.

Y.B. Güzel, K. Khare, N. Harvey, K. Dsouza, D.H. Jang, J. Chen, C.Z. Lam, and M.A. Muñoz. instancespace: A Python package for insightful algorithm testing through Instance Space Analysis. SoftwareX, 31:102246, DOI:10.1016/j.softx.2025.102246, 2025.

DISCLAIMER: This repository contains research code. On occasion, new features will be added, or changes made that may result in crashes. Although we have made every effort to minimise bugs, this code comes with NO GUARANTEES. If you encounter any issues, please let us know as soon as possible through the contact methods outlined at the end of this document.

Installation Instructions

Run pip install instancespace

An example of running can be found in integration_demo.py

An example of a plugin can be found in example_plugin.py

Documentation Instructions

Hosted API docs: https://andremun.github.io/pyInstanceSpace/ (rebuilt automatically on every push to main/v0.9.0/development-branch-QSF via .github/workflows/docs-pages.yml — see #324 for the one-time GitHub Pages setup this depends on).

To build them locally instead, run pdoc instancespace.

Repository layout

• instancespace/ — the package itself: instance_space.py (the InstanceSpace class — build()/explore()/explore_stage_iter() — hardcodes the built-in 7-stage execution order), stage_runner.py (StageRunner, the execution/rollback engine, plus build_stage_runner() for attaching extra/plugin stages to that order via RunBefore/RunAfter), stages/ (one module per pipeline stage — preprocessing, prelim, sifted, pilot, pythia, cloister, trace), data/ (option and metadata dataclasses), _serialisers.py (2D/3D CSV, mesh, plot, and MAT helpers), and model.py (the trained Model and its save methods).
• tests/ — the flat test suite. tests/fixtures/matlab/current/ is reserved for manifest-verified current MATLAB data; tests/matlab_reference/ contains unverified historical regression snapshots. test_build_<stage>.py covers training and test_explore_<stage>.py covers inference. See tests/README.md.
• examples/data/ — real, multi-dataset example data (BBO, JSS, KP, MFP, and more) used by integration_demo.py/example_plugin.py - not a test fixture.
• integration_demo.py — the minimal runnable example: load metadata + options from examples/data/, construct an InstanceSpace with the full stage list, and build() it.
• example_plugin.py — demonstrates writing a custom Stage and slotting it into the pipeline alongside the built-in stages.
• liveDemoIS.ipynb — the operation manual: a stage-by-stage walkthrough of build() and explore()/explore_stage_iter(), meant to be read as a usage guide.
• docs/ — explore_validation.ipynb (how the MATLAB-reference validation numbers were obtained) and the project roadmap/implementation-pathway documents used to plan ongoing work.
• CLIDocs.txt — notes on the (not yet built) command-line interface.

Working with the code

The basic flow is: construct an InstanceSpace from metadata and options, build() it, then save the results.

from instancespace import InstanceSpace
from instancespace.data import metadata, options

metadata_object = metadata.from_csv_file("metadata.csv")
options_object = options.from_json_file("options.json")

instance_space = InstanceSpace(metadata_object, options_object)
instance_space.build()

instance_space.model.save_to_csv("output/")
instance_space.model.save_graphs("output/")

See integration_demo.py for a complete, runnable version of this (including the explicit stage list), and example_plugin.py for how to add a custom Stage to the pipeline.

Applying a trained model to new data: explore()

InstanceSpace.explore() applies a previously trained model to unseen instances, mirroring the MATLAB toolkit's exploreIS.m: the test metadata is bounded and scaled with the stored PRELIM parameters, reduced to the selected SIFTED features, projected with the trained PILOT matrix, and evaluated by the trained PYTHIA selectors and TRACE footprints. No stage is re-fitted.

explore() works directly on the model build() produced: the trained PYTHIA SVMs are fitted scikit-learn SVC objects, and explore() calls each one's own predict/predict_proba — there is no intermediate flattened representation or conversion step. PRELIM, SIFTED, PILOT and TRACE pass their stored parameters through unchanged. The normal flow is therefore direct:

space = InstanceSpace(train_metadata, options)
space.build()
result = space.explore(test_metadata)

explore() returns the full result in one call; explore_stage_iter() runs the same stages but yields each one's output in turn (prelim, sifted, pilot, pythia, trace), for inspecting the pipeline one stage at a time. The operation manual liveDemoIS.ipynb — the Python counterpart of the MATLAB live demo (liveDemoIS.m) — walks through both build() and explore()/explore_stage_iter() stage by stage and is meant to be read as a usage guide; run it from the repository root.

Stage tests combine synthetic contracts, historical regression snapshots, and a 423-file reference-export/v2 oracle generated from a clean MATLAB R2026a Update 4 run. tests/matlab_reference/ is explicitly unverified; the manifest-verified oracle lives under tests/fixtures/matlab/current/. The current MATLAB source and verified execution are the behavioral authority when an issue, review, or older document disagrees. tests/README.md documents the naming and trust conventions.

Development Environment Setup Guide

REQUIREMENTS:

• Python 3.12 installed
• Be inside the repository directory

Step 1: Install poetry

Linux, Mac, WSL

curl -sSL https://install.python-poetry.org | python3 -

Windows

(Invoke-WebRequest -Uri https://install.python-poetry.org -UseBasicParsing).Content | py -

Step 2: Setup virtual environment

poetry shell

Step 3: Install Python dependencies into a virtual environment

poetry install

The metadata file

The metadata.csv file should contain a table where each row corresponds to a problem instance, and each column must strictly follow the naming convention mentioned below:

• instances instance identifier - We expect the instance identifier to be of type "String". This column is mandatory.
• source instance source - This column is optional
• feature_name The keyword "feature_" concatenated with feature name. For instance, if the feature name is "density", the header name should be mentioned as "feature_density". If the name consists of more than one word, each word should be separated by "_" (spaces are not allowed). There must be more than two features for the software to work. We expect the features to be of the type "Double".
• algo_name The keyword "algo_" concatenated with algorithm name. For instance, if the algorithm name is "Greedy", the column header should be "algo_greedy". If the name consists of more than one word, each word should be separated by "_" (spaces are not allowed). You can add the performance of more than one algorithm in the same .csv. We expect the algorithm performance to be of the type "Double".

Moreover, empty cells, NaN or null values are allowed but not recommended. We'd like you to handle missing values in your data before processing. You may use this file as a reference.

Options

The options.json contains a structure that contains all the settings used by the code. Broadly, there are settings required for the analysis itself, settings for data pre-processing, and output settings. These are divided into general, dimensionality reduction, bound estimation, algorithm selection and footprint construction settings. Additionally, the toolkit includes routines for bounding outliers, scaling the data, and selecting features.

Option names below are given as the Python attribute path (e.g. options.perf.max_perf); the same names, case-insensitively, are the keys expected in options.json. A handful of legacy MATLAB-style key spellings (e.g. ncores, cvfolds) are still accepted for backward compatibility with option files written for the MATLAB toolkit.

General settings

• opts.perf.max_perf determines whether the algorithm performance values provided are efficiency measures that should be maximised (set as TRUE), or cost measures that should be minimised (set as FALSE).
• opts.perf.abs_perf determines whether good performance is defined absolutely, e.g., misclassification error is lower than a 20%, (set as TRUE), or if it is defined relatively to the best performing algorithm, e.g., misclassification error is within at least 5% of the best algorithm, (set as FALSE).
• opts.perf.epsilon corresponds to the threshold used to calculate good performance. It must be of the type "Double".
• opts.perf.beta_threshold corresponds to the fraction of algorithms in the portfolio that must have good performance in the instance, for it to be considered an easy instance. It must be a value between 0 and 1.
• opts.parallel.flag determines whether parallel processing will be available (set as TRUE), or not (set as FALSE). The toolkit uses Python's multiprocessing (in TRACE) and scikit-learn's n_jobs (in PYTHIA) to distribute work across local cores.
• opts.parallel.n_cores number of available cores for parallel procesing.
• opts.selvars.small_scale_flag: By setting this flag as TRUE, you can carry out a small-scale experiment using a randomly selected fraction of the original data. This is useful if you have a large dataset with more than 1000 instances and want to explore the model's parameters.
• opts.selvars.small_scale fraction taken from the original data on the small-scale experiment.
• opts.selvars.file_idx_flag by setting this flag as TRUE, you can carry out a small scale experiment. This time, you must provide a .csv file that contains, in a single column, the indices of the instances to be taken. This may be useful if you want to make a more controlled experiment than just randomly selecting instances.
• opts.selvars.file_idx name of the file containing the indices of the instances.

Dimensionality reduction settings

PILOT produces either two or three coordinates. method="standard" uses the analytic solution or a multi-start BFGS solve; method="pls" uses the SIMPLS algorithm used by MATLAB R2026a's plsregress. Technical details about PILOT are available here.

• opts.pilot.method selects "standard" (default) or "pls". SIMPLS ignores opts.pilot.analytic, matching MATLAB.
• opts.pilot.dims selects a 2D (default) or 3D projection and is also passed to SIFTED's candidate projections.
• opts.pilot.analytic selects the analytic (TRUE) or numerical (FALSE) standard solver. The numerical solver is safer for poorly conditioned inputs.
• opts.pilot.n_tries sets the numerical restart count. opts.pilot.x0 supplies starting columns; opts.pilot.precalc_alpha replays a compatible solved column.
• opts.pilot.cost_weight weights performance reconstruction relative to feature reconstruction in the standard solver.
• opts.pilot.view_groups supplies zero-based algorithm-index groups for 3D camera optimization. An empty value creates one global viewpoint. The trained model stores each 2-by-3 view and its azimuth/elevation for plotting.
• opts.pilot.adjust_rotation (default FALSE) rotates a 2D projection so instances poorly solved by every algorithm face 135°. It preserves pairwise distances, reconstruction metrics, and footprint areas. This Python option is not used for 3D.

Empirical bound estimation settings.

The toolkit uses CLOISTER, a correlation-based algorithm, to detect the empirical bounds of the Instance Space.

• opts.cloister.c_thres Determines the maximum Pearson correlation coefficient that would indicate non-correlated variables. The lower this value is, the more stringent is the algorithm; hence, it would be less likely to produce a good bound.
• opts.cloister.p_val Determines the p-value of the Pearson correlation coefficient that indicates no correlation.

Algorithm selection settings

The toolkit trains one scikit-learn SVC per algorithm as the algorithm selection model.

• opts.pythia.cv_folds number of folds of the stratified cross-validation (CV) experiment used during hyperparameter tuning.
• opts.pythia.is_poly_krnl determines whether to use a polynomial (set as TRUE) or Gaussian/RBF (set as FALSE, the default) kernel. The RBF kernel is usually significantly faster to compute and more accurate; however, it also has the disadvantage of producing discontinuous regions of good performance that may appear overfit. We tend to recommend a polynomial kernel if the dataset is higher than 1000 instances.
• opts.pythia.tuning selects the hyperparameter tuning strategy for the SVM's box constraint and kernel scale: 'sobol' (the default, matching the MATLAB toolkit) evaluates opts.pythia.n_tuning_iter scrambled Sobol quasi-random candidates via stratified CV and keeps the best; 'bayes' uses Bayesian optimisation via scikit-optimize's BayesSearchCV instead; 'none' skips tuning entirely and requires opts.pythia.params to already hold valid per-algorithm hyperparameters.
• opts.pythia.n_tuning_iter number of Sobol candidates evaluated when opts.pythia.tuning is 'sobol' (default 20).
• opts.pythia.use_weights determines whether weighted (set as TRUE) or unweighted (set as FALSE, the default) classification is performed. The weights are calculated as , i.e. each instance's absolute deviation from the algorithm's mean performance.
• opts.pythia.uselibsvm (legacy) accepted for backward compatibility with option files from the MATLAB toolkit, and genuinely ignored - does not select LIBSVM, which this implementation does not use.

Footprint construction settings

TRACE builds good, best, hard, and full-space footprints. method="legacy" retains the historical 2D DBSCAN/Shapely path and remains Python's compatibility default. method="trace3" implements MATLAB's current alpha-shape algorithm with 2D polygons or native 3D tetrahedral meshes. A 3D projection always dispatches to TRACE3 because legacy TRACE is 2D-only. Build metrics and explore() rescoring use the same exact, boundary-inclusive membership rule as MATLAB.

• opts.trace.method selects "legacy" (default) or "trace3".
• opts.trace.use_sim uses PYTHIA predictions (TRUE) or observed good-performance labels (FALSE). TRACE3 falls back to observed labels when PYTHIA is skipped.
• opts.trace.purity sets the minimum footprint purity. Its default is method-aware: 0.55 for legacy and 0.60 for TRACE3.
• opts.trace.contra controls legacy contradiction removal.
• opts.trace.min_instances and opts.trace.min_area_frac control TRACE3's minimum support and retained area/volume.

Automatic data bounding and scaling

The toolkit implements simple routines to bound outliers and scale the data. These routines are by no means perfect, and users should pre-process their data independently if preferred. However, the automatic bounding and scaling routines should give some idea of the kind of results that may be achieved. In general, we recommend transforming the data to be close to normally distributed due to the linear nature of PILOT's optimal projection algorithm.

• opts.auto.preproc turns on (set as TRUE) the automatic pre-processing.
• opts.bound.flag turns on (set as TRUE) data bounding. This sub-routine calculates the median and the interquartile range (IQR) of each feature and performance measure, and bounds the data to the median plus or minus five times the IQR.
• opts.norm.flag turns on (set as TRUE) scalling. This sub-routine scales each feature and performance measure into a positive range. Then it calculates a box-cox transformation to stabilise the variance, and a Z-transformation to standardise the data. The results are features and performance measures that are close to normally distributed.

Automatic feature selection

The toolkit implements SIFTED, a routine to select features, given their cross-correlation and correlation to performance. Ideally, we want the fewest orthogonal and predictive features. This routine is by no means perfect, and users should pre-process their data independently if preferred. In general, we recommend using no more than 10 features as input to PILOT's optimal projection algorithm, given the numerical nature of its solution and the difficulty of identifying meaningful linear trends.

• opts.sifted.flag turns on (set as TRUE) the automatic feature selection. SIFTED is composed of two sub-processes. For the first one, SIFTED calculates the Pearson correlation coefficient between the features and the performance metric. Then it takes its absolute value and sorts them from largest to smallest. Then it selects all features with a correlation above the threshold. It automatically bounds itself to a minimum of 3 features. Then, SIFTED uses the Pearson correlation coefficient as a dissimilarity metric between features. Then, k-means clustering is used to identify groups of similar features. To select one feature per group, the algorithm first projects the selected features into two dimensions using Principal Component Analysis (PCA) and then uses Random Forests to predict whether an instance is easy for a given algorithm. Then, the subset of features that gives the most accurate models is selected. This section of the routine is potentially computationally very expensive due to the multilayer training process. However, our current recommended approach is to select the most relevant features. This routine tests all possible combinations if they are less than 1000, or uses the combination of a Genetic Algorithm and a Look-up table otherwise.
• opts.sifted.rho correlation threshold indicating the lowest acceptable absolute correlation between a feature and performance. It should be a value between 0 and 1.
• opts.sifted.k number of clusters which corresponds to the final number of features returned. The routine assumes at least 3 clusters and no more than the number of features. Ideally, it should not exceed 10.
• opts.sifted.n_trees number of trees used by the Random Forest models. Typically, this setting does not require adjustment.
• opts.sifted.max_iter number of iterations used to converge the k-means algorithm. Typically, this setting does not require adjustment.
• opts.sifted.replicates number of repeats carried out of the k-means algorithm. Typically, this setting does not require adjustment.

Output settings

These settings result in more information being stored in files or presented in the console output.

Two-dimensional saves retain the existing polygon CSV and plot formats. Three-dimensional saves write z_1/z_2/z_3 coordinates plus footprint_meshes.json and one-based vertex, tetrahedron, and outward-boundary-face CSV files under the pyinstancespace.trace-mesh/v1 schema. Plots use native matplotlib 3D axes, mesh surfaces, and the stored global or per-algorithm PILOT viewpoint.

• opts.outputs.csv This flag produces the output CSV files for post-processing and analysis. It is recommended to leave this setting as TRUE.
• opts.outputs.png This flag produces the output figure files for post-processing and analysis. It is recommended to leave this setting as TRUE.
• opts.outputs.web This flag produces the output files employed to draw the figures in MATILDA's web tools (click here to open an account). It is recommended to leave this setting as FALSE.

Contact

If you have any suggestions or ideas (e.g. for new features), or if you encounter any problems while running the code, please use this repository's own issue tracker or contact us through MATILDA's Queries and Feedback page.

Acknowledgements

Funding for the development of this code was provided by:

• The Australian Research Council, through the ARC Industrial Transformation Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA; grant No. IC200100009).
• The University of Melbourne, through grant 2025DYA013.

This code was partly developed as part of the subject SWEN90017-18 by students Junheng Chen, Yusuf Berdan Guzel, Kushagra Khare, Dong Hyeog Jang, Kian Dsouza, Nathan Harvey, Tao Yu, Xin Xiang, Jiaying Yi, and Cheng Ze Lam. Ben Golding mentored the team, and Mansooreh Zahedi coordinated the subject. Sean Xiao developed the explore() pipeline.