Stochastic Optimization seeks the best decision in a scenario involving random events, those that depend on chance, whether those events are product prices, task durations, the number of people queueing at an ATM, the number of breakdowns in a fleet of trucks, or even the adoption of regulations.
Stochastic? Are you trying to scare me?
“Stochastic” is an especially dreaded word, and we know it has gained a bad reputation through its treatment in most specialized languages, at the hands of experts who want to jealously guard their secrets. This is true for legal and economic language, and closer to our work, rumor has it that the creator of the C++ language made it so difficult in order to differentiate good programmers from bad, a neat trick. In reality, the word “stochastic” is not dangerous, it simply means random, depending on chance. The idea is pretty simple, but as an adjective it can complicate any discipline.
Stochastic Optimization Problems
Stochastic optimization problems are generally much more complex than those that do not involve random chance, mainly because random chance implies that we do not have a single scenario to optimize, but rather a set of possible scenarios. For example, if we want to optimize the design of a power distribution network, we will be working in an environment of uncertainty, in which we don’t know what the actual demand for energy will be at the time the network is used. Instead of data on the demand we have an estimate, perhaps a finite set of possible demands, each with an associated probability. With this we can already see that the business world is full of stochastic problems. What is the usual approach for solving them?
In scenarios involving simple decisions, or in other words those with few decision variables and few states, it is possible to explicitly list all the possibilities using decision trees that are also very intuitive. We then choose the decision with the greatest expected profit.
For example, a woman learns at the hairdresser that there is a 50% chance of rain and she must decide whether or not to buy a low quality umbrella.
- If she buys the umbrella:
- If it rains (probability 0.5) she will have spent €5 on a low quality umbrella.
- If it doesn’t rain she will have spent the same €5.
- If she doesn’t buy the umbrella:
- If it rains she will have to return to the salon and pay another €15.
- If it doesn’t rain she will not have spent anything.
In conclusion, if she buys the umbrella the expected loss is €5 and if she doesn’t buy it this figure is €7.5. If the woman is in her right mind she should buy the umbrella. Although a priori it seems to be pessimistic and wasteful behavior, it would be the most beneficial.
However, if the problem is more complicated we might end up simplifying it, for example using the expected scenario, or the most likely scenario, since these are deterministic and allow us to solve the problem using conventional optimization. For example, in the case of planning a power distribution network, demand could be set at the level estimated by the National Institute of Statistics, without stopping to assess the potential impact of unexpectedly high or low demand.
At other times, to save themselves a headache, people directly simplify the business. This is what Alexander the Great did with the famous Gordian knot, or to give a more familiar and contemporary example, it means adding another cashier position in a supermarket instead of creating a single queue.
In many cases these simplifications can lead to decisions that are not the most beneficial.
Stochastic Optimization
Although it is thought that this discipline was born in the 1950s with Dantzig and Beale, historically optimization has had enough to do limiting itself to non-stochastic problems, essentially because of the complexity involved in stochastic problems. Addressing real issues remains impossible in many cases, but advances in computing power and the development of optimization techniques mean that we can solve problems that were unthinkable until recently.
In addition, at times simply using a stochastic approach can greatly improve the quality of the solution, resulting in outcomes such as cost savings, improved service and increased profits, all factors worthy of consideration.
So, what is stochastic optimization?
An optimization problem has:
- a number of variables or decisions to be taken
- a number of restrictions that limit those decisions
- and an objective function, a measure of cost or quality of the set of decisions taken.
The data associated with the constraints and the objective function values are usually known. However, what if these values are given by random events? Then the problem is a stochastic optimization problem.
There are two particularly uncomfortable questions:
What happens to feasibility when the constraints are random?
A solution is feasible if it satisfies all the constraints, but with random constraints we cannot talk strictly about feasibility, but instead about the probability that a certain solution is feasible. So in the problem of planning the power distribution network, one restriction could be “the capacity of the distribution network must be greater than or equal to demand,”, but if demand turns out to be unexpectedly high we may not be able to meet this constraint.
How to redefine the objective function?
The answer to this question is less obvious, we could redefine the objective function as the expected value of the previous objective function, but it could be more interesting to reduce the risk of the decision using the worst case scenario (given a solution, what is the worst that can happen?).
Generally, this type of problem has been tackled using linear programming, which is why we also talk about Stochastic Programming.
What is so complicated about these problems?
The complexity of these problems arises from their size. Consider the seemingly simple case of the woman leaving the hairdresser. Let’s assume that she also has to decide whether to go by bus or on foot to complete an errand. Each new random variable (traffic conditions, strikes, demonstrations, what time does it close, 8pm or 8.30pm?) and each new decision (go by bus, walk the long way round to shelter under arcades) multiplies the possibilities. Instead of considering four possible outcomes we need to consider dozens or hundreds. If we continue to consider the elements of uncertainty that could affect the woman, the number of possible outcomes increases exponentially.
Let us now turn to the problem of planning the power distribution network, where demand is random, future energy prices are random, the wind power produced is random, as are fuel prices. The result of any decision in this context will depend on what happens with each of these random events, so there are millions of possible scenarios!
Luckily for us there are techniques to solve these problems more efficiently, such as the Dantzig-Wolfe decomposition, Bender’s Decomposition and Column Generation, but that is a topic for another post.
Conclusion
Most real problems are stochastic in nature, there are few businesses in which all the data are known in advance, we cannot keep avoiding them, so… why simplify the problem and avoid the use of advanced optimization?
Stochastic optimization allows us to efficiently tackle problems that have until now been solved using “intuition”, “common sense”, or with the argument “it has always been done this way”. It can provide solutions that give us a clear advantage over our competitors. It is always worth a try.