You are here

Evolving binary constraint satisfaction problem instances that are difficult to solve

TitleEvolving binary constraint satisfaction problem instances that are difficult to solve
Publication TypeConference Paper
Year of Publication2003
Authorsvan Hemert, JI
Conference NameProceedings of the IEEE 2003 Congress on Evolutionary Computation
PublisherIEEE Press
ISBN Number0-7803-7804-0
Keywordsconstraint satisfaction; problem evolving
Abstract

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.

Full Text