Food Manufacture I Example

Both this model and Food Manufacture II are examples of a blending problem. In blending optimization problems, multiple raw materials are combined in a way the meets the stated constraints for the lowest cost. These problems are common in numerous industries including, for example, the oil industry (blending different types of crude oil at a refinery) and agriculture (manufacturing feed that meets the different nutritional requirements of different animals).

In this particular example, we’ll model and solve a production planning problem where we must create a final product from a number of ingredients, each of which has different costs, restrictions and features. The aim is to create an optimal multi-period production plan that maximizes profit. More details can be found on the Problem Description and Model Formulation tabs below.

In Food Manufacture II, we'll extend this example with additional constraints that change the problem type from a linear program (LP) to a mixed integer program (MIP), which makes it harder to solve.

Note: you can download the model, implemented in Python, here. More information on this type of model can be found in the fifth edition of Model Building in Mathematical Programming, by H. Paul Williams.


Reference: H. Paul Williams, Model Building in Mathematical Programming, fifth edition (Page 253-254, 296-298, 349-350)


Problem Description

A manufacturer needs to refine several raw oils and blend them together to produce a given food product that can be sold. The raw oils needed can be divided into two categories:

Category Oil
Vegetable oils: VEG 1
  VEG 2
Non-vegetable oils: OIL 1
  OIL2
  OIL 3

The manufacturer can choose to buy raw oils for the current month and/or buy them on the futures market for delivery in a subsequent month. Prices for immediate deliver and in the futures market are given below in $/ton:

Month VEG 1 VEG 2 OIL 1 OIL 2 OIL 3
January 110 120 130 110 115
February 130 130 110 90 115
March 110 140 130 100 95
April 120 110 120 120 125
May 100 120 150 110 105
June 90 100 140 80 135

There are a number of additional factors that must be taken into account. These include:

  1. The final food product sells for $150 per ton.
  2. Each category of oil (vegetable and non-vegetable) needs to be refined on a different production line.
  3. There is limited refinement capacity such that in any given month a maximum of 200 tons of vegetable oils and 250 tons of non-vegetable oils can be refined.
  4. Also, there is no waste in the refinement process, so the sum of the raw oils refined will equal the amount of refined oils available.
  5. The cost of refining the oils may be ignored.

In addition to the refining limits above, there are limits to the amount of raw oils that can be stored for future use, and there is a cost associated with each ton of oil stored. The limit is 1000 tons of each raw oil and the storage cost is $5 per ton per month. The manufacturer can not store the produced food product or the refined oils.

The final food product must have a hardness between three and six on a given hardness scale. For the purposes of the model, hardness blends linearly and the hardness of each raw oil is:

Oils Hardness
VEG 1 8.8
VEG 2 6.1
OIL 1 2.0
OIL2 4.2
OIL 3 5.0

At the start of January there are 500 tons of each type of raw oil in storage. For the purpose of the model, this should also be the level of raw oils in storage at the end of June.

Given the above information, what monthly buying and manufacturing decisions should be made in order to maximize profit?

This problem is based on a larger model built for the margarine producer Van den Bergs and Jurgens and discussed in Williams and Redwood (1974).

Model Formulation

