Case Study: The Whiskas Cat Food Problem

Submitted: 31 Jan 2008

Operations Research Topics: LinearProgramming, BlendingModels

Application Areas: Pet Food Manufacturing

Contents

Problem Description

Figure 1 Whiskas cat food label

whiskas_label.jpg

Whiskas cat food (shown in Figure 1) is manufactured by Uncle Ben's. Uncle Ben's want to produce their cat food products as cheaply as possible while ensuring they meet the stated nutritional analysis requirements shown on the cans (see Figure 2). Thus they want to vary the quantities of each ingredient used (the main ingredients being chicken, beef, mutton, rice, wheat and gel) while still meeting their nutritional standards (see Figure 3).

Figure 2 Ingredients and nutritional requirements

whiskas_ingredients.jpg whiskas_nutrition.jpg

Figure 3 Setting the mix of ingredients

whiskas_blend.jpg

The costs of the chicken, beef, and mutton are $0.013, $0.008 and $0.010 respectively, while the costs of the rice, wheat and gel are $0.002, $0.005 and $0.001 respectively. (All costs are per gram.) In this case study, we will ignore the vitamin and mineral ingredients. (Any costs for these are likely to be very small anyway.)

Each ingredient contributes to the total weight of protein, fat, fibre and salt in the final product. The contributions (in grams) per gram of ingredient are given in Table 1.

Table 1 Contributions of ingredients

  Protein Fat Fibre Salt
Chicken 0.100 0.080 0.001 0.002
Beef 0.200 0.100 0.005 0.005
Mutton 0.150 0.110 0.003 0.007
Rice 0.000 0.010 0.100 0.002
Wheat bran 0.040 0.010 0.150 0.008
Gel - - - -

Return to top

Problem Formulation

We will formulate the Whiskas Cat Food Problem as a mathematical programme (using the 4 key steps).

1. Identify the Decision Variables

For the Whiskas Cat Food Problem the decisions are the grams of each of the different ingredients we include in the can.

We must formally define our decision variables, being sure to state the units we are using.

 \begin{align*} x_1 &= \text{ amount (g) of chicken meat in a can of cat food} \\ x_2 &= \text{ amount (g) of beef used in a can of cat food} \\ x_3 &= \text{ amount (g) of mutton used in a can of cat food} \\ x_4 &= \text{ amount (g) of rice used in a can of cat food} \\ x_5 &= \text{ amount (g) of wheat bran used in a can of cat food} \\ x_6 &= \text{ amount (g) of gel used in a can of cat food} \end{align*}

2. Formulate the Objective Function

For the Whiskas Cat Food Problem the objective is to minimise the total cost of ingredients per can of cat food.

We know the cost per g of each ingredient, so we can define our objective: to minimise the total cost of a can

 {\small \begin{equation*} \min \$0.013 x_1 + \$0.008 x_2 + \$0.010 x_3 + \$0.002 x_4 + \$0.005 x_5 + \$0.001 x_6 \end{equation*} }

3. Formulate the Constraints

The constraints for the Whiskas Cat Food Problem are that:
  • The sum of the amounts must make up the whole can (= 100g).
  • The stated nutritional analysis requirements are met.

The constraint for the "whole can" is:

 {\small \begin{equation*} x_1 + x_2 + x_3 + x_4 + x_5 +x _6 = 100 \end{equation*} }

To meet the nutritional analysis requirements, we need to have at least 8g of Protein per 100g, 6g of fat, but no more than 2g of fibre and 0.4g of salt. To formulate these constraints we make use of the previous table of contributions from each ingredient. This allows us to formulate the following constraints on the total contributions of protein, fat, fibre and salt from the ingredients:

 {\small \begin{equation*} \begin{array}{rrrrrrcr} 0.100 x_1 & +0.200 x_2 & +0.150 x_3 & +0.000 x_4 & +0.040 x_5 & +0.0 x_6 &\geq& 8.0 \\ 0.080 x_1 & +0.100 x_2 & +0.110 x_3 & +0.010 x_4 & +0.010 x_5 & +0.0 x_6 &\geq& 6.0 \\ 0.001 x_1 & +0.005 x_2 & +0.003 x_3 & +0.100 x_4 & +0.150 x_5 & +0.0 x_6 &\leq& 2.0 \\ 0.002 x_1 & +0.005 x_2 & +0.007 x_3 & +0.002 x_4 & +0.008 x_5 & +0.0 x_6 &\leq& 0.4 \end{array} \end{equation*} }

4. Identify the data

We know the total weight of the can. We also know the cost of the ingredients, the nutritional analysis requirements and the contribution (per gram) of each ingredient in terms of the nutritional analysis. This is enough to formulate the necessary mathematical programme. However, we will reconsider our data after solving the mathematical programme and performing some analysis.

Generalising the Formulation

The previous formulation will solve the Whiskas Cat Food Problem for the given ingredients and requirements, however we would have to reformulate if a new ingredient or requirement was added. We can "abstract" the data to make our formulation more general and thus easier to modify when the data changes.

Let ${\cal I}$ be the set of all ingredients and let ${\cal R}$ be the set of all requirements (cf. inputs and outputs in a blending model).

Now the decision variables become

\[ x_i = \text{amount (g) of ingredient $i$ in a can of cat food} \]

Let $W$ be the weight of the can and $c_i$ be the cost per g of ingredient $i$. The objective function becomes

\[ \min \sum_{i \in {\cal I}} c_i x_i \]

Finally, let $k_{ri}$ be the "contribution" that 1g of ingredient $i \in {\cal I}$ makes to requirement $r \in {\cal R}$ and let $L_r$ and $U_r$ be the lower and upper bounds on requirement $r \in {\cal R}$ respectively. Now the constraints can be expressed

\[ L_r \leq \sum_{i \in {\cal I}} k_{ri} x_i \leq U_r, \text{ for all } r \in {\cal R} \]

Note that whole can constraint can be easily incorporated in this generalised formulation by setting $k_\text{whole can}, i = 1$ and $L_\text{whole can} = U_\text{whole can} = W$.

Return to top

Computational Model

Using our original formulation, the computational model in AMPL would have been time consuming (and repetitive!) to create, e.g.,

var x1 >= 0; # Amount (g) of chicken meat used in a can of cat food
var x2 >= 0; # Amount (g) of beef used in a can of cat food
.
.
.
var x6 >= 0; # Amount (g) of gel used in a can of cat food (= g)
Note that the # is used for commenting.

However, we can easily translate our generalised formulation into AMPL. First, we define the sets for the ingredients and requirements

set INGREDIENTS;
set REQUIREMENTS;
We will see later how to "populate" these sets using an AMPL data file.

Using the sets we can define the decision variables

var Amount {INGREDIENTS} >= 0;
parameters for the costs
param Cost {INGREDIENTS};
and the objective function
minimize TotalCost : sum {i in INGREDIENTS} Cost[i] * Amount[i];

Now we have a variable that determines the amount (in g) of each ingredient (whatever they may be) in a can of Whiskas and our objective is to minimize the total unit cost of producing the cans (although we haven't specified the actual costs yet).

Next, we need to define parameters for the contribution each ingredient makes to the requirements and for the bounds on the requirements themselves

param Contributes {REQUIREMENTS, INGREDIENTS};

param Lower {REQUIREMENTS} default -Infinity;
param Upper {r in REQUIREMENTS} >= Lower[r], default Infinity;

Note the use of a bound to ensure that Upper $\geq$ Lower and default values for the requirement bounds.

Finally, we can formulate the constraints in AMPL

subject to MeetRequirements {r in REQUIREMENTS} :
  Lower[r] <= sum {i in INGREDIENTS} Contributes[r, i] * Amount[i] <= Upper[r];

Now our AMPL model is complete (see whiskas.mod for a complete AMPL model file).

Once an AMPL model file is complete, we need to create a data file to create an "instance" of this problem. Note that we can use several different data files with the same model file (in practice this means solving the same mathematical programme with different data).

First, create a new data file for AMPL and save it as whiskas.dat.

Next, all our AMPL expressions rely on the sets INGREDIENTS and REQUIREMENTS, so we will define these first. Remember, when AMPL is in data mode (see The AMPL Process), we don't need to enclose set elements with ' and ' (unless there is a whitespace within the symbol). We also don't need { and } to signify the start and end of a set.

We can define the sets of ingredients and requirements using the set keyword and the assignment operator :=

set INGREDIENTS := CHICKEN BEEF MUTTON RICE WHEAT GEL ;

set REQUIREMENTS := PROTEIN FAT FIBRE SALT ONECAN ;

Note Since whitespace signifies the end of a symbol, you need space before the terminating ;.

Now the set of ingredients has been established, we can assign data to parameters that use that set.

First, define the parameter Cost

param Cost :=
CHICKEN 0.013
BEEF    0.008
...
GEL     0.001
 ;

Then, use a transposed table to define the nutritional contribution per gram for the ingredients

param Contributes (tr):
        PROTEIN   FAT FIBRE  SALT ONECAN :=
CHICKEN   0.100 0.080 0.001 0.002    1.0
BEEF      0.200 0.100 0.005 0.005    1.0
MUTTON    0.150 0.110 0.003 0.007    1.0
RICE      0.000 0.010 0.100 0.002    1.0
WHEAT     0.040 0.010 0.150 0.008    1.0
GEL       0.0   0.0   0.0   0.0      1.0
 ;

Finally, we can define both the Lower and Upper parameters

param   Lower :=
PROTEIN 8.0
FAT     6.0
ONECAN  100
 ;
 
param  Upper :=
FIBRE  2.0
SALT   0.4
ONECAN 100
;

Now our data file whiskas.dat is complete.

Now we can use AMPL to determine how to optimally mix the ingredients in a can of cat food. First, start a command line application and navigate to the directory where you saved whiskas.mod and whiskas.dat. Then start AMPL.

Create the model in AMPL by typing:

model whiskas.mod;

Populate the model with data by typing:

data whiskas.dat;

Choose the CPLEX solver (although MINOS also solves linear programming models):

option solver cplex;

and solve The Whiskas Cat Food Problem using AMPL:

solve;

To see the amount (in g) of each ingredient to include in the 100g can:

display Amount;

When you are developing a model and running it many times (while testing and debugging) you might like to create a script file. For the Whiskas Cat Food Problem your script file whiskas.run will be:

reset;
model whiskas.mod;
data whiskas.dat;

option solver cplex;
solve;

display Amount;

Remember, you can run the script file in AMPL with the command:

include whiskas.run;

Return to top

Results

Running whiskas.run gives the following output:

ampl: include whiskas.run;
CPLEX 10.1.0: optimal solution; objective 0.52
2 dual simplex iterations (0 in phase I)
Amount [*] :=
   BEEF  60
CHICKEN   0
    GEL  40
 MUTTON   0
   RICE   0
  WHEAT   0
;

This solution indicates that the mix of ingredients for minimising the cost of a can of Whiskas cat food is to use 60g of beef and 40g of gel. The cost of the can will be 52c.

For the Whiskas Cat Food Problem we will not perform any post-optimal analysis.

Validation To validate our solution for the Whiskas Cat Food Problem, we can do a quick check that our solution makes sense. First, the amounts should add up to the weight of the can (e.g., 60g + 40g = 100g). If not, there is something wrong.

Next, we can do a quick check of the constraints to ensure none of them are violated. For large models you won't always be able to check the solution by hand. However, you can use AMPL expressions to quickly calculate quantities needed for validation.

ampl: display {r in REQUIREMENTS} sum {i in INGREDIENTS} Contributes[r, i] * Amo
unt[i];
sum{i in INGREDIENTS} Contributes[r,i]*Amount[i] [*] :=
    FAT    6
  FIBRE    0.3
 ONECAN  100
PROTEIN   12
   SALT    0.3
;

ampl: display Lower, Upper;
:           Lower       Upper       :=
FAT               6   Infinity
FIBRE     -Infinity          2
ONECAN          100        100
PROTEIN           8   Infinity
SALT      -Infinity          0.4
;

The final validation is to write up a management summary for your manager and/or client and see if they think your solution is a valid one. If they identify some (or all) of the solution that is not valid, then you should discuss with them the reasons why it is invalid and start a "feedback" loop in the Operations Research methodology.

Return to top

Conclusions

The solution for the Whiskas Cat Food Problem is a simple one to summarise. Here is the management summary for the Whiskas Cat Food Problem.

Important When presenting your solution you must be careful about the number of decimal places you use. You should not use a greater accuracy than your data allows.

Return to top

Student Tasks

1. Using whiskas.mod, whiskas.dat and whiskas.run, solve the Whiskas Cat Food Problem. Write a management summary for your solution.

What to hand in Your management summary.

2. Find the optimal mix of ingredients if the can weighs 150g and ham is available as an ingredient that costs $0.007 per g and each g of ham contributes 0.180g of protein, 0.110g of fat, 0.002g of fibre and 0.008g of salt. Note The nutritional requirements are expressed as percentages of the can weight so these will change. Write a management summary for your solution.

What to hand in Your new data file whiskas.dat and your management summary.

Return to top

Topic attachments
I Attachment History Action Size Date Who Comment
Unknown file formatdat whiskas.dat r4 r3 r2 r1 manage 0.9 K 2008-03-09 - 23:21 MichaelOSullivan  
Microsoft Word filedoc whiskas.doc r2 r1 manage 38.0 K 2008-03-11 - 21:07 MichaelOSullivan  
Unknown file formatmod whiskas.mod r6 r5 r4 r3 r2 manage 1.1 K 2008-03-04 - 21:58 MichaelOSullivan  
Unknown file formatrun whiskas.run r2 r1 manage 0.1 K 2008-02-24 - 05:50 MichaelOSullivan  
Edit | Attach | Watch | Print version | History: r56 < r55 < r54 < r53 < r52 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r56 - 2019-07-20 - TWikiAdminUser
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback