In this paper we demonstrate how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances, thereby stress-testing the corresponding algorithms used to solve these instances. The technique is applied in three important domains of combinatorial optimisation, binary constraint satisfaction, Boolean satisfiability, and the travelling salesman problem. Problem instances acquired through this technique are more difficult than ones found in popular benchmarks. We analyse these evolved instances with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms.

We show how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances. The technique is demonstrated on a number of well known domains of combinatorial optimization, including binary constraint satisfaction and the traveling salesman problem. Problem instances acquired through this technique are more difficult than ones found in popular benchmarks. We analyze these evolved instances with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms.

We present preliminary results on evolving hard problem instances for the bounded diameter minimum spanning tree problem, the generalized minimum spanning tree problem, and the multiple 0/1 knapsack problem. For the first and the latter problem we also present random generators based on properties discovered from the evolved instances. Last, we present a novel representation for the bounded diameter minimum spanning tree problem, based on the level of nodes, which is then used in an evolutionary algorithm with specialised operators and local optimisation methods from a variable neighbourhood search.

We demonstrate how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances. The technique is applied in three important domains of combinatorial optimisation, binary constraint satisfaction, Boolean satisfiability, and the travelling salesman problem. Problem instances acquired through this technique are more difficult than ones found in popular benchmarks. We analyse these evolved instances with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms.

We demonstrate how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances. The technique is applied in three important domains of combinatorial optimisation, binary constraint satisfaction, Boolean satisfiability, and the travelling salesman problem. Problem instances acquired through this technique are more difficult than ones found in popular benchmarks. We analyse these evolved instances with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms.

We demonstrate how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances. The technique is applied in three important domains of combinatorial optimisation, binary constraint satisfaction, Boolean satisfiability, and the travelling salesman problem. Problem instances acquired through this technique are more difficult than ones found in popular benchmarks. We analyse these evolved instances with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms.

Two sets of problem 190 instances each. Result of running an evolutionary algorithm for 600 generations while maximising the search effort of one of two TSP solvers, Chained Lin-Kernighan (CLK) and Lin-Kernighan with Cluster Compensation (LK-CC). Discussed in this paper.

We show how an evolutionary algorithm can successfully be used to evolve a set of difficult to solve symmetric travelling salesman problem instances for two variants of the Lin-Kernighan algorithm. Then we analyse the instances in those sets to guide us towards deferring general knowledge about the efficiency of the two variants in relation to structural properties of the symmetric travelling salesman problem.

We show how an evolutionary algorithm can successfully be used to evolve a set of difficult to solve symmetric travelling salesman problem instances for two variants of the Lin-Kernighan algorithm. Then we analyse the instances in those sets to guide us towards deferring general knowledge about the efficiency of the two variants in relation to structural properties of the symmetric travelling salesman problem.

Although many optimisation and constraint satisfaction problems are considered NP-hard, not every problem instance is necessarily hard to solve. This raises the question what structural properties are responsible for making a problem difficult to solve. By evolving hard to solve problem instances for a problem solver and then analysing these, we may defer general knowledge about the efficiency of the problem solver in relation to certain structural properties. We present our first results on binary constraint satisfaction and the travelling salesman problem.

Although the travelling salesman problem (TSP) is considered NP-hard, not every problem instance is necessarily hard to solve. This raises the question what structural properties are responsible for making a TSP problem difficult to solve. Using evolutionary computation we shall search for problem instances that are difficult for a variant of the famous Lin-Kernighan algorithm. Then, we analyse those problem instances in order to identify interesting structural properties.

This paper introduces a generator that creates problem instances for the Euclidean symmetric travelling salesman problem. To fit real world problems, we look at maps consisting of clustered nodes. Uniform random sampling methods do not result in maps where the nodes are spread out to form identifiable clusters. To improve upon this, we propose an evolutionary algorithm that uses the layout of nodes on a map as its genotype. By optimising the spread until a set of constraints is satisfied, we are able to produce better clustered maps, in a more robust way. When varying the number of clusters in these maps and, when solving the Euclidean symmetric travelling salesman person using Chained Lin-Kernighan, we observe a phase transition in the form of an easy-hard-easy pattern.

This paper introduces a generator that creates problem instances for the Euclidean symmetric travelling salesman problem. To fit real world problems, we look at maps consisting of clustered nodes. Uniform random sampling methods do not result in maps where the nodes are spread out to form identifiable clusters. To improve upon this, we propose an evolutionary algorithm that uses the layout of nodes on a map as its genotype. By optimising the spread until a set of constraints is satisfied, we are able to produce better clustered maps, in a more robust way. When varying the number of clusters in these maps and, when solving the Euclidean symmetric travelling salesman person using Chained Lin-Kernighan, we observe a phase transition in the form of an easy-hard-easy pattern.

To conduct the following research abroad for 12 months at the Centre for Emergent Computing of the Napier University, Edinburgh, Scotland. Abstract. It is generally accepted that no superior optimisation algorithm exists (No-Free-Lunch theorem), making it thus more important to determine what the strong and weak points of a particular algorithm are. Important knowledge along these lines can be gained from identification of the structural properties of a problem that either make it easy or make it difficult for the algorithm to solve it. A successful identification depends on a careful selection of problem instances, which can then be used to make a mapping between an algorithm's performance and the structural properties of the problem. In turn, such a mapping serves as rules of thumb for the development of industrial and business applications. We propose here to create a method of searching for algorithm performance on a number of problem domains. This will be accomplished by using evolutionary computation, an established generic optimisation technique. This enables us to directly search for problem instances that make an algorithm behave in a certain way. For example, an objective can be to locate the problem instances that prove to be the most difficult to solve by a given algorithm. By letting evolutionary computation alter the structure of problem instances directly we have the advantage that minor knowledge of the underlying structure of the problem domain is required. The objective formulated as an optimisation problem, together with a measurement taken of the algorithm, will be sufficient for the evolutionary computation to answer questions about what makes interesting problem instances for that algorithm. Hereby we shall contribute new knowledge regarding performance issues of algorithms on scheduling, timetabling and vehicle routing problems, as well as provide a new methodology that can assist domain experts in their assessment of new algorithms.