Let \(T\) be a set of time periods, where \(t_0 \in T\) is the first period and \(t_e \in T\) the last period. Let \(V\) be the set of vegetable oils and \(N\) be the set of non-vegetable oils. We set \(O\) as the union of \(V\) and \(N\). For each time period \(t \in T\) and each oil \(o \in O\) we introduce continuous non-negative variables \(b_{t,o}\), \(u_{t,o}\), \(s_{t,o}\). \(b_{t,o}\) describes how much oil we buy of the type o in the time period \(t\). \(u_{t,o}\) describes how much oil we use of the type o in the time period \(t\). \(s_{t,o}\) describes how much oil we store of the type o in the time period \(t\). For each time period \(t \in T\) we introduce a continuous non-negative variable \(f_t\), that describes how much food is produced in the period \(t\). Furthermore, for each oil \(o \in O\) we are given the positive number \(h_o\), which indicates the hardness of the oil. This is a property of each oil. For each time period \(t \in T\) and each oil \(o \in O\), we are given the estimated purchase price \(g_{t,o}\) for the oil in that period. We are also given the sales price \(p\) for the final product, which is a mix of different oils. Let i be the initial storage amount. The variables can be formulated as \begin{equation} b_{t,o},u_{t,o},s_{t,o} \geq 0 \quad \forall t \in T, \ \forall o \in O \end{equation} \begin{equation} f_t \geq 0 \quad \forall t \in T \end{equation} The balance constraint states that the amount of this kind of oil in the last period and what its bought equals the amount of what is used and stored. This can be formulated as: \begin{equation} s_{t-1,o} + b_{t,o} = u_{t,o}+ s_{t,o} \quad \forall t \in T \setminus t_0, \ \forall o \in O \end{equation} \begin{equation} i + b_{t_0,o} = u_{t_0,o} + s_{t_0,o} \quad \forall o \in O. \end{equation} We set \(s_{t-1,o}=i\) for the first time period \(t_0 \in T\), since there is no period before the first one. The endstore constraints force that at the end of the last period the storage contains the initial amount of each product. The problem description demands that the storage is as full as in the beginning. This can be formulated as: \begin{equation} s_{t_e,o} = i \quad \forall o \in O. \end{equation} The capacity constraints restrict the amount of veg and non-veg oils which can be processed per period. Per month only 200 tons of vegetable oil and 250 tons of non-vegetable oil can be processed to the final product. This can be formulated as: \begin{equation} \sum_{o \in V} u_{t,o} \leq 200 \quad \forall t \in T \end{equation} \begin{equation} \sum_{o \in N} u_{t,o} \leq 250 \quad \forall t \in T. \end{equation} The hardness constraints limit the hardness of the final product, which needs to remain between 3 and 6. Each oil has a certain hardness. The final product may be made up by different oils. The hardness of the final product is measured by the hardness of each ingredient multiplied by its share of the final product. It is assumed that the hardness blends linear. This can be stated as: \begin{equation} 3 f_t \leq \sum_{o \in V} h_o u_{t,o} \leq 6f_t \quad \forall t \in T. \end{equation} The conserve constraints ensure that the amount of products used in each period equals the amount of food produced in that period. This makes sure that all oil that is used is also processed to the final product (food). This can be formulated as: \begin{equation} \sum_{o \in V} u_{t,o} = f_t \quad \forall t \in T. \end{equation} The objective is to maximize the profit of the company. This is calculated as revenue minus costs for buying and storing of the purchased products (ingredients). This can be stated as: \begin{equation} \max \sum_{t \in T} (p f_t) - \sum_{t \in T} \sum_{o \in O} (g_{t,o} u_{t,o}+5 s_{t,o}). \end{equation} The full model can be stated as: \begin{equation} \max \sum_{t \in T} (p f_t) - \sum_{t \in T} \sum_{o \in O} (g_{t,o} u_{t,o}+5 s_{t,o}) \end{equation} \begin{equation} s_{t-1,o} + b_{t,o} = u_{t,o}+ s_{t,o} \quad \forall t \in T \setminus t_0, \ \forall o \in O \end{equation} \begin{equation} i + b_{t_0,o} = u_{t_0,o} + s_{t_0,o} \quad \forall o \in O \end{equation} \begin{equation} s_{t_e,o} = i \quad \forall o \in O \end{equation} \begin{equation} \sum_{o \in V} u_{t,o} \leq 200 \quad \forall t \in T \end{equation} \begin{equation} \sum_{o \in N} u_{t,o} \leq 250 \quad \forall t \in T \end{equation} \begin{equation} 3 f_t \leq \sum_{o \in V} h_o u_{t,o} \leq 6f_t \quad \forall t \in T \end{equation} \begin{equation} \sum_{o \in V} u_{t,o} = f_t \quad \forall t \in T \end{equation} \begin{equation} b_{t,o},u_{t,o},s_{t,o} \geq 0 \quad \forall t \in T, \ \forall o \in O \end{equation} \begin{equation} f_t \geq 0 \quad \forall t \in T \end{equation}

Implementation with comments

First, we import the Gurobi Python Module and initialize the data structures with the given data.

from gurobipy import *

# tested with Python 3.5.2 & Gurobi 7.0.1

time_periods = ["January", "February", "March", "April", "May", "June"]

oils = ["VEG1", "VEG2", "OIL1", "OIL2", "OIL3"]

prices = tupledict({
	('January', 'VEG1'): 110,
	('January', 'VEG2'): 120,
	('January', 'OIL1'): 130,
	('January', 'OIL2'): 110,
	('January', 'OIL3'): 115,
	('February', 'VEG1'): 130,
	('February', 'VEG2'): 130,
	('February', 'OIL1'): 110,
	('February', 'OIL2'): 90,
	('February', 'OIL3'): 115,
	('March', 'VEG1'): 110,
	('March', 'VEG2'): 140,
	('March', 'OIL1'): 130,
	('March', 'OIL2'): 100,
	('March', 'OIL3'): 95,
	('April', 'VEG1'): 120,
	('April', 'VEG2'): 110,
	('April', 'OIL1'): 120,
	('April', 'OIL2'): 120,
	('April', 'OIL3'): 125,
	('May', 'VEG1'): 100,
	('May', 'VEG2'): 120,
	('May', 'OIL1'): 150,
	('May', 'OIL2'): 110,
	('May', 'OIL3'): 105,
	('June', 'VEG1'): 90,
	('June', 'VEG2'): 100,
	('June', 'OIL1'): 140,
	('June', 'OIL2'): 80,
	('June', 'OIL3'): 135
})


hardness = {"VEG1": 8.8, "VEG2": 6.1, "OIL1": 2.0, "OIL2": 4.2, "OIL3": 5.0}

price = 150
IStore = 500
vegCapa = 200
oilCapa = 250

hardness_lb = 3
hardness_ub = 6
store_pricing = 5

Next, we create a model and the variables. For each period we create a variable which will take the value of the food produced. For each product (5 kinds of oils) and each period we will create variables for the amount, which get bought, used and stored.

