The Orange Juice Algorithm
JeanFrancoisPuget 2700028FGP Visits (10369)
Update on May 20. A recent Netw
A nice, recent, article in Bloo
So, where's the magic? What follows may be an answer. Let me first say that I have not worked directly on this problem hence all what follows needs to be taken with a (large) grain of salt. Anyway, reading this article reminded me of a problem I worked on. I'd like to share it as I believe it can shed some light on what Coke is doing.
I have been working with an industrial gelatin producer during my ILOG days. This company is (was) producing gelatin by cooking bones with water, then filtering the resulting liquid and cooling it. The cooking process migrates the collagen from the bones to the water, which then solidifies as gelatin when cooling down. Gelatin quality is described by some measured values for some features. Feature list included density, transparency, viscosity, etc.
Customers of that company ordering gelatin with some desired value for each feature. So far so good. One simply has to produce the right kind of gelatin.
Issue is that it is next to impossible to control the cooking process enough to guarantee that the result meets customer demand. Basically, one knows what is being produced only when it is over. Gelatin quality is described by measuring features like transparency, density, level of some chemical compound, viscosity, etc that are measured once the gelatin is produced. Then, the gelatin company has to blend gelatin coming from various batches in order to meet customer demand within some agreed upon tolerance.
How do we model such blending problem? The first thing is to understand how the properties of the mix are derived from the properties of the constituents. For the sake of discussion, let's pick one feature, for instance the amount of sugar per volume unit. Let's start with a simple case, where we have two batches, bacth1 and batch2. Let's call si the amount of sugar per liter for batch i. We therefore have a volume v1 of gelatin with s1 grams of sugar per liter, and a volume v2 of gelatin with s2 grams of sugar per liter. Then the amount of sugar per liter if we mix the two batches
(v1.s1 + v2.s2)/'v1 + v2)The level of sugar in the mix is the weighted average of the levels of sugar in each batch.
This is a no brainer, isn"t it? Why am I asking?
Well, it is not obvious at all if you think about it. It is true nevertheless, but it is true thanks to a quite surprising property of water as a solvent. Let's do a small experiment to see where I am going.
[Start of physics 101] Let's take a volume of pure water, say 1 liter (experiment is valid if you use ounces or gallons...), in a large cup. Let's then pour some sugar in it. We'll see the following:
First, the level of water will increase in the cup, because the volume of the mix is the original volume of water plus the volume of sugar we poured. Then, as the sugar dissolves in water, the level of water decrease until all sugar is dissolved. At this point we are back to the original level.. It means that sugar behaves as if it has a null volume once dissolved. This is quite surprising if you think about it. What precedes is true for small quantities of sugar. After some point you cannot dissolve more sugar in water, it is saturated. ¨Point is that as long as you stay below saturation level, then sugar acts as if it has zero volume. Then, the volume of the blend is the sum of the volumes of its constituents. This in turns explains why the sugar level in the blend is the average of the sugar levels in the batches, weighted by their volumes.We say that sugar level is a linear property of the blend. It turns out that most of the measured features are linear properties in the case of gelatin. In particular, all the features that are the level of some compound in water are linear properties. Some other are not exactly linear, such as viscosity, but they are close. It is safe, for this business problem, to assume that all features are linear. Not that this isn't true for other blending problems, such as the ones occurring in the oil industry. In that case properties of blend aren't linear.
[End of physics 101]
We now know how to relate the properties of the blend to the properties of the constituents. If each batch i is having sugar level si and volume vi, then the sugar level of the blend will be
(1) (sum si * vi) / sum vi
Our problem is therefore to blend various gelatin batches such that the properties computation by equation (1) above are close to the values a given customer asks. Here close mean within some small interval centered on the customer demand.
Let's go back to the orange juice problem. Here is how it is described in Bloo
It’s here that Coke has perfected a top-secret methodology it calls Black Book to make sure consumers have consistent orange juice 12 months a year, even though the peak growing season lasts about three months.According to the paper, there is more to Black Book than the above, but that's the part I want to focus on. This part really looks similar to my gelatin experience IMHO.
Here's the analogy in case you' ve not spotted it already. When you press oranges, you get what you get. It is hard to control how oranges grow in order to ensure that their juice will be exactly what people expect to find in their stores, even if you can help a bit by selecting when you pick up the fruits. Oranges are pressed in batches, and juice is collected. Juice is analyzed along 600 dimensions, and a profile with several features (acidity, sweetness, etc) is stored for each juice batch. Then Coke needs to blend various batches in order to match customer preferences.
If you disagree it is similar to the gelatin case, fine, I won't argue with you. I will nevertheless use my gelatin example as a proxy for understanding the orange juice blend problem.
Let's now model our problem as a mathematical optimization problem. We get as input a set of batch descriptions, and a customer demand. Both are described by a volume, and a set of values, one for each feature.
Decision variables for this problem are quite obvious: it is the volume of each batch that we will use to respond to a given customer order. Let' call vi the volume of batch i that is used. vi = 0 means that batch i isn't used at all.
Constraints are directly derived from equation (1) above. For a given feature s, where batch i has value si, and given that the target value for feature s must lie within the interval [ls, us], the constraints or feature s are
(sum si * vi) / sum vi >= lsThese aren't linear constraints, but can be easy transformed into linear constraint by multiplying by the sum of volumes
sum si * vi >= sum ls * vi
To make the problem more interesting, gelatin is stored in containers. When gelatin is produced, a number of containers are filled, and one may be partly filled. For instance if one batch produces 3,842 liters then we get 3 full containers with 1,000 liters each, and one container with 842 liters in it. When blending occurs containers are used entirely. You cannot take 32.46% of a given container. It is all or nothing. The main reason is that gelatin is perishable, it cannot be stored for long, and exposing it to air accelerates the process; Therefore, having full containers (hence without air) is better as it minimizes air exposure for gelatin. It means that for a batch with 3,842 liters, the only possible volume that can be used are: 0, 842, 1000, 1842, 2000, 2842, 3000, and 3842.
So, what will we pick as decision variables? One way is to have one 0-1 variable per container, since each container is either not used, or used entirely. While this is correct it may lead to performance issues because of symmetry. Say for instance that a solution uses 1,842 liters of the 3,842 liter batch. That batch comes in four containers, c1 to c4 such that c1, c2, and c3 contain 1000 liters each, and c4 contains 842 liters. One solution could be to use c1 and c4 to provide the 1,842 liters we need. An equally valid solution would be to use c2 and c4. And a third one is to use c3 and c4. The existence of equivalent solutions is called symmetry. While state of the art solvers, like our IBM ILOG CPLEX, handle symmetry better and better, it is usually a good practice to avoid stating problems with symmetry if one can avoid them. Here, we can avoid symmetry by using two decision variables per batch i. A first variable xi represents the number of full containers to be used, while the second variable yi represents the use of the partially filled container. The yi variables are 0-1 variables while the xi variables are general integer variables. For the batch with 3,842 liters, the x variable can take any integer value between 0 and 3 (the number of full containers), while the y variable i a 0-1. For that batch, the quantity used will be 1000 * x + 842 * y.
What objective could we use? Our customer didn't specify one at first, as they merely wanted to met customer demand. But it may make sense to favor solutions that lead to better business efficiency. One way could be to minimize the number of batches that are used to meet each customer demand. Indeed, it would probably mean less handling and bookkeeping. In order to model this we add one 0-1 variable zi per batch, whose value is set to 1 if and only if the batch is used. Therefore, zi = 0 if the volume used for batch i is null, and zi = 1 if some or all of batch i is used. We use the classical big M trick here to relate zi and the quantity used for batch i. If vi is the quantity then we have
where vmaxi is the total available volume for batch i.
Another aspect of the business problem may be to favor the use of batches that are older, in order to minimize the waste due to the perishable nature of gelatin. We do not include this in our model because w were not provided age information regarding batches.
This completes our model of the problem. An OPL model for it is appended below, as well as a sample data set. There are 6 features per batches, named "a", "b", "w", "x", "y", and "z". I wish I could give real names but these weren't disclosed.
The orange juice problem is certainly more complex, but I bet the main blending constraints look similar to these. I also reckon that there must be some limits on the volume one can use for each batch, as there are good sides to using full containers too.
/***A sample data for this problem