Informatics Report Series


Report   

EDI-INF-RR-0905


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Evolving combinatorial problem instances that are difficult to solve
Authors: Jano Van Hemert
Date:Dec 2006
Publication Title:Evolutionary Computation
Publisher:MIT Press Journals
Publication Type:Journal Article Publication Status:Published
Volume No:14(4) Page Nos:433-462
DOI:10.1162/evco.2006.14.4.433 ISBN/ISSN:1063-6560
Abstract:
In 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.
Links To Paper
Available from MIT Press
Bibtex format
@Article{EDI-INF-RR-0905,
author = { Jano Van Hemert },
title = {Evolving combinatorial problem instances that are difficult to solve},
journal = {Evolutionary Computation},
publisher = {MIT Press Journals},
year = 2006,
month = {Dec},
volume = {14(4)},
pages = {433-462},
doi = {10.1162/evco.2006.14.4.433},
url = {http://www.mitpressjournals.org/toc/evco/14/4},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh