Skip navigation

The Algorithm

Here we describe an algorithm for calculating the best way to combine any set of ingredients into a sour style cocktail.

Algorithm Inputs

The algorithm prompts the user to select choices from a menu of known ingredients. No restrictions are made at this point on the type or number of ingredients that can be chosen. When the user is finished making selections, the program then has N ingredients from which to calculate a cocktail. The only things known about these ingredients are their flavor density vectors: \vec{\rho}_{1},\vec{\rho}_{2},...,\vec{\rho}_{N}. See Statement of the Theory for a discussion on the meaning of these quantities, and Ingredient Calibration for a discussion on how they are measured.

Calculation of the Cocktail

As explained in Statement of the Theory, the most balanced cocktail from the given set of ingredients must be a solution to The Fundamental Theorem of Sours:

(1)   \begin{equation*} \begin{bmatrix} \rho_{bite, 1} & \rho_{bite, 2} & \ldots & \rho_{bite, N} \\ \rho_{sweet, 1} & \rho_{sweet, 2} & \ldots & \rho_{sweet, N} \\ \rho_{sour, 1} & \rho_{sour, 2} & \ldots & \rho_{sour, N} \end{bmatrix} \begin{bmatrix} A_{1} \\ A_{2} \\ \vdots \\ A_{N} \end{bmatrix} =c \left[ \begin{array}{c} 1} \\ 1 \\ 1 \end{array} \right]. \end{equation*}

We first set the arbitrary constant c=1 and worry about scaling the drink to a reasonable size later; see section Scaling the Recipe for details. For compactness, let’s define the amount vector

(2)   \begin{equation*} \vec{A} \equiv \begin{bmatrix} A_{1} \\ A_{2} \\ \vdots \\ A_{N} \end{bmatrix}, \end{equation*}

the flavor density matrix

(3)   \begin{equation*} \rho \equiv \begin{bmatrix} \rho_{bite, 1} & \rho_{bite, 2} & \ldots & \rho_{bite, N} \\ \rho_{sweet, 1} & \rho_{sweet, 2} & \ldots & \rho_{sweet, N} \\ \rho_{sour, 1} & \rho_{sour, 2} & \ldots & \rho_{sour, N} \end{bmatrix}, \end{equation*}

and the constant vector

(4)   \begin{equation*} \vec{T} \equiv \left[ \begin{array}{c} 1} \\ 1 \\ 1 \end{array} \right]. \end{equation*}

The goal is to solve:

(5)   \begin{equation*} \rho \vec{A} = \vec{T}. \end{equation*}

Note that for N ingredients, \rho has dimensions of 3 \times N.
Now is the time to remember our linear algebra and realize that this will play out one of three ways: a unique solution, no solution, or infinite solutions. The primary challenges in developing this algorithm are identifying and addressing the cases in which there is not a unique solution.

Rank and Number of Solutions

To help with this, we use the concept of rank. The rank of a matrix is the maximum number of linearly independent column vectors in the matrix. We will also construct the augmented matrix:

(6)   \begin{equation*} [\rho|\vec{T}]= \begin{bmatrix} \rho_{bite, 1} & \rho_{bite, 2} & \ldots & \rho_{bite, N} & 1 \\ \rho_{sweet, 1} & \rho_{sweet, 2} & \ldots & \rho_{sweet, N} & 1 \\ \rho_{sour, 1} & \rho_{sour, 2} & \ldots & \rho_{sour, N} & 1 \end{bmatrix} \end{equation*}

which just means that we tack on \vec{T} as an additional column to the matrix \rho.

Now, linear algebra tells us that:

  • There are no solutions when rank(\rho)<rank([\rho|\vec{T}]).
  • There is a unique solution when rank(\rho)=rank([\rho|\vec{T}])=N.
  • There are infinite solutions when rank(\rho)=rank([\rho|\vec{T}])<N.

Grouping of Collinear Ingredients

One immediately obvious issue arises when there are multiple ingredients whose flavor density vectors are proportional to (or collinear with) one another.  They are clearly not linearly independent, so rank(\rho)<N.  This means that the solutions, if there are any, will be infinite.  An example of this would be a cocktail involving both lemon juice and lime juice.  If we assume that \vec{\rho}_{\textnormal{Lemon Juice}} and \vec{\rho}_{\textnormal{Lime Juice}} have only one non-zero component of sourness, then they are collinear with one another.  To solve Eq. 5, we need the total sourness to add up to one.  We could have all the sourness come from lemon juice, we could have all the sourness come from lime juice, or we could have any combination of lime juice and lemon juice such that the sourness adds to one.  There are infinitely many ways of arranging this.  We will, however, make the solution unique by introducing an additional constraint.  For any group of N_{g} ingredients collinear with one another and with flavor density vectors \vec{\rho}_{1},\vec{\rho}_{2},...,\vec{\rho}_{N_{g}} we impose the condition that the amounts of each ingredient A_{1},A_{2},...,A_{N_{g}} satisfy:

