callback request

Search the site

Find out More

Optimisation

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 being 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 semi-definite 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 is possible to work in the reverse direction, applying discrete techniques (such as polyhedral theory or branch-and-cut) to continuous problems.

Another topic being 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 below is an attempt to represent one such problem.  The black lines represent linear constraints, the black dots represent feasible solutions, and the red ovals represent contour lines for a convex quadratic objective function.)

There are links between this research cluster and two other LANCS research clusters: the one on heuristic understanding, due to the fact that heuristics are often needed to solve large-scale optimisation problems, and the one on stochastic modelling, since some stochastic optimisation problems can, under certain assumptions, be converted into discrete and/or nonlinear optimisation problems.