Optimization Problems

Learning and Model-Fitting Problems

1. Travelling Salesman Problem

TSP 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

graph coloring 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. Knapsack Problem

graph coloring 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

4. Linear Programming

graph coloring 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

5. Mixed Integer Programming

graph coloring 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

6. Black-Box Optimization

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 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

6. Job Shop Scheduling

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

7. 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
Learning and Model-Fitting Problems