01287nas a2200193 4500008004100000245007300041210006900114300001300183490000700196520067600203653002700879653002800906653002900934653002100963653001900984653002401003100001601027856005001043 2006 eng d00aEvolving combinatorial problem instances that are difficult to solve0 aEvolving combinatorial problem instances that are difficult to s a433--4620 v143 aIn 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.10aconstraint programming10aconstraint satisfaction10aevolutionary computation10aproblem evolving10asatisfiability10atravelling salesman1 aHemert, J I uhttp://www.mitpressjournals.org/toc/evco/14/401488nas a2200217 4500008004100000020001800041245013700059210006900196260002800265300001300293520075400306653002801060653002701088653002801115653002901143100001601172700001401188700001601202700001301218856003901231 2004 eng d a3-540-21367-800aA Study into Ant Colony Optimization, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems0 aStudy into Ant Colony Optimization Evolutionary Computation and bSpringer-Verlag, Berlin a114--1233 aWe 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.10aant colony optimisation10aconstraint programming10aconstraint satisfaction10aevolutionary computation1 aHemert, J I1 aSolnon, C1 aGottlieb, J1 aRaidl, G uhttp://research.nesc.ac.uk/node/22