Bridging the Gap

Bridging the Gap: Research Themes

This project will focus on four broad themes as described below, which are critically important and timely across a number of disciplines covered by EPSRC, including computer science, mathematics, engineering, chemistry, physics, and psychology. Each theme is championed and led by a Leader and a Co-leader from two different disciplines.

Theme 1: Multi-disciplinary Combinatorial Optimisation

Leader: Prof X. Yao, Co-leader: tbc

Optimisation is ubiquitous. Many real world problems are inherently difficult, e.g. Nondeterministic Polynomial-time hard (NP-hard) problems in combinatorial optimisation and non-linear programming problems (with non-linear constraints) in numerical optimisation. Heuristic methods often have to be used in practice. Unfortunately, most heuristic methods are not well understood currently, lacking sound theoretical foundation(s) to explain why and when various methods are successful for certain problems. In spite of successes in applying some heuristic methods to certain problems, such successes are not readily translated to other problems. Considerable experimental work has to be done in order to evaluate the effectiveness of different heuristics for different problems, due to the lack of a theory that explains why and how heuristics may be successfully applied for different problems.

There is an urgent need for mathematical tools and theoretical foundations for analysing heuristic methods/algorithms. The importance of such research has been pointed out by one of the most distinguished computer scientists in the world, Professor Papadimitriou, "developing the mathematical methodology for explaining and predicting the performance of heuristics is one of the most important challenges facing the fields of optimisation and algorithms today." Particular challenges often occur in noisy, dynamic systems, e.g., those arising from engineering, medical imaging and optimal control.

Some examples that collaborations may pursue include:
  • Managing the UK railway network in terms of operation and maintenance is an extremely complex operation and it has been realised in recent years that the best approach is to view the network as a whole as a complex system to which systems engineering techniques, e.g., adaptive optimisation techniques, should be applied.
  • Highway authorities and engineers in marginal winter climates are responsible for the precautionary salting of the road network in order to prevent frozen roads. The decision whether to salt the road network at marginal nights is a difficult problem. The consequences of making a wrong decision are serious, as untreated roads are a major hazard. However, if grit/salt is spread when it is not actually required, there are unnecessary financial and environmental costs.
  • Scheduling trains (particularly after an incident) and railway maintenance
  • Determination of physically-based unified constitutive equations from experimental data using efficient optimisation techniques. This is still an open problem for industry (Corus, Rolls Royce and Airbus).
  • Optimization of permutational isomers in bimetallic nanoparticles (nanoalloys).
  • Inversion problems (as optimisation problems) in medical imaging and image interpretation.

Theme 2: Conic Optimisation

Leader: Prof M Kocvara, Co-leader: Prof K Deb

In the last decades, linear programming (LP) has become an integral part of many industrial and decision-making processes. This progress went hand in hand with the development of very efficient and robust LP software. However, with the growing interest in optimisation, researchers in many scientific disciplines realised that they need to solve more general optimisation models than just LP. A natural extension of LP is the conic programming (CP) which includes several important problem classes, such as LP itself, quadratic programming, and semidefinite programming. CP has been rapidly developing in the last few years. In the latest International Symposium on Mathematical Programming in 2006, about one fourth of contributions were devoted to various aspects of CP.

Conic programming has applications in financial management, mechanical and civil engineering, medicine, chemical engineering, power management, computer science, electrical engineering and many others. These include, for instance, portfolio optimisation, robust optimisation, machine learning, structural optimisation, limit analysis, optimal control, combinatorial optimisation, image recognition, and others. Also subproblems in algorithms used for solving other complex optimisation problems, e.g., global and mixed-integer optimisation problems, can be formulated as CPs. The development of the CP algorithms and software is still in the "academic" phase, though, and by far did not reach the robustness and efficiency of LP solvers. The many research challenges of CP include:

  • Development of CP algorithms and software for large and very large scale linear conic problems coming from different applications, utilising special data structure of these problems.
  • Development of algorithms for nonlinear CP. This is a completely new discipline in mathematical optimisation and big progress is expected here in the coming years.
  • Development of various CP relaxations or approximations of highly complex nonconvex and mixed-integer optimisation problems.
  • Development of mathematical models of problems arising in various applications and formulation of these models as (nonlinear) CP problems.
The last point implies huge potential for interdisciplinary collaboration. It turns out that many difficult and seemingly impossible to solve problems can be formulated as CPs and solved, sometimes very efficiently, by the corresponding tools. Many researchers in various scientific disciplines are just not aware of this fact, due to the relative novelty of CP.

Theme 3: Advanced Data Analysis and Data Mining

Leader: Prof Z Kourtzi, Co-leader: Prof. P. Watkins

