Using Robust Optimisation and Mixed Integer Programming to manage Singapore’s water resources — Part III
The reader may need some basic knowledge of probability to understand the content in this segment.
Written by: Dr Loke Gar Goei
Data Scientists: Dr Loke Gar Goei, Chin Chii Yeh, Tan Kai Wei
PUB Engineers: Ashley Ng, Daniel John Tan, Hariharan Ramasamy
Visual Designer: Glenn Goh
If you have missed out Part I and Part II, please click on the respective links.
Robust Optimisation
In a perfect world, we have full information about our parameters. In reality, we don’t actually know that, even though we may know how it may vary based on our past data. We call this uncertainty and we say that the parameter is a random variable (values depend on outcomes of a random phenomenon).
Planning without care of uncertainty can be dangerous. Let us look at this example. Suppose John is an amateur fund manager. His client estimates that she will have $10 million to invest in the coming year. John is considering between two funds — Fund A, which requires $3 million investment, with returns of $2 million in a year’s time, and Fund B, which requires $10 million investment, with returns of $7 million in a year’s time. He may buy as many units of each fund as he likes.
John decides that he would go with 1 lot of Fund B, as it gives the highest returns of $7 million (as opposed to $6 million returns from 3 lots of Fund A). However, as the year closes, his client realises that she only has $9.5 million and is unable to raise enough capital for the last $0.5 million! John wishes that he could have gone for the more conservative approach of investing in 3 lots of Fund A.
This example illustrates a few principles:
1. If one ignores uncertainty, the proposed optimal solution may sometimes not even be feasible (John did not have enough for Fund B), once the uncertainty materialised!
2. By being slightly conservative (hence being slightly less than optimal), we can be assured that the solution would be robust to this uncertainty.
Techniques that address such problems are broadly referred to as Robust Optimisation. As it turns out, Singapore is one of the leading global centres for research in Robust Optimisation, with at least 2 professors who are ranked within the top 10 in the world for publication in major journals.
The interested (and technically competent) reader may attempt a reading of the papers in the footnote. We will nonetheless, be going through the key ideas explored in this project. The technique used in this project is known as Satisficing¹.
Key Ideas
The key idea of robust optimisation loosely speaking is about being slightly more conservative so as to reduce the impact that uncertainties have on your decisions.
We can apply the concepts of uncertainty to the constraints we use in linear programming. For instance, ensuring that the total amount of resources (x_i) available at a locality i is going to be sufficient to fulfill the demand for that resource at that locality (d_i). This can be represented by the inequality:
Unfortunately, the demand d_i is an uncertain random variable. If d_i is very large, then this inequality might not be satisfied. As such, we can only talk about the probability, P, that this inequality would be satisfied. We write this as follows:
We would like this probability to be 1, which means that the demand would always be fulfilled. We want the probability to be large and near 1.
In general, any expression involving probabilities is very difficult to work with on a computer. I won’t dwell too much on that; you can take my word on it (or a more legit guy’s word² on it). This means that we have to think about things in a different manner.
Step 1
Trying to have a large probability that demand is fulfilled, is the same as trying to keep the probability where demand is not fulfilled really tiny. Consider this:
This is the probability where we do not just fulfill the demand, we actually run short of it by at least 𝜑 (assumed positive)! At least. If we can say that this probability is small for any 𝜑, then that must mean that we fulfill the demand with high probability. Sounds good?
Step 2
What does it mean to say that the probability is small? One way is if it is always smaller than some upper bound. Let’s try to do just that:
Step 3
It would have been kind of cool if we can proceed with the very last step and discard all of the other expectations to get just one constant exp(-𝜑/k). Of course, the computation in Step 2 would all work out if we could somehow guarantee that our solution obeys
Or equivalently,
This expression has some meaning in the context of risk in finance⁴! But let’s put fanboydom down for a while.
The way to guarantee something in optimisation is to set it as a constraint. Now x_i is the amount of available resources (at the beginning, as well as any additional resources produced). All of that has totally nothing to do with the expectation. So we can happily bring it out of the expectations.
The only part left is d_i, which is the demand. Historical data would be used to compute the expectation. In the end, we will have a constraint like
That looks like it will fit nicely into a linear programming model.
Step 4 — What’s k?
The sharp reader would notice that the k magically appeared and disappeared! In reality, k did not disappear. It is still in the “stuff involving the demand”.
What k represents is the risk level. Recall that we said the chance of an unlikely event happening by at least 𝜑 is no more than exp(- 𝜑/k). So the smaller k is, the lower the chance of the unlikely event happening! That’s nice. Unfortunately, the smaller k is, the larger the term for the “stuff involving the demand”. At some point, the inequality cannot ever be satisfied by any decisions we make on x_i. In other words, it becomes infeasible.
As such, our goal is to find the smallest k, ie. the lowest chance of the unlikely event happening, such that it is still possible to find some feasible decision. This is the optimisation problem we solve:
Now imagine the above being applied back to the case of water management, where demand for water, for instance, is a random variable. We would need to be robust to this uncertainty, and produce enough potable water to meet whatever demand of water that actually unfolds.
For those who are curious about the pseudo-algorithm,
Summary
Neat, eh? Turns out this is not too hard to write code for as well, as seen in Part II. Of course, we ditched a lot of details in this process, but do not hesitate to write to us by commenting below if you want to know more about the model 🙂
If you’re passionate about using tech to help the public, do follow us on Medium and join our team. We are hiring Data Scientists, Software Engineers, and DevOps Engineers. Send your resume to us at recruit@dsaid.gov.sg!
[1] Jaillet, P., S. D. Jena, T. S. Ng and M. Sim (2016). Satisficing Awakens: Models to Mitigate Uncertainty. Available online at http://www.optimization-online.org/DB_HTML/2016/01/5310.html
[2] Nemirovski, A. and A. Shapiro (2006). Convex Approximations of Chance Constrained Programs. SIAM Journal on Optimization 17(4):969–996.
[3]https://en.wikipedia.org/wiki/Markov%27s_inequality
[4] Aumann, R. J. and R. Serrano (2008). An Economic Index of Riskiness. Journal of Political Economy 116(5):810–836. Available online at https://www.econstor.eu/bitstream/10419/80128/1/522867952.pdf
