During Weeks 7-10 of the STOR-i MRes, each week is structured as a “Sprint” on a specific topic. Each week starts with an introductory lecture on a given topic, a research task is set by the Sprint leader, we are randomly assigned into groups, and we have until Thursday afternoon to present our findings and answer questions on what we have presented. The Sprints give a good first taste of what it’s like to be a researcher in a group setting, and provide a good environment to bounce ideas off each other and work collaboratively. Following the Sprints, each student chooses the topic they found most interesting, and writes a short individual report on that topic. My topic of choice was Optimisation under Uncertainty, a topic that combines aspects of both Statistics and Operational Research. But before I can talk about that, I must answer the question: what IS Operational Research?
While everyone knows what statistics is, at least to some extent, nowhere near as many people know what is meant by Operational Research. The Operational Research Society gives the following definition:
Operational Research is a scientific approach to the solution of problems in the management of complex systems that enables decision makers to make better decisions.
The OR Society
In other words, Operational Research is a rigorous mathematical approach to decision-making in the real world. In the broadest sense, we have a collection of things we control or actions we can take, some outcome value we either want to maximise (such as profit) or minimise (such as unfairness), and some relationship between the two. Decisions might be a one-off big decision, such as a company plan for the next few years, or a sequence of decisions, to adapt to an ever-changing environment. The relationship between decisions and outcomes might be deterministic, so the same decisions always have the same outcome, or they might be random.
To give an example, consider a company that makes some number of products, has a finite amount of resources, and wants to maximise profit by deciding how much of each product to make. If we assume everything is fixed, this is a Deterministic Optimisation Problem, and is one of the first types of Optimisation problem we encounter during the first five weeks of the STOR-i MRes. Due to the linear relationships found in the problem, it ends up being very easy to solve computationally. Now instead consider that this problem is really subject to fluctuations in the market; your stock levels fluctuate, the profit from each item sold changes with market prices, demand for the product changes with competition, and so on. To incorporate these types of uncertainty into the problem, we must turn our attention to the field of Stochastic Optimisation.
The goal of Stochastic Optimisation is to make a decision that optimises some outcome that is subject to randomness. In the strictest sense, this is impossible. We cannot choose one decision that will work as well as possible all of the time in a random scenario. Instead, we seek to find a decision that works “quite well” most of the time. To do this, we replace our random outcome function with a fixed deterministic function that represents how the outcome usually behaves. In the probabilistic sense, we replace the random function by its Expectation, or average in laymens’ terms. This leads to a new additional problem, that this expected outcome function is almost always going to be highly non-linear and non-convex (only one optimum), if not completely intractable (impossible to write out), and therefore very difficult to solve. Our solution to this problem is to instead approximate the expectation by using a sample average.
Rather than trying to incorporate all of our theoretical knowledge of the distribution of our sources of randomness (say, market fluctuations), we instead randomly generate examples (or use actual data) of different states of our source of randomness (called scenarios), find the average of the outcome functions under these different scenarios, and treat that as our expected outcome function. As this is a linear combination (weighted sum) of linear functions (our original outcome function under a given scenario), our new outcome function is also linear and therefore relatively easy to solve for. A downside of this approach is that, if you do this for something like 100 scenarios, the resulting linear program becomes 100 times larger by incorporating all the necessary variables of the 100 subproblems, meaning it will take far longer for a computer to produce a solution.
An intuitive understanding of what the solution achieves is that it finds a good middle ground solution for all the different scenarios presented, and should then hopefully be a good middle ground solution overall. The quality of the solution therefore depends on how representative the set of scenarios given is of the whole space of scenarios. This leads to an area known as Scenario Generation, which is one of the research interests of Dr. Jamie Fairbrother, who was the Sprint leader for this topic. A scenario generation technique I looked into is known as Latin Hypercube Sampling, which ensures that at least some samples are taken from areas of the scenario space that have a lower probability, ensuring that some more extreme situations are incorporated into the problem. The technique also more generally assures that a sample is representative by partitioning the scenario space into n spaces equal in probability (n is the sample size), and taking a random sample from each space (this gets more complicated when you have multiple sources of randomness).
As an extension, we can also consider whether or not Expectation is a good summary statistic in this situation. The formulation discussed is known as a “risk-neutral” approach, and is only concerned with the average performance. However, in situations more concerned with safety and security, such as a nuclear reactor, this might not be a good enough approach. We might instead wish to optimise for strict worst-case performance, or something like 99.9% worst-case performance. These approaches are called “risk-averse”, and are included here as an example of the different ways in which stochastic optimisation can be approached. In these situations, scenario generation is even more important, as we need to ensure that we have enough samples in this (for example) 99.9% worst-case scenario.
This concludes a high-level overview of the topic covered in my Sprint report. I hope it gave a good entry-level overview of the kind of problems encountered in Optimisation. While I’ve tried to keep the raw maths to a minimum here, if you are interested in Optimisation, it’s probably worth mentioning that the actual formulations of problems can sometimes look a bit cumbersome, with lots of variables to keep track of everything going on in the problem. However, when you break everything down, it isn’t too hard to understand. I’ll also mention that, while I’ve been discussing products and profits throughout this post for simplicity’s sake, the application I actually looked into was the assignment of extra capacity to a communications network to minimise expected unmet demand on that network. Quite a lot of surprising things like network routing can be modelled as an optimisation problem, which is what makes it such a powerful field.