(7)   \begin{equation*} A_{1}|\vec{\rho}_{1}|=A_{2}|\vec{\rho}_{2}|=...=A_{N_{g}}|\vec{\rho}_{N_{g}}|=constant. \end{equation*}

The magnitude |\vec{\rho}_{i}| \equiv \sqrt{\rho_{bite,i}^{2}+\rho_{sweet, i}^{2}+\rho_{sour, i}^{2}} is a measure of the overall flavor density of the ingredient.  Thus, A_{i}|\vec{\rho}_{i}| is a measure of the overall flavor contributed by an ingredient.  Condition 7 then requires that all ingredients within a group of collinear ingredients contribute equal amounts of overall flavor.  We could arrange these ingredients in infinitely many ways to achieve balance in the cocktail (i.e. to solve 5), but we choose the unique solution that makes each ingredient contribute equal amounts of total flavor.  This is based on the assumption that when the user enters multiple similar (collinear) ingredients, his or her intention is to obtain a cocktail that showcases all of them equally, that no one ingredient should dominate the others. Why bother putting in a bunch of stuff if all you can really taste is one or a few of them? We refer to this idea as The Principle of Equal Flavor Contribution, an important assumption that allows for a unique solution.  Whether condition 7 is the best way of ensuring equal flavor contributions or not is debatable.  There may be other things worth considering besides bite, sweetness, and sourness.  Even if we restrict ourselves to only the information contained within \vec{\rho}_{i}, we could perhaps think of other quantities besides |\vec{\rho}_{i}| as potential ways of measuring overall flavor density, which is an inherently vague concept.  Nonetheless, we will stick with the proposed method, which is fairly straightforward and reasonably well-motivated.

Since the amounts of all ingredients in a collinear group are constrained relative to each other by condition 7, there is only one degree of freedom for the entire group: the total amount of all ingredients in the group.  Once we know the total amount, condition 7 already tells us how it is distributed among the members of the group.  So we can think of a collinear group as one big ingredient with some flavor density vector \vec{\rho}_{G} and some amount A_{G}=\sum\limits_{i=1}^{N_{g}} A_{i} for which we must solve.  From condition 7, we can compute the fraction of the group total contributed by ingredient i:

(8)   \begin{equation*} \frac{A_{i}}{A_{G}} = \frac{1}{|\vec{\rho}_{i}| \sum\limits_{j=1}^{N_{g}} \frac{1}{|\vec{\rho}_{j}|}}. \end{equation*}

The overall flavor density vector of the group is the weighted average of all the component ingredient flavor density vectors:

(9)   \begin{equation*} \vec{\rho}_{G} =\left(\frac{1}{\sum\limits_{j=1}^{N_{g}} \frac{1}{|\vec{\rho}_{j}|}} \right)\sum\limits_{i=1}^{N_{g}} \frac{\vec{\rho}_{i}}{|\vec{\rho}_{i}|}. \end{equation*}

The algorithm finds groups of collinear ingredients and then sorts things out so that they appear as adjacent rows in \vec{A} and adjacent columns in \rho for Eq. 5.  The adjacent columns in \rho are replaced with a single column (given by \vec{\rho}_{G}) and the adjacent rows in \vec{A} are likewise replaced with a single row (A_{G}).  The reduced matrix equation is now:

(10)   \begin{equation*} \widetilde{\rho} \widetilde{\vec{A}} = \vec{T}. \end{equation*}

If \widetilde{N} is the number of collinear groups (\widetilde{N}=N when no two ingredients are collinear), then \widetilde{\rho} has dimensions 3 \times \widetilde{N} and \widetilde{\vec{A}} has \widetilde{N} rows.

For the purposes of solving Eq. 10, it’s helpful to classify the scenario based on the number of  unique, non-collinear ingredients \widetilde{N}.

Case 1: Overdetermined System (\widetilde{N}<3)

When the number of unique ingredients is fewer than three, there are three equations of constraint for less than three unknowns (the amounts); thus, the situation is overdetermined. In this case, there will either be no solutions if the system is inconsistent or there will be a unique solution if certain equations are not actually linearly independent.  Because we’ve already reduced collinear ingredients at this stage and \widetilde{N} can be no more than two, we are guaranteed that rank(\widetilde{\rho})=\widetilde{N} so there cannot be multiple solutions.

