Scientific Computing & Optimisation

The Scientific Computing and Optimisation group specializes in the theory, design and application of heuristic and probabilistic algorithms, focussing on two main strands of interest. One strand concentrates on non-linear and probabilistic modelling for data analysis and signal processing, and the other on heuristic and metaheuristic search. Some topics we are currently pursuing include:

• Heuristic and metaheuristic search
• Multiobjective optimization
• Non-linear modelling, data analysis and signal processing
• Complexity analysis of bioinformatics data

Non-linear and Probabilistic Modelling

A key achievement of the group is the development of the Gamma test. Around this essentially simple technique, a new set of analytical tools has evolved which allow us to model smooth non-linear systems directly from the data with a precision and confidence that hitherto was inaccessible. Development has also involved powerful new mathematical tools enabling the theoretical analysis and discovery of novel noise and entropy estimation algorithms.

Opportunistic data networks consist of mobile nodes equipped with short range wireless communications devices, where information is dispersed both by wireless transmission between the nodes and the movement of the nodes themselves. We are currently developing probabilistic models and theoretical performance bounds for this type of network, within the overall aim of designing network protocols that allow efficient opportunistic networks to emerge as a result of decisions taken autonomously by the participating nodes.

In bioinfomatics, development continues of complexity measures of genetic sequences in collaboration with Cardiff University's Institute of Medical Genetics. These measures have proved extremely interesting in their applications to analyzing the evolution of the vertebrate genome. Analysis of the local DNA sequence environment will further our understanding of the mechanisms of human gene mutations causing human inherited diseases. For example new regulatory DNA elements have been found by complexity analysis. The Cardiff based Human Gene Mutation Database is being used in these studies.

Heuristic and Metaheuristic Search

The group has also worked on various heuristic and metaheuristic algorithms to tackle problems involving hard combinatorial search. Applications include cutting, packing, and placement, timetabling and scheduling and supply chain optimization. Simple techniques that scale to large instances are of particular interest to the group and we have achieved some notable success in our recent work on vehicle routing, beating some tough literature benchmarks. In addition, we have developed simple but competitive techniques for multi-objective optimization.