1. Travelling Salesman Problem
The traveling salesman problem (TSP) seeks to find the shortest route between a set of points
(cities) that a salesperson must visit exactly once before returning their starting city.
The goal is to minimise the distance travelled by the salesperson, as a proxy measure for
costs incurred. Our studies have focused on Euclidean TSPs, and the performance of two wellknown
variants of the LinKernighan heuristic: one that exploits cluster structure in a TSP instance (set of cities),
and one that doesn't. The instance space analysis supports the intuition that the heuristic that
exploits cluster structure is more powerful, except on instances where little cluster structure exists.
The test instances used to build the instance space include randomly generated 100node TSPs, and instances
that have been evolved to be hard or easy for the two heuristics, as described in the papers below.
Research Publications 
Downloads 
Instance Space Analysis 
1. SmithMiles, K. A., van Hemert, J., Lim, Y., “Understanding TSP Difficulty by Learning from Evolved Instances”, Proceedings of Learning and Intelligent Optimization, LION 4, Lecture Notes in Computer Science, vol. 6073, pp. 266280, 2010.
2. SmithMiles, K. and van Hemert, J. “Discovering the Suitability of Optimisation Algorithms by Learning from Evolved Instances”, Annals of Mathematics and Artificial Intelligence, vol. 61, no. 2, pp. 87104, 2011.
3. SmithMiles, K. and Tan, T. “Measuring Algorithm Footprints in Instance Space”, in Proceedings of the 2012 IEEE Congress on Evolutionary Computation, pp. 34463453, 2012

Instances
Metadata
Feature Extraction Code


2. Graph Coloring Problem
In graph theory, graph or vertex colouring aims to colour the vertices of a graph
such that no two adjacent vertices share the same color. Our 2014 study considered the
benchmark graphs commonly used in computational studies
of graph colouring algorithms, as well as a collection of eight stateoftheart heuristics.
The instance space reveals pockets where the "onaveragebest" performing algorithm is not as well suited as other
algorithms, and the unique strengths and weaknesses of each algorithm can be visualised. Our extended study in 2015,
focusing on 100node graphs,
showed how new graphs could be evolved to fill the instance space, challenging the conclusions that are formed
when only graphs from existing generators are studied.
Research Publications 
Downloads 
Instance Space Analysis 
SmithMiles, K. A., Baatar, D., Wreford, B. and Lewis, R., “Towards Objective Measures of Algorithm Performance across Instance Space”, Computers and Operations Research, vol. 45, pp. 1224, 2014.

Metadata
Code for Feature Selection


SmithMiles, K. A. and Bowly, S., "Generating New Test Instances by Evolving in Instance Space", Computers & Operations Research, vol. 63, pp. 102113, 2015. 
Instances
Metadata


3. MaxCut Graph Problem
The Maximum Cut (MaxCut) graph problem involves partitioning the nodes of a
graph into two subsets such that the number of edges between the subsets is maximised.
There also exist generalisations of this problem such as the nMaxCut problem, where the aim is
to partition the nodes into n subsets, and the weighted MaxCut problem, where each edge is assigned
a numerical weight and the aim is to maximise the sum of the edge weights between subsets.
We have constructed an instance space focusing on the unweighted 2MaxCut problem.
MaxCut is a well studied NPHard problem, with many researchers attempting to find new and innovative algorithms.
In this research, we focus on the Adiabatic Quantum Computing algorithm to solve the MaxCut graph.
The aim of this project is to run the algorithm on a wide variety of different graph instances and
investigate how the features of the graph instances make it easy and hard for adiabatic quantum computing when solving MaxCut.
4. Knapsack Problem
Given a set of items, each with a weight and a value, the Knapsack Problem aims to determine the number of
each item to select so that the total value of the knapsack is as large as possible, while the total weight
meets the maximum capacity constraint. Our studies have focused on the 01 knapsack problem, where each
item is either selected or not, and multiple copies of each item are not considered. We have constructed
an instance space of well known benchmark instances aiming to show where the hard instances lie, in response to
efforts to generate harder knapsack instances.
5. Bin Packing Problem
The onedimensional Bin packing problem (1DBPP) is one of the bestknown optimisation problems, and its
structure and applications have been actively studied. In the 1DBPP there are a set of items,
each with its own weight, and an infinite number of bins, all with the same capacity. The objective
is to minimise the total number of bins used, subject to the constraints that every item is placed
in a bin, and the sum of the weights of the items in each bin does not exceed the capacity.
There is also an analog of the 1DBPP in two dimensions. In the twodimensional
bin packing problem (2DBPP), the bins and items are rectangular. All the bins have
equal widths and heights, and the optimisation objective is to minimise the total
number of bins used while placing the objects into the bins without overlap. During
the placement process, items cannot be rotated.
The goal of this research is to use the methodology of Instance Space Analysis to
study the 1DBPP and 2DBPP. The strengths and
weaknesses of common heuristics are analyzed by exploring the relationships between instance
features and algorithm performances, and scrutinising the diversity of common benchmark test instances.
^{*} The instancespace was originally generated without "random" instances, which were projected on the original instancespace later.
6. Linear Programming
Linear programming is an optimization technique for finding the optimal decision variables that maximise or
minimise a linear objective function subject to a set of linear inequality or equality constraints. Our
studies have focused on understanding how the various strategies used in simplex algorithms are influenced by
the properties of the constraint set. We have also developed methods for generating feasible bounded instances to
enable a more diverse set of instances to be considered than existing benchmark problems offer.
Research Publications 
Downloads 
Instance Space Analysis 

