School Seminars and Colloquia

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

ORSUM Seminar

by Kate Smith-Miles

Institution: Monash University
Date: Fri 12th November 2010
Time: 4:15 PM
Location: Access Grid Room, RMIT (host) 8.9.66 (Building 8, Level 9, Room 66)

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.

Biography: 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. She has published 2 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 she 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.

For More Information: contact: Christina Burt. email: