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.

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.

We present a study on the difficulty of solving binary constraint satisfaction problems where an evolutionary algorithm is used to explore the space of problem instances. By directly altering the structure of problem instances and by evaluating the effort it takes to solve them using a complete algorithm we show that the evolutionary algorithm is able to detect problem instances that are harder to solve than those produced with conventional methods. Results from the search of the evolutionary algorithm confirm conjectures about where the most difficult to solve problem instances can be found with respect to the tightness.

Invited lecture at the School of Computing at the Napier University. Introduction on binary constraint satisfaction, phase transition, problem generating models, solving binary CSPs using evolutionary computation and generating difficult problem instances of binary CSPs using evolutionary computation.