A guest lecture in the regular seminar on heuristic optimisation methods. The aim is to introduce concepts of constraint satisfaction and show a number of methods from constraint programming that solve problems from this domain. We also look at a number of interesting properties of constraint satisfaction problems. The lecture covers definitions and examples of constraint satisfaction, typical search algorithms, consistency checking, variable and value ordering, full assignment approaches, symmetry, problem hardness, and phase transitions.

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.

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