The algorithm figures out which is the case by first calculating the least squares solution: \widetilde{\vec{A}}_{LS}; this is a common feature of linear algebra libraries for programming languages. It is also a standard technique for fitting a function with limited free parameters to an abundance of data points. If the system actually has a solution, then it will be identical to the least squares solution. The algorithm tests whether

(11)   \begin{equation*} \widetilde{\rho} \widetilde{\vec{A}}_{LS} - \vec{T} = 0 \end{equation*}

is true or not. If Eq. 11 holds within some small numerical precision, then we have a unique cocktail solution: \widetilde{\vec{A}}=\widetilde{\vec{A}}_{LS}. Otherwise, there is no exact solution. This issue is discussed in Dealing with No Solutions

Case 2: Square Matrix (\widetilde{N}=3)

With exactly three unique ingredients, \widetilde{\rho} is a square matrix. All situations are possible: no solution, infinite solutions, or a unique solution. We would like to know which one it is first.

The algorithm first checks whether a solution exists at all by evaluating whether rank(\widetilde{\rho})=rank([\widetilde{\rho}|\vec{T}]) holds or not.  Linear algebra software libraries typically have built in methods to calculate rank.  When this test fails, see Dealing with No Solutions.  If this test is successful, we then need to determine if the solution is unique.  This is done simply by computing the determinant of \widetilde{\rho} and checking that det(\widetilde{\rho}) \neq 0.  When this check fails, see Dealing with Infinite Solutions.  If this test passes, we know that \widetilde{\rho} is invertible and the unique solution can be calculated as:

(12)   \begin{equation*} \widetilde{\vec{A}}=\widetilde{\rho}^{-1}\vec{T}. \end{equation*}

We need to check that the solution is physical: the amounts should all be positive; we can’t very well put in negative amounts of cocktail ingredients!  If the solution is unphysical, see Dealing with No Solutions.  Otherwise we are done finding a solution.

Case 3: Underdetermined System (\widetilde{N}>3)

In this scenario, there are more unknowns than there are equations to constrain them.  Here we know that rank(\widetilde{\rho})<\widetilde{N}, so a unique solution is not possible.  We first evaluate rank(\widetilde{\rho})=rank([\widetilde{\rho}|\vec{T}]) to check for the existence of solutions.  If there are none, see Dealing with No Solutions.  Otherwise, the only possibility left is infinite solutions: see Dealing with Infinite Solutions.

Dealing with No Solutions

In the event that the selected ingredients can in no way be combined to solve Eq. 5, we will attempt to find the most minimal addition of auxiliary ingredients so that a solution becomes possible. We use a set of exactly three predefined reserve ingredients with flavor density vectors \vec{\rho}_{1},\vec{\rho}_{2},\vec{\rho}_{3} of a specific form:

(13)   \begin{equation*} \vec{\rho}_{1} = \left[ \begin{array}{c} \rho_{1}} \\ 0 \\ 0 \end{array} \right] \;\; \vec{\rho}_{2} = \left[ \begin{array}{c} 0} \\ \rho_{2} \\ 0 \end{array} \right] \;\; \vec{\rho}_{3} = \left[ \begin{array}{c} 0} \\ 0 \\ \rho_{3} \end{array} \right], \end{equation*}

where \rho_{1},\rho_{2},\rho_{3}>0. Such a set forms a complete basis for \mathbf{R}^{3}. For any selection of ingredients the user has given, we will only need to add at most two of these reserve ingredients in order for a solution to be possible. This is because, at worst, the user selects ingredients with flavor density vectors that are all proportional to one of the reserves; so, by including the other two reserves we can now span the entire space of \mathbf{R}^{3} and find a linear combination that adds to \vec{T} and thus solves Eq. 5. The algorithm attempts to find a solution by adding a single reserve ingredient. If no single reserve ingredient can do the job, then the algorithm tries adding all possible pairs of two reserve ingredients until a pair is found that does the job. The interpretation of all of this is simple. The reserve ingredients have pure alcoholic bite, pure sweetness, and pure sourness respectively. When the user selects ingredients with no solution, it means that there is either not enough sweetness, not enough sourness, not enough bite, or any two of those conditions together. This is why a solution becomes possible when we add the requisite sweetness, sourness, etc…

