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)
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:
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).
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")
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
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) |