Evolving Combinatorial Problem Instances That Are Difficult to Solve
- 1 December 2006
- journal article
- research article
- Published by MIT Press in Evolutionary Computation
- Vol. 14 (4), 433-462
- https://doi.org/10.1162/evco.2006.14.4.433
Abstract
This paper demonstrates how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances. As a result of this technique, the corresponding algorithms used to solve these instances are stress-tested. The technique is applied in three important domains of combinatorial optimisation, binary constraint satisfaction, Boolean satisfiability, and the travelling salesman problem. The problem instances acquired through this technique are more difficult than the ones found in popular benchmarks. In this paper, these evolved instances are analysed with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms.Keywords
This publication has 24 references indexed in Scilit:
- Automatic test program generation: a case studyIEEE Design & Test of Computers, 2004
- Predicting phase transitions of binary constraint satisfaction problems with constraint graph informationIntelligent Data Analysis, 1998
- No free lunch theorems for optimizationIEEE Transactions on Evolutionary Computation, 1997
- Locating the phase transition in binary constraint satisfaction problemsArtificial Intelligence, 1996
- An empirical study of phase transitions in binary constraint satisfaction problemsArtificial Intelligence, 1996
- Exploiting the deep structure of constraint problemsArtificial Intelligence, 1994
- HYBRID ALGORITHMS FOR THE CONSTRAINT SATISFACTION PROBLEMComputational Intelligence, 1993
- Enhancement schemes for constraint processing: Backjumping, learning, and cutset decompositionArtificial Intelligence, 1990
- Increasing tree search efficiency for constraint satisfaction problemsArtificial Intelligence, 1980
- Backtrack ProgrammingJournal of the ACM, 1965