Introduction
Welcome to my first official blog post! There are lots of interesting topics in statistics and operational research and it’s hard to pick one to talk about but I am going to start with uncertainty, particularly uncertainty in decision making.
There’s one thing for certain: uncertainty is everywhere. Whether that’s deciding how fast a virus spreads through a population or deciding between cooking dinner or ordering a takeaway (and if you get a takeaway, which one?). How do decision makers deal with uncertainty in order to make the best decision? With maths of course!
An Example
Say you are the manager of a company and it is up to you to decide which factories to open and how much product each factory produces in order to meet customer demand and reduce costs. For customers to get their orders as quick as possible, factories must be open and the product must be made before customers place their orders. Opening a factory comes with a cost and there’s also a (holding) cost for every excess unit of product made, along with transportation costs and costs for unmet demand.
The goal is to decide which factories to open and how much product to make at each factory whilst reducing costs and meeting demand. So let’s do this mathematically!
There’s a branch of mathematics called Optimisation where the goal is to find the best solution possible, given some pre-set conditions. For the problem above, the goal is to reduce costs so we say we want to minimise the total costs. Some of the constraints could be: the maximum amount of product produced at a factory can be no more than the maximum capacity of the factory (which makes sense), the amount of excess product at any factory is equal to the amount of product produced at the factory minus the amount of product sent to the customer (which also makes sense), etc. Okay great, but how do we incorporate the uncertainty of customer demand into our model?
Dealing with Uncertainty
In an ideal world, we would know exactly how much product the customers want before any orders are placed so we could open the necessary number of factories and produce the exact amount of product. In this kind world where all the information is known, we call this a deterministic optimisation problem because we know all the values for every variable, every variable is determined and there is no uncertainty. There are many methods for solving a deterministic optimisation problems, such as the Revised Simplex Method and Branch-and-Bound, as well as programming solvers that can solve optimisation problems using these methods, like Gurobi.
Unfortunately, in real life customer demand is unknown and can’t be known with 100% certainty. But not all is lost. When there is an element of uncertainty in our problem, we can turn to stochastic optimisation, where stochastic (roughly) means randomness. This area specifically deals with incorporating uncertainty into mathematical optimisation. For this blog post, we will focus on what is called a two-stage stochastic optimisation problem with recourse.
The factory opening problem is an example of a two-stage problem with recourse. There are various decisions that need to be made so we split these into two-stages. First-stage decisions are ones that need to be made and are not affected the uncertainty in the problem, e.g. deciding on which factories to open and how much each factory produces before customer demand is known. Second-stage decisions are decisions that can be made once we get more information about the uncertainty, e.g. once customer demand is known we can decide how much product to send from factory A to customer X. The term “recourse” is used to highlight the fact that the second stage decision variables adapt and vary depending on what information is provided from the uncertainty.
Solving a model with uncertainty
Fantastic! Now we know how to model decision making problems and how to include uncertainty into these models. But we still need to address the elephant in the room, how do we actually solve a problem when some variables are unknown? One answer to this is sampling. Assume that customer demand follows some probability distribution Fi for each customer, i = 1, … ,n, and assume each customer has a probability, pi, of placing an order. If a customer does place an order, draw a random sample for the amount they order. Do this n times for all n customers. We now have a set of n generated samples, and we call this set a scenario.
So instead of some uncertain random variable that could take on any value, we now have actual values for what the customer demand is. Now the problem turns from a stochastic optimisation problem to a deterministic optimisation problem which, as stated before, is easier to solve. Sampling from a distribution isn’t exact, so our solution won’t be accurate. This is why we generate multiple scenarios and take an average from these in order to get a more accurate solution (read the paper below on assessing solution quality).
Conclusion
So welcome to the world of optimisation, where we use mathematics to (try and) make the best decision possible. The topic of stochastic optimisation goes on, with work done in improving all aspects of this optimisation process. For example, there are different algorithms for solving optimisation problems, such as Benders decomposition which takes advantage of the structure of the model and increases computational efficiency (solves problems faster). The sampling method described above is called independent sampling but there are other methods of sampling, such as Antithetic Variate (AV) sampling and Latin Hypercube (LH) sampling, which aim to improve the quality of the solution produced from the model.
Every problem is different and requires different methods and solutions, so there is no “one shoe fits all” approach or method. However, the process of learning from previous work and improving on it is what makes research interesting! If you want to read more into the topic, have a look through the papers below.
Further Reading
Stochastic Programming: Optimisation When Uncertainty Matters – Julia L. Higle
Evaluation of scenario-generation methods for stochastic programming – Michal Kaut and Stein W. Wallace
The impact of sampling methods on bias and variance in stochastic linear programs – Michael B. Freimer, Jeffrey T. Linderoth, Douglas J. Thomas
Benders decomposition – Z Caner Taşkin