CS代考 Solving LPs with Gurobi

Solving LPs with Gurobi
Solving Linear Programs with Gurobi Optimizer¶
This notebook contains two examples of how to formulate and solve linear programs using Python and Gurobi. The first example is the “Bag Production” problem from class. The second example is the “Product Delivery” example from class.
Example 1: Bag Production¶
Recall that the linear program for the bag production problem is given by
\begin{align}
\underset{x_S, x_D}{\text{max}} \;\; & 10 x_s + 8 x_D\\
\text{s.t.} \;\; &\frac{7}{10} x_S + x_D \le 630 \\
& \frac{1}{2} x_S + \frac{5}{6} x_D \le 600 \\
& x_S + \frac{2}{3} x_D \le 708 \\
& \frac{1}{10}x_S + \frac{1}{4} x_D \le 135 \\
& x_S, x_D \ge 0.
\end{align}To solve the LP above, we first load the Gurobi module into Python.
from gurobipy import *
We will now formulate the LP using functions provided by the Gurobi module.
# Construct a ‘blank’ model.
mod = Model()
# Define decision variables. We will use variable names ‘S’ and ‘D’ for simplicity.
S = mod.addVar()
D = mod.addVar()
# Construct constraints.
cutting_con = mod.addConstr((7/10)*S + D <= 630) sewing_con = mod.addConstr((1/2)*S + (5/6)*D <= 600) finishing_con = mod.addConstr(S + (2/3)*D <= 708) inspecting_con = mod.addConstr((1/10)*S + (1/4)*D <= 135) # Add non-negativity constraints. mod.addConstr(S >= 0.0)
mod.addConstr(D >= 0.0)
# Create the objective function, and set it to be maximized.
mod.setObjective(10*S + 9*D, GRB.MAXIMIZE)
Set parameter Username
Academic license – for non-commercial use only – expires 2022-03-03
We now push the updated constraints and objective to the blank model.
mod.update()
Now that the model is set up, we can call Gurobi to solve it.
mod.optimize()
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (mac64[rosetta2])
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 6 rows, 2 columns and 10 nonzeros
Model fingerprint: 0xf5068f88
Coefficient statistics:
Matrix range [1e-01, 1e+00]
Objective range [9e+00, 1e+01]
Bounds range [0e+00, 0e+00]
RHS range [1e+02, 7e+02]
Presolve removed 2 rows and 0 columns
Presolve time: 0.01s
Presolved: 4 rows, 2 columns, 8 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 9.0000000e+03 4.791138e+01 0.000000e+00 0s
2 7.6680000e+03 0.000000e+00 0.000000e+00 0s
Solved in 2 iterations and 0.01 seconds (0.00 work units)
Optimal objective 7.668000000e+03
After we solve the problem, we can retrieve the optimal solution found by Gurobi and the associated optimal value.
# Extract the solution status.
if mod.status == GRB.OPTIMAL:
print(“Solved to optimality”)
# Extract the optimal values of the decision variables.
S_opt = S.x
D_opt = D.x
print(“Number of Standard bags: “, S_opt)
print(“Number of Deluxe bags: “, D_opt)
# Retrieve the optimal value.
opt_val = mod.objval
print(“Optimal profit:”, opt_val)
Solved to optimality
Number of Standard bags: 539.9999999999999
Number of Deluxe bags: 252.0000000000001
Optimal profit: 7668.0
Example 2: Product Delivery¶
For the product delivery problem, it may be impractical to write the constraints explicitly if the number of warehouses and/or customers is large. Instead, we will import the data from .csv files. Recall that the linear program is given by
\begin{align}
\underset{{\bf x}}{\text{min}} \;\; & \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij} \\
\text{s.t.} & \sum_{i=1}^m x_{ij} \ge d_j, \quad j = 1,2,\ldots,n, \\
& \sum_{j=1}^n x_{ij} \le s_i, \quad i = 1,2,\ldots,m, \\
& x_{ij} \ge 0, \quad i = 1,2,\ldots,m, \; j = 1,2,\ldots,n.
\end{align}First, we read in the model parameters using the numpy package.
from numpy import genfromtxt
demand = genfromtxt(‘demand.csv’, delimiter=’,’)
supply = genfromtxt(‘supply.csv’, delimiter=’,’)
cost = genfromtxt(‘cost.csv’, delimiter=’,’)
We now formulate the constraints and objective.
# Define the data
# Initialize the model
mod = Model()
# Define variables
# mod.addVars(m,n) will create variables where rows are indexed from 0 to m-1 and columns are indexed from 0 to n-1
x = mod.addVars(m,n)
# Constraint: All demands must be satisfied
demand_con = {}
for j in range(n):
demand_con[j] = mod.addConstr(sum(x[i,j] for i in range(m)) >= demand[j])
# Constraint: Total delivery from each warehouse cannot exceed available supply
supply_con = {}
for i in range(m):
supply_con[j] = mod.addConstr(sum(x[i,j] for j in range(n)) <= supply[i]) # Nonnegativity constraints: for i in range(m): for j in range(n): mod.addConstr(x[i,j] >= 0.0)
# Construct objective
mod.setObjective(sum(cost[i][j] * x[i,j] for i in range(m) for j in range(n)), GRB.MINIMIZE)
Note that the constraints are written in a form that closely resemble the mathematical expressions in the LP formulation — this readability is one of the advantages of using the Gurobi package in Python to build and solve optimization models.
Next, we update and solve the model.
# Update and solve
mod.update()
mod.optimize()
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (mac64[rosetta2])
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 5510 rows, 5000 columns and 15000 nonzeros
Model fingerprint: 0x15cb881c
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [5e-06, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [4e-03, 1e+02]
Presolve removed 5000 rows and 0 columns
Presolve time: 0.01s
Presolved: 510 rows, 5000 columns, 10000 nonzeros
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 3.142678e+01 0.000000e+00 0s
577 2.5642351e+01 0.000000e+00 0.000000e+00 0s
Solved in 577 iterations and 0.02 seconds (0.01 work units)
Optimal objective 2.564235109e+01
Observe that the output provides the number of simplex algorithm iterations taken to solve the LP.
As in Example 1, we can now retrieve the optimal solution and optimal value.
# Retrieve optimal value and optimal solution
opt_val = mod.objval
print(“Optimal cost:”,opt_val)
x_opt = [x[i,j].x for i in range(m) for j in range(n)]
print(x_opt)
Optimal cost: 25.642351091747752
[0.0, 0.0, 0.79442612, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.65808973, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.62451576, 0.18313888, 0.0, 0.89630676, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.99956897, 0.55641985, 0.0, 0.0, 0.0, 0.0, 0.0, 0.80288216, 0.0, 0.0, 0.0, 0.65559661, 0.0, 0.0, 0.0, 0.0, 0.27034121, 0.0, 0.0, 0.0, 0.0, 0.49900153, 0.0, 0.0, 0.78831782, 0.0, 0.47949353, 0.0, 0.68921674, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.68327286, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.34346244, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.74789833, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.83729652, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.6044689, 0.71418836, 0.25696758, 0.0, 0.65410904, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.29523295, 0.0, 0.71142798, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.82216781, 0.61511221, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.60749366, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.53247743, 0.0, 0.0, 0.87951413, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.24322004, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.64217539, 0.0, 0.0, 0.78389377, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.39841906, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.78886239, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.9944148, 0.0, 0.0, 0.0, 0.0, 0.0, 0.75202846, 0.0, 0.0, 0.0, 0.37660098, 0.0, 0.0, 0.0, 0.0, 0.0, 0.40711552, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.88524399, 0.0, 0.0, 0.33894856, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.85510668, 0.0, 0.0, 0.82595163, 0.0, 0.23044472, 0.0, 0.53349888, 0.769709, 0.12009485, 0.46545708, 0.0, 0.18887598, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.06129547, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.78452388, 0.0, 0.30347989, 0.0, 0.0, 0.78159635, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.73861539, 0.68983163, 0.0, 0.0, 0.0, 0.0, 0.90706408, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.04510912, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.6252557, 0.0, 0.0, 0.0, 0.55196388, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.21006282, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.30526007, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.80368767, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.03169356, 0.0, 0.0, 0.812815, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.46898984, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.16468573, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.08971565, 0.0, 0.0, 0.0, 0.0, 0.79611923, 0.0, 0.0, 0.0, 0.0, 0.0, 0.16333193, 0.0, 0.0, 0.0, 0.0, 0.14976528, 0.89585154, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.76567006, 0.0, 0.0, 0.0, 0.0, 0.125552, 0.0, 0.16270587, 0.0, 0.69852052, 0.96277179, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.41947836, 0.0, 0.96718217, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.20031325, 0.0, 0.0, 0.73540839, 0.0, 0.0, 0.0, 0.0, 0.61412336, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.01375895, 0.0, 0.0, 0.0, 0.0, 0.10673528, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.54752225, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.97173771, 0.0, 0.0, 0.0, 0.0, 0.0, 0.4471811, 0.0, 0.54428102, 0.0, 0.0, 0.0, 0.0, 0.6719484, 0.0, 0.0, 0.48049689, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.15425341, 0.0, 0.0, 0.0, 0.0, 0.23290269, 0.39158843, 0.0, 0.53174474, 0.0, 0.18590074, 0.0, 0.0, 0.0, 0.53846803, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.65138968, 0.15520205, 0.0, 0.0, 0.0, 0.0, 0.72278534, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.02887738, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.53716856, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.96793019, 0.0, 0.0, 0.0, 0.0, 0.0, 0.45214915, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.34305754, 0.0, 0.0, 0.0, 0.28667711, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.71830324, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.70860971, 0.0, 0.12430757, 0.0, 0.0, 0.81666956, 0.54753283, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.7075335, 0.0, 0.0, 0.0, 0.0, 0.0, 0.08553424, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.24089405, 0.0, 0.0, 0.0, 0.0, 0.56367924, 0.0, 0.0, 0.78928187, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.73799094, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.08279635, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.6369076, 0.0, 0.0, 0.0, 0.0, 0.60180362, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.21346292, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.08978604, 0.0, 0.10215484, 0.0, 0.26847091, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.49512499, 0.0, 0.63268411, 0.0, 0.0, 0.0, 0.0, 0.0, 0.56013016, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.92134764, 0.0, 0.0, 0.0, 0.61752472, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.43470017, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.33086002, 0.0, 0.0, 0.0, 0.32076487, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.95557452, 0.48775157, 0.0, 0.0, 0.12789412, 0.19459782, 0.0, 0.00614059, 0.0, 0.0, 0.0, 0.0, 0.0, 0.59479603, 0.0, 0.0, 0.0, 0.0, 0.10552198, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.68336638, 0.17853768, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.60617619, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.4967224, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.69313551, 0.0, 0.95152569, 0.0, 0.0, 0.0, 0.0, 0.83829985, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.13016578, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.9055699, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.41448913, 0.0, 0.0, 0.0, 0.16491902, 0.52816711, 0.0, 0.14652309, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.36582963, 0.0, 0.0, 0.0, 0.0, 0.21633807, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.49491574, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.72516145, 0.0, 0.0, 0.0, 0.02053143, 0.0, 0.66886132, 0.60673112, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.12005222, 0.0, 0.0, 0.21504648, 0.0, 0.0, 0.16794043, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.08152387, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.62489654, 0.55684536, 0.0, 0.2784095, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.59071693, 0.0, 0.0, 0.0, 0.0, 0.50536709, 0.0, 0.0, 0.0, 0.0, 0.0, 0.38908391, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.29631184, 0.0, 0.0, 0.0, 0.0, 0.76269853, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.97748396, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.91599727, 0.0, 0.0, 0.0, 0.0, 0.08376819, 0.0, 0.0, 0.0, 0.95405573, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.82632236, 0.0, 0.0, 0.0, 0.60744594, 0.33600765, 0.0, 0.0, 0.0, 0.0, 0.50269476, 0.0, 0.22494446999999745, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.54123886, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.19779855, 0.0, 0.0, 0.0, 0.43167288, 0.55778485, 0.0, 0.0, 0.87313383, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.09897014, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.19003552, 0.0, 0.6540494, 0.0, 0.0, 0.0, 0.3992156, 0.0, 0.21738805, 0.0, 0.54692815, 0.0, 0.0, 0.0, 0.0, 0.0, 0.7961825, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.5151042, 0.0, 0.0, 0.0, 0.1453343, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.74195755, 0.0, 0.0, 0.96352103, 0.77983661, 0.0, 0.0, 0.0, 0.93860458, 0.0, 0.0, 0.0, 0.70178237, 0.0, 0.67804845, 0.0, 0.0, 0.0, 0.0, 0.63886541, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.21841469, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.13617821, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.82440298, 0.0, 0.0, 0.36201799, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.23699816, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.42844356, 0.7761263, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.85974082, 0.0, 0.0, 0.0, 0.0, 0.33427644, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.71842703, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.80405936, 0.8683312, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.21005182, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.9005975, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.22960069, 0.0, 0.0, 0.0, 0.0, 0.0, 0.81859792, 0.0, 0.0, 0.0, 0.0, 0.0, 0.43781127, 0.0, 0.34310689, 0.0, 0.86316634, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.26404933, 0.0, 0.0, 0.0, 0.0, 0.0, 0.37266922, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.8342229, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.12058088, 0.0, 0.0, 0.0, 0.0, 0.0, 0.47438722, 0.0, 0.51312771, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0706934, 0.0, 0.0, 0.0, 0.40746728, 0.0, 0.0, 0.0, 0.0, 0.56849735, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.64448426, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.86950951, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.72551629, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.56774902, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.65857106, 0.0, 0.72121264, 0.0, 0.0, 0.36337362, 0.0, 0.0, 0.0, 0.0, 0.0, 0.04349403, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.68111873, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.571495, 0.02802203, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.3159536, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.79193731, 0.0, 0.0, 0.0, 0.0, 0.15511798, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.66348003, 0.0, 0.0, 0.7735105, 0.0, 0.0, 0.27409927, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.43413189999999247, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.04863476, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.59955671, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.79596457, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.68446896, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,