Motivational example: fröccs
A continuous decision problem for motivation, and to discuss basic concepts and principles
- Prerequisites
Ányos Jedlik was a famous Hungarian engineer/priest, who is mostly known for the invention of the dynamo, and a machine to efficiently produce carbonated water. According to some legends, He was the first to come up with the idea of mixing this water with white whine to make a refreshing drink. The resultant beverage is called Fröccs, or Spritzer in some German speaking countries.
Disclaimer: Writing "carbonated water" every time below would be a drag, so I'll just use the term soda instead. I'm fully aware, that in some countries this could mean coke or other fizzy drinks, so please be ware, and don't start mixing coke with white wine. (Mix it with red wine if you must, to get a Vadász.)
Problem description
Imagine, that we are the managers of a pub, that sells only the following varieties of fröccs with the listed prices below:
| Name | Translation | Wine (dl) | Soda (dl) | Price (HUF) |
|---|---|---|---|---|
| Kisfröccs | Small fröccs | 1 | 1 | 110 |
| Nagyfröccs | Large fröccs | 2 | 1 | 200 |
| Hosszúlépés | Long step | 1 | 2 | 120 |
| Házmester | Housekeeper | 3 | 2 | 260 |
| Viceházmester | Vice-Housekeeper | 2 | 3 | 200 |
| Krúdy fröccs | Krúdy fröccs | 9 | 1 | 800 |
| Sóherfröccs | Stingy fröccs | 1 | 9 | 200 |
| Puskás fröccs | Puskás fröccs | 6 | 3 | 550 |
You may be unfamiliar with the measurement unit of deciliter (dl), that equals to a tenth of a liter, however, if you visit Hungary, the portion for wine, soda, or other drinks will usually be measured in that. (Except for strong alcoholic drinks, that use centiliter (cl).) As you can see, some of these have cultural references as well, the Puskás fröccs pays respect to a famous football match, that Hungary won against England in 1953. If you ever try fröccs in Hungary, please keep in mind that the prices vary from place to place a lot, these are just estimated prices for a small village pub in 2018. Also, there are a lot of other variants, but we will stick to only this 8 now.
After this cultural detour, let's get back on track and define our optimization problem: we have a fixed stock of 100 liters of wine and 150 liters of soda for a day, and want to achieve maximal profit. We can assume a few tings:
- The guests will ask us what to drink
- Our guests will always remain thirsty
- The guests even accept "partial" servings as well, e.g., we can sell them a half Krúdy fröccs for 400 HUF
I'm well aware that this is a very ideal and non-realistic example, but it will serve us well for now. Also, the profit value, that we determine this way will be a strict upper bound on the real profit that we can get in a real case scenario where these assumptions are not met.
Trial and error approach
Similarly to the festivals example, try to find a good solution by hand first. Do it either on paper, excel, or use this simple tool below.
Applying the ideas from the festivals example
If you don't remember them, follow the link above, and after re-reading it, try to figure out yourself, which ideas can be used for this example, and which can not.
Brute force approach
Our third assumption above was to allow "proportional servings" of these beverages. It is easy to see, that this results in an infinitely large solution set. If only rational numbers are allowed, than "just" countably infinite, otherwise, if irrational proportions are also allowed, then the cardinality of the set of solutions is the same as that of the real numbers. Either way, no brute force algorithm can cover all that.
Greedy approach
A greedy approach can be constructed to probably any problem, and this one is not an exception either. Several variations could be designed, just a few example:
- The Krúdy fröccs is the most expensive one, sell as much as possible from that
- Based on the wine/price ratio, the Sóherfröccs is the most expensive, sell as much as possible from that one
- Since we have 1.5 times as many soda as wine, wine is 3/2 more "valuable resource" than soda. Based on this, we could calculate a price/ingredient value ratio for all of them, and produce the most from the one that is on the top of that list.
Generally, a greedy algorithm would continue with something like "and then select the second most valuable item, and sell as much as possible from that, and continue this until we can still sell something". Since here we only have 2 ingredients, and both of them are required by all of the fröccs types, there could be no such iteration. This type of iterative approach would have meaning for more ingredients and products, where the products do not always require all of the ingredients in some proportion.
Similarly to the festivals problem, the greedy approach will not necessarily provide an optimal solution here either.
Simplify the problem by presolve
Some types above are just not worth to sell. Try to figure out which ones yourself, and why, then click on the button to check if you have discovered them all. Show unprofitable fröccs types
The simplest to observe is probably the Puskás fröccs, as it is equivalent of selling 3 Nagyfröccs. The latter would make 600 HUF profit, while the former costs only 550.
Házmester is a slightly more difficult to see. It is equivalent of selling a Kisfröccs and a Nagyfröccs. While the combination of those two would bring us 310 HUF, Házmester does only 260. In a similar fashion, instead of selling Viceházmester, it is better to sell a Kisfröccs and a Hosszúlépés, as it would bring 230 HUF instead of 200.
The only types that remain are the following ones:
| Name | Wine (dl) | Soda (dl) | Price (HUF) |
|---|---|---|---|
| Kisfröccs | 1 | 1 | 110 |
| Nagyfröccs | 2 | 1 | 200 |
| Hosszúlépés | 1 | 2 | 120 |
| Krúdy fröccs | 9 | 1 | 800 |
| Sóherfröccs | 1 | 9 | 200 |
Another easy thing to observe is, that if we sell a single Nagyfröccs ad Hosszúlépés, that would require 3 dl of both wine and soda, and produce 320 HUF income. That is less then selling 3 portions of Kisfröccs for 330, that would take the same amount of ingredients. This means, that Nagyfröccs and Hosszúlépés will definitely not sold together in an optimal solution. Similarly, 10 Kisfröccs is better than a Krúdy fröccs and a Sóherfröccs.
As a result, we know, that in the optimal solution at most 3 different types of fröccs will be sold, but we can not eliminate yet any more rows from the table.
What we did when we eliminated some fröccs types was to "cook up" a recipe, how it can be made from other types in a more profitable way. If we order the types based on wine / soda ratio, we get the following table:
| Name | Wine/Soda ratio | Wine (dl) | Soda (dl) | Price (HUF) |
|---|---|---|---|---|
| Krúdy fröccs | 9 | 9 | 1 | 800 |
| Nagyfröccs | 2 | 2 | 1 | 200 |
| Kisfröccs | 1 | 1 | 1 | 110 |
| Hosszúlépés | 0.5 | 1 | 2 | 120 |
| Sóherfröccs | 0.111 | 1 | 9 | 200 |
It is simple to see, that any fröccs type can be "cooked up" from a stronger and from a weaker beverage. If there are 3 types in decreasing wine/soda ratio: A, B, C, then there are non-negative integers \(\lambda_A,\lambda_C\) such that \(\lambda_A\cdot A + \lambda_C \cdot C = B\).
But what does A,B,C exactly mean in this equation? What we want to express is the amount of ingredients that they take. So they are basically ingredient vectors. Let's look at an example with Krúdy fröccs (A), Nagyfröccs (B), and Kisfröccs (C) as an example: \[ (9,1)\cdot\lambda_{A}+(1,1)\cdot\lambda_{C}=(2,1)\]
Which basically results in the following equation system: \[ \begin{array}{rcl} 9\cdot\lambda_{A}+1\cdot\lambda_{C} & = & 2\\ 1\cdot\lambda_{A}+1\cdot\lambda_{C} & = & 1\\ \end{array} \]
The solution to this system is \(\lambda_{A}=\frac{1}{8}\) and \(\lambda_{C}=\frac{7}{8}\). This means, that a Nagyfröccs can be made up by 1/8 Krúdy fröccs, and 7/8 Kisfröccs. The profit from that would be \(\frac{1}{8}\cdot 800 + \frac{7}{8}\cdot 110 = 196.25\) HUF. This is less than the price of a Nagyfröcs (200 HUF), which means, that selling Krúdy fröccs and Kisfröccs together is not a good deal.
Without realizing it, this is basically, how we proved, that Krúdy and Sóher fröccs are not good together nor are Nagyfröccs and Hosszúlépés. The other outcome of solving such an equation system could have been, that the midlde one (B) is less profitable, which would mean, that it can be eliminated.
Try to eliminate some other fröccs types with this approach.
Investigate only feasible solutions
As discussed previously in the case of the brute force approach, there are infinitely many solutions. That is also true for the feasible ones, so this would not really help us. The search space could significantly be decreased if only such solutions are examined, that use up at least one ingredient completely, which means, that they can not be improved by selling a bit more of something atop of that solution. This way a lot of sub-optimal solution can be disregarded.
However, even if we only consider Kisfröccs and Nagyfröcs, it is still easy to see, that there are infinitely many solutions that use up all of our wine storage. Try to find such solutions yourself, and prove, that there are infinitely many others.
Final notes
This problem is seemingly more difficult than the festivals example, because having proportional servings made the number of solutions infinitely large. At this point we would assume, that restricting the problem to whole servings would render it simpler, because the number of solutions would become finite, and thus enumerable in a finite amount of time. Contrary to our expectations, it is the other way around, as we will see in the following lectures.