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 well-known variants of the Lin-Kernighan 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 100-node 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. Smith-Miles, 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. 266-280, 2010. 2. Smith-Miles, 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. 87-104, 2011. 3. 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	Instances Metadata Feature Extraction Code	View

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 state-of-the-art heuristics. The instance space reveals pockets where the "on-average-best" 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 100-node 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
Smith-Miles, 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. 12-24, 2014.	Metadata Code for Feature Selection	View
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.	Instances Metadata Code for Feature Selection	Coming Soon

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 n-MaxCut 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 2-MaxCut problem. MaxCut is a well studied NP-Hard 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.

Masters Dissertation	Downloads	Instance Space Analysis
Fenella McAndrew, "Adiabatic Quantum Computing to solve the MaxCut graph problem", Master of Science (Mathematics and Statistics) dissertation, The University of Melbourne, 2020 (supervised by Kate Smith-Miles and Charles Hill).	Metadata	View

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 0-1 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.

Research Publications	Downloads	Instance Space Analysis
Smith-Miles, K., Christiansen, J., Muñoz, M. A., Revisiting Where are the Hard Knapsack Problems? via Instance Space Analysis, pre-print	Metadata Metadata (Evolved Instances) Code for Feature Selection Instances	View View (Evolved Instances)

5. Bin Packing Problem

The one-dimensional Bin packing problem (1DBPP) is one of the best-known 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 two-dimensional 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.

Masters Dissertation	Downloads	Instance Space Analysis
Kelvin Liu, "Using Instance Space Analysis to Study the Bin Packing Problem", Master of Science (Mathematics and Statistics) dissertation, The University of Melbourne, 2020 (supervised by Kate Smith-Miles and Alysson Costa).	Metadata-1D Code for Feature Selection-1D Instances-1D Metadata-2D Code for Feature Selection-2D Instances-2D	View(1D*) View(2D)

^* The instance-space was originally generated without "random" instances, which were projected on the original instance-space 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.

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.

8. Black-Box 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 non-calculable derivatives, exhibit uncertainty or noise, or may involve time-consuming simulations or experiments. All that is known is a black-box 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 black-box optimization (BBO). Our studies have focused on both single-objective and multi-objective BBO problems. For single-objective BBO we have constructed an instance space of the well-studied 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 multi-objective 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 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.	Metadata Instances Code for Feature Selection	View
M.A. Muñoz and K. Smith-Miles. Generating new space-filling test instances for continuous black-box optimization. Evolutionary Computation, vol. 28, no. 3, pp. 379-404, 2020.	Instances 2D Contour Plot Images Code for Feature Selection	Coming Soon

9. Job Shop Scheduling

The Early-Tardy (E/T) Scheduling Problem is motivated by Just-in-Time 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 rule-based 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
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.	Metadata	View

10. Timetabling

Udine Timetabling, also known as the curriculum-based course timetabling problem, was the subject of track 3 of the 2007 International Timetabling Competition (ITC2007). 21 real-world 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 real-world 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) real-world like, and ii) more discriminating of unique algorithm performance. A total of 8199 instances from these three classes are contained in the meta-data, 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 self-organising 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 real-world instances.

Research Publications	Downloads	Instance Space Analysis
Smith-Miles, 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. 524-539, Springer, 2011. Lopes, L. and Smith-Miles, K., “Generating Applicable Synthetic Instances for Branch Problems”, Operations Research, vol. 61, no. 3, pp. 563-577, 2013. Lopes, L. B. and Smith-Miles, 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. 299-302, Springer, 2010. Smith-Miles, K.A and Muñoz, M. A “Instance Space Analysis for Algorithm Testing: Methodology and Software Tools” (under review)	Metadata	View
De Coster, A., Musliu, N., Schaerf, A., Schoisswohl, J. and Smith-Miles, K. “Algorithm Selection & Instance Space Analysis for Curriculum-based Course Timetabling. (under review)	Metadata Instances Code for Feature Selection	View

11. 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 worst-case 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 over-representation within the selected sample of test instances. The methodology enables new insights into the performance of state-of-the-art general-purpose MFP algorithms, as well as recommendations for the construction of comprehensive and unbiased benchmark test suites for MFP algorithm testing.

Research Publications	Downloads	Instance Space Analysis
Alipour, H., Muñoz, M. A. and Smith-Miles, K. A., "Enhanced Instance Space Analysis for the Maximum Flow Problem", In preperation.	Metadata Code for Feature Extraction	View