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
|
|
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
|
|
| 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.
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.
5. 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 |
6. 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 |
7. 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
|
|
|
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
|
8. 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
|
|
9. 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.
|
Metadata
Summary of Instance Space Analysis
|
|
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
|
|