Optimisation - Overview

Last Updated on Friday, 19 June 2009 17:58

Optimisation is concerned with methods for finding the ‘best’ option when one is faced with a huge range of possible options.  More formally, it deals with maximising (or minimising) a function of some decision variables, subject to various constraints.  It is an inter-disciplinary field, lying at the interface between Operational Research, Computer Science and Applied Mathematics.  Moreover, it has applications in many other fields, including Physics, Chemistry, Biology, Statistics, Engineering and Finance.

This research cluster focuses on discrete and non-linear optimisation, and the connections between them.  Discrete (or combinatorial) optimisation is concerned with problems in which some or all of the decision variables are restricted to take values from a finite set.  Non-linear optimisation, on the other hand, is concerned with continuous problems in which the objective function and/or constraints are non-linear.  These two fields progressed largely independently in the past, but recently there has been increased interaction between them.

One topic to be explored is the application of techniques from one field to problems in the other.  There already exists a body of literature on the use of non-linear techniques (such as semidefinite programming or interior-point methods) to compute bounds for discrete problems.  It seems however that more could be done in that direction.  Perhaps more interestingly, it may be possible to work in the reverse direction, applying discrete techniques (such as polyhedral theory) to continuous problems.

Another topic to be explored is problems that have both discrete and non-linear aspects simultaneously.  Such problems arise frequently, for example, in the utilities and process industries.  (The figure on the right is an attempt to represent one such problem, in which the constraints are linear, the variables are constrained to be integers, and the objective function is quadratic and convex.)  Although some progress has already been made on certain kinds of discrete non-linear optimisation problems, there is a need for improved theory, algorithms and software.  As well as exact algorithms, heuristic techniques are also of interest, so there may be some interaction between this research cluster and the one concerned with heuristic understanding.