Operations research is about the utilisation of scarce resources. For beer home brewing, the scarce resources are the ingredients. At its most basic, beer requires just 4 ingredients: malted barley, hops, yeast and water (bring in the Reinheitsgebot, or the German purity law). However, with each of these ingredient categories, except water, there are many varieties to choose from. For example, there are hundreds of hop varieties, such as Simcoe, Citra, Mosaic, Goldings, Fuggels and Saaz. Malted barley, includes pale, Munich, crystal, roasted and chocolate. Finally, the yeast varieties are related to the beer styles, such as ale or larger, but even more specific such as Belgian, US ale and Bavarian wheat.
One may be asking, how is all of this related to optimisation and operations research. The ingredient utilisation issue comes from the conflict between the quantities required to brew a beer and the minimum order quantities. I will highlight this with an example recipe for the Home Brew Recipe Bible by Chris Colby:
|Fermentis U.S.-05 yeast||11g|
|U.S. 2-row pale malt||4.3kg|
|Crystal malt (40oL)||220g|
|Crystal malt (60oL)||84g|
(Home Brew Recipe Bible by Chris Colby)
Wastage from ordering
The yeast comes in a packet that contains 11g. So we don’t need to worry about that one. It is the malt and hops that introduce some utilisation issues. The minimum order quantity for malt is typically 500g, but for some of the more common malts, such as U.S. 2-row pale malt, the minimum order quantity could be 1kg. In regards to hops, these come in 100g pouches. Considering our recipe above, I have updated the table with the order quantity and the wastage (order quantity minus required quantity).
|Fermentis U.S.-05 yeast||11g||11g||0g|
|U.S. 2-row pale malt||4.3kg||5kg||700g|
|Crystal malt (40oL)||220g||500g||280g|
|Crystal malt (60oL)||84g||500g||416g|
(Home Brew Recipe Bible by Chris Colby)
As you can see, for some ingredients we must order a significant amount more than what is required, especially for the hops. The worst outcome is actually the malts, since these are perishable once crushed. So you would want to use these malts as soon as possible.
Reduce wastage using optimisation
If we just brewed one beer, then there is nothing to be done. The wastage is just an outcome of the process. However, most brewers will brew more than one beer. Thus, it is possible to select your recipes to minimise the amount of wastage.
The optimisation problem that we encounter draws upon a number of different classical problems. There is a knapsack component, since we want to select recipes that collectively have ingredients that is less than the minimum order quantity (specifically for the hops), but as close as possible to this quantity. We could also consider this as a multiple knapsack problem, where each ingredient has its own knapsack, which is activated when at least one recipe requires that ingredient. Alternatively, there are aspects of a cutting stock problem in trying to reduce wastage. However, there is no minimum quantity required for each ingredient (i.e. satisfying demand). The closest to what I have discussed previously is substitution scheduling for a football tournament. However, this problem is not directly related to the other blogs on this site.
A possible modelling approach
It is not immediately obvious how to best formulate this problem, so we will start by describing the objective function and then present a modelling idea.
In regards to the requirements for the problem, there are no direct constraints. This is because, we don’t need to brew any beer. However, we may want to impose a limit on the total number of beers. This is because in the limit, wastage is negligible. But that would result in us drinking an infinite number of beers.
The vast range of beer styles and corresponding ingredients makes this a very difficult task for a human to optimise. If we just limit ourselves to the recipes in the Home Brew Recipe Bible, we still have 101 recipes. Across this collection of recipes there are more than 80 ingredients, not including yeast. As such, I estimate that the optimisation problem would contain approximately 180 variables. While it may be possible to devise a heuristic to minimise the wastage by hand, software would be valuable in performing this task.
My solution to this would be to develop a database of the all recipes. Many of these exist, especially in the case of recipe builders, such as the recipe generator from Brew UK. Each recipe would be represented as a discrete variable, where the selection of the recipe consumes some quantity of ingredients. Then the ordering of each ingredient would be represented by a discrete decision, with a corresponding order quantity. When the sum of the required quantity for an ingredient exceeds the order quantity, then an additional unit must be ordered.
The most time consuming part of this process is building the database. The optimisation problem is relatively simple, and it is possible that publicly available solvers would provide a good answer in reasonable run times (however I have not tested this).
I came about this problem, because I found that I was purchasing more ingredients that I needed. Especially, since I am brewing at 1/4 of the quantity of most recipes. As a result, I have been stuck brewing the same beer styles for the last year.
Unfortunately, I don’t have a technology solution to solve this problem. I decided that brewing the beer would be more fun than building the database to minimise the wastage of ingredients. So I am still brewing my different varieties of pale ales. Hopefully, I will be able to branch out in the near future.