Four Steps to Robustify your Linear Program
And how that can help you with baking cakes
In the first year of uni, I was introduced to linear programming, which opened a whole new world to me. The professors taught us to model all kinds of problems in a broad range of fields using an LP. This appealed to me because it can give an optimal solution – if the problem is small enough – and is relatively easy to construct. Being overly enthusiastic about this method, I used it in almost every uni project and even ended up basing my whole thesis on an LP.
It was only in the second year of my master’s that I realized that I had never learned how to take uncertainty into account when constructing LPs. When I look at it now, that feels pretty silly. After all, how often have you heard about data being 100% accurate or studies with zero estimation errors in their experiments? Probably never, right? Basic LPs are usually based on exact input data and don’t take into account that those input values might not be completely accurate. These models lack robustness against different worst-case scenarios. For example, if you are baking a cake, but your consumption of ingredients differs every time due to waste, you might want to have a solution that will always work, no matter the spillage. If you want to implement only a bit more sophisticated mathematical models including uncertainty, you will probably need a robust version of your LP.
Fortunately enough for me, I took a class in mathematical optimization in which they elaborately dealt with this topic. One of the take-aways was that the robustification of an LP can be boiled down to 4 steps, which I will explain in this post.
Definition
First of all, what does robust mean? A robust solution stays, to some extent, feasible – and does not critically deteriorate – against variations of your input data. In other words: it optimizes your worst-case scenario. In terms of the cake baking example, you always want to be able to bake a cake, no matter the spillage.
The Basic LP
Let’s say that we only need 4 ingredients to bake a cake: milk, eggs, flour and sugar and that our bakery sells two kinds of cake. They yield a profit of 12 and 9 dollars, respectively, yet, have different recipes. The first cake requires one unit of milk and flour and four of sugar. The second one needs one unit of eggs and flour and two of sugar. Since the bakery is rather small, there’s only 1000 units of milk, 1500 units of eggs, 1750 units of flour and 4800 units of sugar available every day.
The question is: how many cakes of each type should we bake in order to maximize our profit without exceeding the maximum amount of ingredients? Below, you can find the corresponding LP.
Since the cakes in our bakery are manually made, sometimes a bit of sugar is spilled. We want to keep that into account when deciding about our optimal baking strategy. The smart bakers want to determine the best possible production mix which stays feasible against fluctuations of the consumption of sugar. Yet, the aforementioned LP does not do that. Therefore, we need to add some uncertainty.
Uncertainty Sets
Uncertainty comes in many different kinds and flavors, but I will stick to the three basic uncertainty sets in this post:
- box uncertainty set (black)
- ellipsoidal (bal) uncertainty set (blue)
- polyhedral uncertainty set (orange)
An uncertainty set is the set of values which can be possibly taken by the uncertain parameters. In our example, there are two: one spillage parameter for each cake. Below, you can find the three uncertainty sets visualized.
As you can see, the box uncertainty set (indicated by black square) is the most conservative. After all, it covers the biggest area in the uncertainty state space. The corners of the square indicate that both uncertain parameters can have extreme values at the same time. This does not occur with ball uncertainty (indicated by the blue circle): the corners are not included. The polyhedral uncertainty set (indicated by the orange diamond) goes even further. Depending on your preference of conservatism, you could choose one of these sets for your own problem. For the sake of simplicity, we are taking the box uncertainty set in our example.
The Steps
In order to make an LP robust, four steps should be taken:
- Construct the Nominal Problem
- Construct the Adversary Problem
- Find the Dual of the Adversarial
- Plug the Dual in the Nominal Problem
Nominal Problem
The nominal problem is simply writing down your initial LP, which we have done a few paragraphs back. Yet, it is also necessary to identify the uncertain parameters, which we have not done so far. Below, you can see in red what has been changed: we have added the uncertain parameters. They come from a box uncertainty set, which is mathematically defined in the last line.
It is obvious that the most conservative values for both uncertain parameters amount to 0.1. Yet, for the sake of the example, I will explain how you can mathematically derive this.
Adversary Problem
Remember that we want to optimize our policy for the worst-case scenario. Therefore, we introduce an artificial opponent, whose goal it is to make your optimization terrible. Below, you can see in red how the opponent works. It wants to maximize the left hand side of the sugar constraint in order to make your optimal solution less good.
It is the red part that we want to focus on. We maximize the left hand side of the constraint, while ensuring that the constraints of the uncertainty set are not violated. You can see the resulting adversary problem below, which can be seen as the mathematical model of the "opponent".
Dual
Having found the adversary problem, it is time to construct the corresponding dual. If you’re new to the concept of primal and dual problems, have a look at this video. Below, you can find the dual problem of the adversarial.
Plug & Play
The dual problem can replace the red constraint in the nominal problem. The resulting robust LP is shown below:
The benefit of this LP is that its stays feasible against variations of the input data. The optimal baking strategy does not need to change if a bit of sugar is spilled. That makes mathematical modeling more realistic and therefore more applicable to real life examples.
The Takeaway
If the input data of your mathematical model are not accurate or reliable, it is worth robustifying your LP. This can be done in four steps:
- Construct the Nominal Problem
- Construct the Adversary Problem
- Find the Dual of the Adversarial
- Plug the Dual in the Nominal Problem
Yet, if you find this concept still rather vague, don’t worry. It’s already quite something that you have heard about it. And honestly, who needs an LP when baking a cake after all? Happy baking!
References
dr. A. Zocca & dr. R. Paradiso in the course Mathematical Optimization at Vrije Universiteit Amsterdam, 2021/2022.
Share This Article
Towards Data Science is a community publication. Submit your insights to reach our global audience and earn through the TDS Author Payment Program.
Write for TDS