The rapid advances in ICT have led to an explosion of the amount of data collected in engineering and physical sciences. There has been a constant struggle for computer scientists, statisticians, mathematicians, engineers and life science researchers to analyse and mine the huge amount of data. Although researchers in different disciplines have their own tricks of the trade, more systematic and principled approaches are needed through synergistic research effort by a research team with different expertise and backgrounds. There are many examples of such a research challenge, including:
  • Recent advances in magnetic resonance physics have provided the unique opportunity to study the human brain at work in real time using a combination of multimodal imaging techniques (MRI, EEG, MEG). However, progress in unravelling the brain architecture that mediates human behaviour depends critically on the development of novel unified algorithmic approaches for mining these rich and complex biological signals. As well as enhancing our understanding of the neural basis of human behaviour, these theoretical developments may provide novel formulations to advance computational algorithms based on biophysical models.
  • In particular, predictive modelling is necessary for efficient decoding of the multitude of information sources derived from multimodal imaging data in conjunction with human behaviour. Multidisciplinary work by computer scientists, mathematicians, neuroscientists and psychologists are urgently needed to develop novel approaches that can handle large and complex data sets.
  • Optimising and constraining computational algorithms in a probabilistic manner that is characteristic of the behaviour of biological systems (human observers, neural responses) and will allow closer comparison of machine and human classification performance. These theoretical developments will provide important advances in both neuroscience and computational optimisation: while providing powerful tools for characterising the neural representations that guide human decisions, they will provide insights for further development of these algorithms and their implementation in biologically-inspired artificial systems (e.g. systems for face, fingerprint or hand-writing recognition, gene or tumour classification).
  • Similar data analysis and data mining challenges exist in physics as well. In order to investigate top quark production, a sample of events is isolated which match the predicted characteristics of top quark decays in order to measure the top quark properties. Samples of simulated detector data for top quarks and all the other expected processes are used to optimise the selection of top quark (signal) events compared to other processes (background). This separation can be based on simple cuts on each variable or more complex methods to improve the separation. In the latter case it may be much harder to reliably estimate the uncertainties in the method. Searches for new massive particles and the precise measurement of particle properties also rely on these separation techniques. Of course the data samples are very large and many of the most interesting processes are very rare and so efficient data mining techniques are of great interest.

Theme 4: High-performance Computing for Modelling Complex Systems

Leader: Prof A Chan, Co-leader: Prof E Claridge

Many real world problems are large and complex. They pose specific challenges to both the application fields and high-performance computing. Given Birmingham's excellent computing infrastructure, including a 2000-CPU cluster and access to the national Grid, we are ideally placed to tackle some of the new challenges in modelling and simulating complex systems in engineering, chemistry, computational psychology, and social systems. Selected examples include:
  • Regionalisation of rainfall runoff model has been a challenge to civil engineers for years. The problem is based on rainfall runoff data of hundreds to thousands of gauged catchments. The data are imprecise and the volume is large. The first task is to find a suitable model through efficient algorithms. Issues at the model selection include noise, over-parameterisation, physical or generic parameters, and choice of independent variables. After the choice of model, advanced multi-objective optimization is needed to find the optimal set of parameters. Because of the amount of computation and data involved, high-performance computing is essential. Advanced modelling techniques on parallel and distributed computing systems need to be studied.
  • Finding upper and lower bounds of failure load in structures is another typical challenge in mechanical and civil engineering involving the solution of a large set (tens of millions degrees of freedom for 3D structure) of equations with constraints. No satisfactory solutions exist at present.
  • Predicting spring-back in sheet metal forming is still a great challenge. None of the methods available in the world can be used to predict spring-back in sheet metal forming accurately, since so many parameters affect the results. However, in industry, engineers and technicians have got significant experience to estimate the amount of spring-back and have got empirical methods to compensate for spring-back in forming different shapes of sheet metal panels, although they could not achieve first-time-right. The development of a model (or models) to capture their expertise and experience has become increasingly urgent due to the ageing problems in the industry. The combination of the top-down knowledge-based approach and bottom-up data-driving modelling would be a promising direction given the availability of advanced computing power.
  • Modelling complex systems is also a challenge in computational psychology. Although it is a different discipline from engineering, its modelling problems share many similarities with those in engineering from the computational point of view. Classically cognitive psychology theorises about experimental evidence in a qualitative way. More recently, however, there has been an increasing development of computational models of experimental results. These models are often more clearly defined and more detailed than their qualitative counter parts. Typically, they imitate the neural network structure of the brain and therefore consist of a large number of non-linear differential equations. The parameterisation of these systems require the solution of a complex optimization problem fitting the model to a broad range of types of data, e.g. behavioural data (reaction times, accuracy), electrophysiological data, etc