Title | Evolving binary constraint satisfaction problem instances that are difficult to solve |

Publication Type | Conference Paper |

Year of Publication | 2003 |

Authors | van Hemert, JI |

Conference Name | Proceedings of the IEEE 2003 Congress on Evolutionary Computation |

Publisher | IEEE Press |

ISBN Number | 0-7803-7804-0 |

Keywords | constraint 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 |