[PYTHON] Optimization learned with OR-Tools [Linear programming: Let's refine oil]

This blog is what

We will learn mathematical optimization using OR-Tools developed by Google. Most of the content is based on this book. Practical Python AI Projects: Mathematical Models of Optimization Problems with Google OR-Tools (English Edition)

Click here for a list of codes by author The code described in this blog is almost the same as the original one of the author, and it is only partially corrected to Japanese.

Mathematical rigor and theoretical commentary are of low priority. Please forgive me.

This time: Linear programming-oil refinery-

Model a linear program. I don't like linear programming, I'm really sorry. This time, "Let's maximize profits by making the petroleum products you want from the crude oil that is the raw material. Is an example. If it is the amount of crude oil used, it seems that a variable can be allowed even if it is a continuous value, so I think this is an example, maybe.

Scene setting

You are an elementary school student working on your summer vacation homework, an independent study. When you went to the refinery for a social studies tour, you thought, "Make petroleum products efficiently and make a profit ...", so I chose this as the subject of my free research.

Each petroleum product you want to make has an octane number specified, and each crude oil used as a raw material also has an octane number. (It seems that the octane number is unlikely to cause knocking. I didn't know what to look for, so I think it's like alcohol content.) Crude oils with different octane numbers must be mixed nicely to make petroleum products with a specific octane number. The cost per barrel differs depending on the type of crude oil, and the selling price per barrel differs depending on the type of petroleum product. Please see the table as it becomes difficult to understand the meaning in sentences.

An important assumption here is that the octane number of a mixture of crude oil is determined by a linear function. In other words, when crude oil with an octane number of 80 and crude oil with an octane number of 90 are mixed in a ratio of 4: 6,

80\times\frac{4}{10}+90\times\frac{6}{10}=86

Then, a product with an octane number of 86 is born. I feel like I did it because of the problem of the concentration of saline solution.

Now, because you want to maximize your profits, you need to maximize (sales from petroleum products you make)-(costs from crude oil you use).

Formulation

The problem this time is that you want to know "○○ that maximizes profits". What is ○○? "The amount of each crude oil used" is a little insufficient. This is because when you focus on a petroleum product X, you need to know the breakdown of how much crude oil was used to make X. Therefore,

G_{ij}:Amount of crude oil i used for product j

Prepare a variable called. Therefore, the coefficient of determination is defined as a matrix *** (crude oil type) x (product type) ***. I'm happy if I know the contents of this table.

As a result, the total amount of crude oil used R and the total amount of product produced F

R_i = \sum_{j} G_{ij}:Total amount of crude oil i used. Sum in the row direction\\
F_j = \sum_{i} G_{ij}:Total production of product j. Sum in the column direction

Is established. Now you can define the objective function. Assuming that the unit price of crude oil i is $ c_i $ and the selling price of product j is $ p_j $,

max \sum_{j}F_jp_j-\sum_{i}R_ic_i

Is the objective function. Finally, regarding the constraint condition, the constraint on the range that $ R_i and F_j $ can take is troublesome, so I will omit it. Well, you can't use more than you own, or you have to make it within the range of demand.

The important thing this time is the octane number. Crude oil must be mixed so that the product has a specific octane number, not just mixing. Assuming that the octane number of crude oil i is $ O_i $ and the octane number of product j is $ o_j $ (already confusing)

\sum_{i}O_iG_{ij}=F_jo_j\\

Must hold. If this is not met, you will not be able to make the product you want. For the time being, the formulation was completed. Let's implement it.

Implementation

This time, I will introduce only the code that describes the necessary functions. Author GitHub has all the necessary code. Use test_gas_blend.py to run it and my_or_tools.py to make OR-Tools easier to use.

gas_blend.Part of py

from my_or_tools import SolVal,ObjVal,newSolver

def solve_gas(C, D):                                            #List of crude oil,Take a list of products as an argument
  s = newSolver('Gas blending problem')                         #Define solver
  nR,nF = len(C),len(D)                                         #Number of crude oil,Get the number of products
  Roc,Rmax,Rcost = 0,1,2                                        #Octane number of crude oil,Ownership,Expense column number
  Foc,Fmin,Fmax,Fprice = 0,1,2,3                                #Octane number of product,Lower limit of demand,Demand cap,Selling price column number
  G = [[s.NumVar(0.0,10000,'') 
        for j in range(nF)] for i in range(nR)]                 #Prepare a matrix of variables Gij
  R = [s.NumVar(0,C[i][Rmax],'') for i in range(nR)]            #Prepare a variable R that is the sum of the row directions of Gij
  F = [s.NumVar(D[j][Fmin],D[j][Fmax],'') for j in range(nF)]   #Prepare the variable F which is the sum of the column directions of Gij
  for i in range(nR):                                   
    s.Add(R[i] == sum(G[i][j] for j in range(nF)))              #Equality that R should satisfy
  for j in range(nF):
    s.Add(F[j] == sum(G[i][j] for i in range(nR)))              #Equality that F should satisfy
  for j in range(nF):                                     
    s.Add(F[j]*D[j][Foc] ==                                     #Octane number constraints
          s.Sum([G[i][j]*C[i][Roc] for i in range(nR)]))
  Cost = s.Sum(R[i]*C[i][Rcost] for i in range(nR))             #Costs of using crude oil
  Price = s.Sum(F[j]*D[j][Fprice] for j in range(nF))           #Sales from product generation
  s.Maximize(Price - Cost)                                      #Maximize profits
  rc = s.Solve()
  return rc,ObjVal(s),SolVal(G)

Using my_or_tools.py makes it easier to define solvers.

result

The value in the lower right is the profit from this optimal solution.

Takashi was able to submit a free study for the summer vacation safely. I'm happy. Writing formulas and tables in Qiita is difficult. Maybe I'm just not used to it. There is almost no explanation of the algorithm because it is for my own review, and it seems that it will be only formulation and implementation by OR-Tools, I'm sorry.