How can data mining help to understand what makes an optimization problem hard, which algorithm will perform best, and why?

Host Institution:

AGR at RMIT University

Title of Seminar:

A MASCOS and ORSUM OR Seminar via AGR - How can data mining help to understand what makes an optimization problem hard, which algorithm will perform best, and why?

Speaker's Name:

Kate Smith-Miles

Speaker's Institution:

Monash University

Time and Date:

Friday 12th November 2010 at 4:15 pm AEST

Seminar Abstract:

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.

Kate Smith-Miles is a Professor and Head of the School of Mathematical Sciences at Monash University. She has held Chairs in three disciplines - Mathematical Sciences, Information Technology, and Engineering ñ and has been involved in many cross-disciplinary research projects. Kate obtained a B.Sc.(Hons) in Mathematics and a Ph.D. in Electrical Engineering, both from the University of Melbourne, Australia.

Kate has published two books on neural networks and data mining applications, and over 200 refereed journal and international conference papers in the areas of neural networks, combinatorial optimization, intelligent systems and data mining. She is on the editorial board of several international journals including the prestigious IEEE Transactions on Neural Networks, and has been involved in organizing numerous international conferences in the areas of data mining, neural networks, and optimization.

In 2010 Kate was awarded the Australian Mathematical Society Medal for distinguished research. She is a Fellow of the Australian Mathematical Society, and a Fellow of Engineers Australia.

ORSUM seminar abstracts and subscription details are available

Seminar Convenor:

This email address is being protected from spambots. You need JavaScript enabled to view it.

AGR IT support:

This email address is being protected from spambots. You need JavaScript enabled to view it.