how can data mining help to understand what makes an optimization problem hard, which algorithm will perform best, and why
The challenge faced by any algorithm when tackling an optimization problem depends greatly on the characteristics of the particular instance. Some instances are easy for all algorithms, some instances are challenging for most algorithms, and some instances are curiously challenging only for certain types of algorithms. Most optimization problems exhibit easy-hard phase transitions, whereby control of some critical parameter leads to generation of instances that shift from easy to hard. We still know so little about what makes an optimization problem hard for a particular algorithm though. There is much that can be learned from generating large collections of instances, with measurable features to characterize their difficulty, as well as performance results from a variety of algorithms. Data mining processes can be applied to such experimental datasets with a view to learning the relationships between the features of problem instances and the performance of algorithms. This approach can assist with automated algorithm selection, performance prediction, and gaining valuable insights into algorithm behaviour. The methodology for achieving this will be presented, with a case study of the famous Travelling Salesman Problem.
| Departamento de Ingeniería Industrial |
| Facultad de Ciencias Físicas y Matemáticas | Universidad de Chile |
República 701, Santiago, Chile | Teléfono:(562)978-4072 | Fax:(562)978-4011