The ideal choices of reserve ingredients are items that satisfy Eq. 13 while adding as little additional flavor nuance as possible to what the user has already entered. Simple syrup is used for adding pure sweetness and no other flavor. Lemon juice is used for adding sourness; it’s not really neutral in flavor otherwise but a better alternative remains elusive. Vodka is used to add bite because it is otherwise very flavor neutral (a specific brand needs to be used). I would like to make the reserve ingredients tunable for the user at some point; at the moment the algorithm is just using preset defaults.

Dealing with Infinite Solutions

Even after grouping together collinear ingredients and imposing condition 7 on them, we may still have a situation with infinite solutions. On top of that, if we’ve landed here, we can’t easily determine what the solutions are by inverting a matrix. In this case, we will need to find the solutions numerically. We do this by searching an \widetilde{N}-dimensional lattice, where each dimension represents the possible amounts of an ingredient. At each point on the lattice, we calculate the error for the corresponding ingredient amounts (\widetildeP{\vec{A}}):

(14)   \begin{equation*} \Delta E =\frac{| \widetilde{\vec{\rho}}\widetilde{\vec{A}}-\vec{T}|}{|\vec{T}|}. \end{equation*}

For an exact solution, \Delta E = 0, but since we are solving numerically, we can consider points on the lattice with very small values of \Delta E to be solutions. As \widetilde{N} grows, the computational complexity of the algorithm grows very fast. We adopt an adaptive lattice spacing so that the spacing for ingredient i is scaled by the maximum entry in \vec{\rho}_{i}. This just means that we need a small spacing for ingredients with strong flavors because a small change in volume produces a significant change in the overall balance, and vice-versa for ingredients with weaker flavors.

Now that we have dealt with the problem of picking out the solutions, we now impose an additional constraint to make the solution unique. The Principle of Equal Flavor Contribution can do this; however, it is not generally possible to simultaneously satisfy both Eq. 5 and condition 7 when all ingredients are considered and not just collinear groups. Instead, we enforce a weaker version of condition 7. Among the possible solutions, we shall choose the one that minimizes the figure of merit:

(15)   \begin{equation*} \mathcal{F}(A_{1},A_{2},...,A_{N}) = \sum\limits_{i=1}^{N-1} \sum\limits_{j=i+1}^{N} (A_{i} |\vec{\rho}_{i}| - A_{j} |\vec{\rho}_{j}|)^{2}. \end{equation*}

Here \mathcal{F} is a function of the amounts of all ingredients in the cocktail that simply calculates the sum of all squared flavor differences of ingredient pairs. If it is possible to find a solution that yields \mathcal{F}=0, it is equivalent to satisfying condition 7 among all ingredients. More generally, we will pick the solution with the smallest value of \mathcal{F}. The interpretation of this is that of the infinitely many balanced cocktails we could make with the set of ingredients, we want the one that comes closest to making all the ingredients contribute equal amounts of total flavor.

The algorithm for this faces some subtle difficulties. Of the lattice of points we look at, the values for \Delta E in Eq. 14 tend to lie along a closely spaced continuum. Deciding where to make the cut for acceptable solutions is somewhat arbitrary. One can try to optimize the tradeoff between how closely Eq. 5 is solved and how small of an \mathcal{F} can be achieved. I do not attempt to describe this algorithm yet because it has undergone several changes and may undergo more in the future.

Scaling the Recipe

At this point, the algorithm has calculated a precise set of amounts for the ingredients. In the final step, this recipe, which may contain amounts in fractions of a ml and may be really small or really large in size, is converted into a convenient recipe with amounts that can actually be measured and that makes for a reasonable cocktail size. In other words, we will decide on the most convenient value for c in Eq. 1.

An ideal amount of total alcoholic ingredients is about 2 oz. This makes for a fairly typical drink size that neither contains too little nor an excessive amount of alcohol. We allow for some range around this: we consider values for c such that the total amount of alcoholic ingredients is between 1 oz and 2.5 oz. The total amount of alcoholic ingredients is calculated by adding the amounts for all ingredients in the recipe with non-zero alcoholic bite (\rho_{bite}>0).

The other consideration is that we wish to report the ingredient amounts in multiples of 5 ml since this is the smallest unit that can really be measured. At the same time, we want to preserve the correct proportions of ingredients as accurately as possible. The algorithm numerically searches the range of c values described above in small discrete steps. For each step, all of the ingredient amounts are rounded to the nearest multiple of 5 ml and the error of Eq. 14 is computed. A threshold precision is defined at \Delta E=0.01, below which all values are considered equally viable solutions. Of all the scale factors with \Delta E values below that threshold, we choose the one that makes the total alcoholic content closest to 2 oz. If no scale factors are below that threshold, then we just choose the one with the smallest value of \Delta E.

Leave a Reply