A Blending Problem =================== Problem Description ------------------- .. image:: images/whiskas_label.jpg Whiskas cat food, shown above, 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. 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. .. image:: images/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.) For this exercise 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 the table below. ============ ========= ========= ======== ======= Stuff 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 0.000 0.000 0.000 0.000 ============ ========= ========= ======== ======= Simplified Formulation ~~~~~~~~~~~~~~~~~~~~~~ First we will consider a simplified problem to build a simple Python model. Identify the Decision Variables +++++++++++++++++++++++++++++++++++ Assume Whiskas want to make their cat food out of just two ingredients: Chicken and Beef. We will first define our decision variables: .. math:: x_1 &= \text{ percentage of chicken meat in a can of cat food }\\ x_2 &= \text{ percentage of beef used in a can of cat food } The limitations on these variables (greater than zero) must be noted but for the Python implementation, they are not entered or listed separately or with the other constraints. Formulate the Objective Function ++++++++++++++++++++++++++++++++ The objective function becomes: .. math:: \textbf{ min } 0.013 x_1 + 0.008 x_2 The Constraints +++++++++++++++ The constraints on the variables are that they must sum to 100 and that the nutritional requirements are met: .. math:: 1.000 x_1 + 1.000 x_2 &= 100.0\\ 0.100 x_1 + 0.200 x_2 &\ge 8.0\\ 0.080 x_1 + 0.100 x_2 &\ge 6.0\\ 0.001 x_1 + 0.005 x_2 &\le 2.0\\ 0.002 x_1 + 0.005 x_2 &\le 0.4\\ Solution to Simplified Problem ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ To obtain the solution to this Linear Program, we can write a short program in Python to call PuLP's modelling functions, which will then call a solver. This will explain step-by-step how to write this Python program. It is suggested that you repeat the exercise yourself. The code for this example is found in :download:`WhiskasModel1.py <../../../examples/WhiskasModel1.py>` The start of the your file should then be headed with a short commenting section outlining the purpose of the program. For example: .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 1-5 Then you will import PuLP's functions for use in your code: .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 7-8 A variable called ``prob`` (although its name is not important) is created using the :class:`~pulp.LpProblem` function. It has two parameters, the first being the arbitrary name of this problem (as a string), and the second parameter being either ``LpMinimize`` or ``LpMaximize`` depending on the type of LP you are trying to solve: .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 10-11 The problem variables ``x1`` and ``x2`` are created using the :class:`~pulp.LpVariable` class. It has four parameters, the first is the arbitrary name of what this variable represents, the second is the lower bound on this variable, the third is the upper bound, and the fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are ``LpContinuous`` or ``LpInteger``, with the default as ``LpContinuous``. If we were modelling the number of cans to produce, we would need to input ``LpInteger`` since it is discrete data. The bounds can be entered directly as a number, or ``None`` to represent no bound (i.e. positive or negative infinity), with ``None`` as the default. If the first few parameters are entered and the rest are ignored (as shown), they take their default values. However, if you wish to specify the third parameter, but you want the second to be the default value, you will need to specifically set the second parameter as it's default value. i.e you cannot leave a parameter entry blank. e.g:: LpVariable("example", None, 100) or:: LpVariable("example", upBound = 100) To explicitly create the two variables needed for this problem: .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 13-15 The variable ``prob`` now begins collecting problem data with the ``+=`` operator. The objective function is logically entered first, with an important comma ``,`` at the end of the statement and a short string explaining what this objective function is: .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 17-18 The constraints are now entered (Note: any "non-negative" constraints were already included when defining the variables). This is done with the '+=' operator again, since we are adding more data to the ``prob`` variable. The constraint is logically entered after this, with a comma at the end of the constraint equation and a brief description of the cause of that constraint: .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 20-25 Now that all the problem data is entered, the :meth:`~pulp.LpProblem.writeLP` function can be used to copy this information into a .lp file into the directory that your code-block is running from. Once your code runs successfully, you can open this .lp file with a text editor to see what the above steps were doing. You will notice that there is no assignment operator (such as an equals sign) on this line. This is because the function/method called :meth:`~pulp.LpProblem.writeLP` is being performed to the variable/object ``prob`` (and the string ``"WhiskasModel.lp"`` is an additional parameter). The dot ``.`` between the variable/object and the function/method is important and is seen frequently in Object Oriented software (such as this): .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 27-28 The LP is solved using the solver that PuLP chooses. The input brackets after :meth:`~pulp.LpProblem.solve` are left empty in this case, however they can be used to specify which solver to use (e.g ``prob.solve(CPLEX())`` ): .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 30-31 Now the results of the solver call can be displayed as output to us. Firstly, we request the status of the solution, which can be one of "Not Solved", "Infeasible", "Unbounded", "Undefined" or "Optimal". The value of ``prob`` (:attr:`pulp.pulp.LpProblem.status`) is returned as an integer, which must be converted to its significant text meaning using the :attr:`~pulp.constants.LpStatus` dictionary. Since :attr:`~pulp.constants.LpStatus` is a dictionary(:obj:`dict`), its input must be in square brackets: .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 33-34 The variables and their resolved optimum values can now be printed to the screen. .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 36-38 The ``for`` loop makes ``variable`` cycle through all the problem variable names (in this case just ``ChickenPercent`` and ``BeefPercent``). Then it prints each variable name, followed by an equals sign, followed by its optimum value. :attr:`~pulp.LpVariable.name` and :attr:`~pulp.LpVariable.varValue` are properties of the object ``variable``. The optimised objective function value is printed to the screen, using the value function. This ensures that the number is in the right format to be displayed. :attr:`~pulp.LpProblem.objective` is an attribute of the object ``prob``: .. literalinclude:: ../../../examples/WhiskasModel1.py :lines: 40-41 Running this file should then produce the output to show that Chicken will make up 33.33%, Beef will make up 66.67% and the Total cost of ingredients per can is 96 cents. Full Formulation ---------------- Now we will formulate the problem fully with all the variables. Whilst it could be implemented into Python with little addition to our method above, we will look at a better way which does not mix the problem data, and the formulation as much. This will make it easier to change any problem data for other tests. We will start the same way by algebraically defining the problem: #. Identify the Decision Variables For the Whiskas Cat Food Problem the decision variables are the percentages of the different ingredients we include in the can. Since the can is 100g, these percentages also represent the amount in g of each ingredient included. We must formally define our decision variables, being sure to state the units we are using. .. math:: x_1 &= \text{percentage of chicken meat in a can of cat food}\\ x_2 &= \text{percentage of beef used in a can of cat food}\\ x_3 &= \text{percentage of mutton used in a can of cat food}\\ x_4 &= \text{percentage of rice used in a can of cat food}\\ x_5 &= \text{percentage of wheat bran used in a can of cat food}\\ x_6 &= \text{percentage of gel used in a can of cat food} Note that these percentages must be between 0 and 100. #. 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. We decide the percentage of each ingredient in the can, so we must divide by 100 and multiply by the weight of the can in g. This will give us the weight in g of each ingredient: .. math:: \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 #. Formulate the Constraints The constraints for the Whiskas Cat Food Problem are that: * The sum of the percentages must make up the whole can (= 100%). * The stated nutritional analysis requirements are met. The constraint for the "whole can" is: .. math:: x_1 + x_2 + x_3 + x_4 + x_5 +x _6 = 100 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: .. math:: 0.100 x_1 +0.200 x_2 +0.150 x_3 +0.000 x_4 +0.040 x_5 +0.0 x_6 0&\ge 8.0 \\ 0.080 x_1 +0.100 x_2 +0.110 x_3 +0.010 x_4 +0.010 x_5 0+0.0 x_6 &\ge 6.0 \\ 0.001 x_1 +0.005 x_2 +0.003 x_3 +0.100 x_4 0+0.150 x_5 +0.0 x_6 &\le 2.0 \\ 0.002 x_1 +0.005 x_2 +0.007 x_3 0+0.002 x_4 +0.008 x_5 +0.0 x_6 &\le 0.4 Solution to Full Problem ~~~~~~~~~~~~~~~~~~~~~~~~ To obtain the solution to this Linear Program, we again write a short program in Python to call PuLP's modelling functions, which will then call a solver. This will explain step-by-step how to write this Python program with it's improvement to the above model. It is suggested that you repeat the exercise yourself. The code for this example is found in the :download:`WhiskasModel2.py <../../../examples/WhiskasModel2.py>` As with last time, it is advisable to head your file with commenting on its purpose, and the author name and date. Importing of the PuLP functions is also done in the same way: .. literalinclude:: ../../../examples/WhiskasModel2.py :lines: 1-8 Next, before the ``prob`` variable or type of problem are defined, the key problem data is entered into dictionaries. This includes the list of Ingredients, followed by the cost of each Ingredient, and it's percentage of each of the four nutrients. These values are clearly laid out and could easily be changed by someone with little knowledge of programming. The ingredients are the reference keys, with the numbers as the data. .. literalinclude:: ../../../examples/WhiskasModel2.py :lines: 10-61 The ``prob`` variable is created to contain the formulation, and the usual parameters are passed into :class:`~pulp.LpProblem`. .. literalinclude:: ../../../examples/WhiskasModel2.py :lines: 63-64 A dictionary called ``ingredient_vars`` is created which contains the LP variables, with their defined lower bound of zero. The reference keys to the dictionary are the Ingredient names, and the data is ``Ingr_IngredientName``. (e.g. MUTTON: Ingr_MUTTON) .. literalinclude:: ../../../examples/WhiskasModel2.py :lines: 66-67 Since ``costs`` and ``ingredient_vars`` are now dictionaries with the reference keys as the Ingredient names, the data can be simply extracted with a list comprehension as shown. The :func:`~pulp.lpSum` function will add the elements of the resulting list. Thus the objective function is simply entered and assigned a name: .. literalinclude:: ../../../examples/WhiskasModel2.py :lines: 69-73 Further list comprehensions are used to define the other 5 constraints, which are also each given names describing them. .. literalinclude:: ../../../examples/WhiskasModel2.py :lines: 75-92 Following this, the :meth:`~pulp.LpProblem.writeLP` line etc follow exactly the same as in the simplified example. The optimal solution is 60% Beef and 40% Gel leading to a objective Function value of 52 cents per can.