Coming Soon 
Coming Soon 
7. Mixed Integer Programming
Mixed integer programming extends linear programming by constraining some variables to only integer or binary values.
Our studies have focused on generating small instances which are challenging for branch variable selection methods.
Specifically, we evolve instances which show a large discrepancy in the size of the branch and bound tree generated by
different branch variable selection methods.
Research Publications 
Downloads 
Instance Space Analysis 

Coming Soon 
Coming Soon 
8. BlackBox Optimization
The goal in a continuous optimization problem is to maximize or minimize a function whose input and output
variables are real numbers, subject to some constraints. Often, these problems lack an algebraic
expression, have noncalculable derivatives, exhibit uncertainty or noise, or may involve timeconsuming
simulations or experiments. All that is known is a blackbox output response to a given input. Therefore,
sampling the inputs and obtaining the output response is the only way to acquire information about the problem.
This approach is known as blackbox optimization (BBO). Our studies have focused on both singleobjective and
multiobjective BBO problems. For singleobjective BBO we have constructed an instance space of the wellstudied COCO
benchmarks, and then filled the instance space by evolving new test instances exhibiting a wide variety of problem features
and landscapes. Our ongoing work in multiobjective BBO is developing features that can characterise the difficulties of
MOO problems, and the robustness of existing test instance benchmarks.
Research Publications 
Downloads 
Instance Space Analysis 
Muñoz, M. A. and SmithMiles, K. A., "Performance analysis of continuous blackbox optimization algorithms via footprints in instance space", Evolutionary Computation, vol. 25, no. 4, pp. 529554, 2017.

Metadata
Instances
Code for Feature Selection


M.A. Muñoz and K. SmithMiles. Generating new spacefilling test instances for continuous blackbox optimization. Evolutionary Computation, vol. 28, no. 3, pp. 379404, 2020.

Instances
2D Contour Plot Images
Code for Feature Selection


9. MultiObjective Continuous BlackBox Optimisation
Multiobjective optimisation involves the simultaneous maximisation or minimisation of two or more objective functions.
When the objectives are not in conflict with each other, the problem is trivial as an MOP, since it can be solved for
a single best solution. However, when the objectives are conflicting, there are tradeoffs between the objectives
whereby a solution is better for one (or more) objective(s) but worse for the others. Our studies focus on three
contributions: 1) exploring the diversity of existing suites by tuning problem parameters, 2) consolidating many
of the continuous multiobjective suites which are typically considered in isolation and understanding how well
they represent the entire instance space, and 3) supporting and exploring new methods for constructing interesting
benchmark problems which differ from the already available instances.
10. Job Shop Scheduling
The EarlyTardy (E/T) Scheduling Problem is motivated by JustinTime production, which required delivery
of goods to be made at the time required. Both early and late production are discouraged, as early production
incurs holding costs, and late delivery means a loss of customer goodwill. The problem we consider is the single
machine, distinct due date, early/tardy scheduling problem, where each job has an earliness and tardiness penalty
and due date. Once a job is dispatched on the machine, it runs to completion with no
interruptions permitted. The objective is to minimise the total penalty produced when each job is scheduled as
close as possible to its due date. We evaluate the performance of two of the simplest and most commonly used dispatching
heuristics for the E/T scheduling problem:Earliest Due Date and Shortest Processing Time heuristics. The instance space analysis
provides visual confirmation of the relationships discovered in a rulebased machine learning analysis in the 2009 paper below, and
identifies the conditions under which each heuristic is better suited.
Research Publications 
Downloads 
Instance Space Analysis 
SmithMiles, 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. 89103, 2009. 
Metadata


11. Timetabling
Udine Timetabling, also known as the curriculumbased course timetabling problem, was the subject of
track 3 of the 2007 International Timetabling Competition (ITC2007). 21 realworld instances from the
University of Udine were available. In a series of studies below, we have taken the top 2 performing
algorithms in ITC2007  simulated annealing with constraint propagation (SACP) and tabu search over weighted
constraint satisfaction problem (TSCS) and examined their performance on instances from a variety of sources.
Besides the 21 competition realworld instances, we used instances from a random generator of Burke et al. (2010),
and instances we generated by using machine learning to adapt the parameters of this random generator to create
instances that are i) realworld like, and ii) more discriminating of unique algorithm performance. A total of
8199 instances from these three classes are contained in the metadata, along with 32 timetabling features.
Applying instance space analysis now to these previous studies supports the findings in the papers below
(which used decision trees and selforganising maps at that time). There are features such as slack that
determine unique algorithm behaviour, other features such as properties of the teacher connectivity graph that
determine tied behaviours, and features that explain the key differences between the randomly generated instances
and realworld instances.
Research Publications 
Downloads 
Instance Space Analysis 
SmithMiles, K. A.,
and Lopes, L. B., “Generalising Algorithm Performance in Instance Space: A timetabling
case study”, Proceedings of the 5th Learning and Intelligent Optimization conference, LION 5,
Lecture Notes in Computer Science, vol. 6683, pp. 524539, Springer, 2011.
Lopes, L. and SmithMiles, K., “Generating Applicable Synthetic Instances
for Branch Problems”, Operations Research, vol. 61, no. 3, pp. 563577, 2013.
Lopes, L. B. and SmithMiles, K. A., “Pitfalls in Instance Generation for Udine Timetabling”, Proceedings of the 4th Learning and Intelligent Optimization conference, LION 4, Lecture Notes in Computer Science, vol. 6073, pp. 299302, Springer, 2010.
SmithMiles, K.A and Muñoz, M. A “Instance Space Analysis for Algorithm Testing: Methodology and Software Tools” (under review)

Metadata
Summary of Instance Space Analysis


De Coster, A. Musliu, N., Schaerf, A., Schoisswohl, J. and SmithMiles, K., "Algorithm Selection and Instance Space Analysis for Curriculumbased Course Timetabling", Journal of Scheduling, in press, 2021.

Metadata
Instances
Code for Feature Selection


12. Maximum Flow Problem
The Maximum Flow Problem (MFP) involves finding the maximum
volume of flow of a commodity that could be sent from a source
node to a sink node through a network. This problem has been
studied for more than six decades and different polynomial time
algorithms has been proposed for it. Although almost all MFP
algorithms are supported by strong theoretical worstcase
analyses, the judgement about which algorithm is best for a
particular instance or class of instances is still unclear.
The
aim of this research is to construct and analyze the instance
space of MFP for the first time, including proposing suitable
features of MFP instances that capture the algorithms’
performances. Additionally, this research contributes to the
literature by expanding the ISA methodology to address the issue
of how benchmark instances should be selected to reduce bias in
the analysis. Using the enhanced ISA methodology with MFP as a
case study, the paper demonstrates that the most important
instance features affecting algorithm performance can be
detected, and machine learning methods can learn their impact on
algorithm performance, without the bias caused by
overrepresentation within the selected sample of test
instances. The methodology enables new insights into the
performance of stateoftheart generalpurpose MFP algorithms,
as well as recommendations for the construction of comprehensive
and unbiased benchmark test suites for MFP algorithm testing.
Here, three different instance spaces, i.e., Initial,
Augmented, and Unbiased, can be explored for MFP. The initial
instance space is constructed by the initial metadata, which
includes 8508 instances. The Augmented instance space is
constructed based on the augmented metadata, which is obtained
by adding (generating) 16893 new instances with specific
characteristics to the initial metadata to fill the sparse areas
of the initial instance space. Applying the instance selection
process on the augmented metadata, a filtered metadata with only
3857 out of 25401 instances is obtained. The unbiased instance
space is constructed using this filtered metadata.