model = Model('Food Manufacture I')
# Quantity of food produced in each period
food = model.addVars(time_periods, name="Food")
# Quantity bought of each product in each period
buy = model.addVars(time_periods, oils, name = "Buy")
# Quantity used of each product  in each period
use = model.addVars(time_periods, oils, name = "Use")
# Quantity stored of each product  in each period
store = model.addVars(time_periods, oils, name = "Store")

Next, we insert the constraints: The balance constraints ensure that the amount of oil that is in the storage in the last period and the amount that gets purchased equals the amount that is used and stored for each oil in the current period.

#Initial Balance
model.addConstrs((IStore + buy[time_periods[0], oil] ==
     use[time_periods[0], oil] + store[time_periods[0], oil] for oil in oils), "Initial_Balance")

#Balance
model.addConstrs((store[time_periods[time_periods.index(time_period)-1], oil] + buy[time_period, oil] 
     == use[time_period, oil] + store[time_period, oil] for oil in oils for time_period in time_periods 
               if time_period != time_periods[0]), "Balance")

The endstore constraints force that at the end of the last period the storage contains the initial amount of each product.

#End Store
model.addConstrs((store[time_periods[-1], oil] == IStore for oil in oils),"End_Balance")

The capacity constraints restrict the amount of veg and non-veg oils, which can processed per period.

# Capacity1 & Capacity2
model.addConstrs(
	(quicksum(use[time_period, oil] for oil in oils if "VEG" in oil) <= vegCapa
	 for time_period in time_periods), "Capacity_Veg")
model.addConstrs(
	(quicksum(use[time_period, oil] for oil in oils if "OIL" in oil) <= oilCapa
	 for time_period in time_periods), "Capacity_Oil")

The hardness constraints limit the hardness of the final product, which needs to remain between 3 and 6.

# Hardness
model.addConstrs(
	(quicksum(hardness[oil] * use[time_period, oil] for oil in oils)
	 >= hardness_lb * food[time_period] for time_period in time_periods),
	"Hardness_lower")
model.addConstrs(
	(quicksum(hardness[oil] * use[time_period, oil] for oil in oils)
	 <= hardness_ub * food[time_period] for time_period in time_periods),
	"Hardness_upper")

The conserve constraints ensure that the amount of oil used in each period equals the food produced in this period.

# Conserve
model.addConstrs((use.sum(time_period) == food[time_period]
				  for time_period in time_periods), "Conserve")

The objective is to maximize the profit of the company. It includes the revenue as well as the costs for buying and storing of the used products.

# Objective
obj = price*food.sum() - buy.prod(prices) - store_pricing*store.sum()
model.setObjective(obj, GRB.MAXIMIZE) # maximize profit

Next, we start the optimization and Gurobi tries to find the optimal solution.

model.optimize()
for v in model.getVars():
    if v.X != 0:
        print("%s %f" % (v.Varname, v.X))

Note: If you want to write your solution to a file, rather than print it to the terminal, you can use the model.write() command. An example implementation is:

model.write("food-manufacture-i-output.sol")

Gurobi Output and Analysis

Optimize a model with 65 rows, 96 columns and 258 nonzeros
Coefficient statistics:
  Matrix range     [1e+00, 9e+00]
  Objective range  [5e+00, 2e+02]
  Bounds range     [0e+00, 0e+00]
  RHS range        [2e+02, 5e+02]
Presolve removed 28 rows and 45 columns
Presolve time: 0.00s
Presolved: 37 rows, 51 columns, 149 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    5.5261281e+05   9.097405e+03   0.000000e+00      0s
      38    1.0784259e+05   0.000000e+00   0.000000e+00      0s

Solved in 38 iterations and 0.01 seconds
Optimal objective  1.078425926e+05

Analyzing the Output

The profit (revenue from sales − cost of raw oils) resulting from this plan is $107 843. There are alternative optimal solutions.  

Buy Use Store
January Nothing 22.2 tons VEG 1
177.8 tons VEG 2
250 tons OIL 3
477.8 tons VEG 1
322.2 tons VEG 2
500 tons OIL 1
500 tons OIL 2
250 tons OIL 3
February 250 tons OIL 2 200 tons VEG 2
250 tons OIL 3
477.8 tons VEG 1
122.2 tons VEG 2
500 tons OIL 1
750 tons OIL 2
March Nothing 159.3 tons VEG 1
40.7 tons VEG 2
250 tons OIL 2
318.5 tons VEG 1
81.5 tons VEG 2
500 tons OIL 1
460 tons OIL 2
April Nothing 159.3 tons VEG 1
40.7 tons VEG 2
250 tons OIL 2
159.3 tons VEG 1
40.7 tons VEG 2
500 tons OIL 1
250 tons OIL 2
May 500 tons OIL 3 159.3 tons VEG 1
40.7 tons VEG 2
250 tons OIL 2
500 tons OIL 1
500 tons OIL 3
June

659.3 tons VEG 1
540.7 tons VEG 2
750 tons OIL 2
159.3 tons VEG 1
40.7 tons VEG 2
250 tons OIL 2
500 tons each oil (stipulated)