Title: How can data mining help to understand what makes an optimization problem hard, which algorithm will perform best, and why?
Speaker: Prof Kate Smith-Miles, School of Mathematical Sciences, Monash University, Australia
Date and venue: Tuesday, 17 August, 4 p.m., Room 205, Mechanical Engineering Department
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 case studies.
Biography: Kate Smith-Miles is a Professor and Head of the School of Mathematical Sciences at Monash University, Australia. She has held Chairs (Professorships) in three disciplines - Mathematical Sciences, Information Technology, and Engineering and is 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. She is a frequent reviewer of international research activities including grant applications in Canada, U.K., Finland, Hong Kong, Singapore and Australia, refereeing for international research journals, and PhD examinations. From 2007-2008 she was Chair of the IEEE Technical Committee on Data Mining (IEEE Computational Intelligence Society). In addition to her academic activities, she also regularly acts as a consultant to industry in the areas of optimisation, data mining, and intelligent systems.