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.

We introduce the concept of fruitful regions in a dynamic routing context: regions that have a high potential of generating loads to be transported. The objective is to maximise the number of loads transported, while keeping to capacity and time constraints. Loads arrive while the problem is being solved, which makes it a real-time routing problem. The solver is a self-adaptive evolutionary algorithm that ensures feasible solutions at all times. We investigate under what conditions the exploration of fruitful regions by employing anticipatory routing, improves the effectiveness of the evolutionary algorithm.

We introduce the concept of fruitful regions in a dynamic routing context: regions that have a high potential of generating loads to be transported. The objective is to maximise the number of loads transported, while keeping to capacity and time constraints. Loads arrive while the problem is being solved, which makes it a real-time routing problem. The solver is a self-adaptive evolutionary algorithm that ensures feasible solutions at all times. We investigate under what conditions the exploration of fruitful regions by employing anticipatory routing, improves the effectiveness of the evolutionary algorithm.

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 introduce the concept of fruitful regions in a dynamic routing context: regions that have a high potential of generating loads to be transported. The objective is to maximise the number of loads transported, while keeping to capacity and time constraints. Loads arrive while the problem is being solved, which makes it a real-time routing problem. The solver is a self-adaptive evolutionary algorithm that ensures feasible solutions at all times. We investigate under what conditions the exploration of fruitful regions improves the effectiveness of the evolutionary algorithm.

We compare two heuristic approaches, evolutionary computation and ant colony optimisation, and a complete tree-search approach, constraint programming, for solving binary constraint satisfaction problems. We experimentally show that, if evolutionary computation is far from being able to compete with the two other approaches, ant colony optimisation nearly always succeeds in finding a solution, so that it can actually compete with constraint programming. The resampling ratio is used to provide insight into heuristic algorithms performances. Regarding efficiency, we show that if constraint programming is the fastest when instances have a low number of variables, ant colony optimisation becomes faster when increasing the number of variables.

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.

A presentation in This Week's Discoveries, a colloquium of the faculty of Mathematics and Natural Studies of the Leiden University.

A lecture in the Evolutionary Algorithms course dedicated to the field of Genetic Programming.

A lecture for the user group Artificial Intelligence of the Haagse Computer Club (HCC).

A lecture for the Leidse Biologen Club (LBC).

A lecture for LCN, a company that solves constraint and planning problems.