Я использую библиотеку Python для инструмента OR, чтобы решить проблему резки материала. Но в последние несколько дней потребовалось слишком много времени, чтобы ответить. Ответ занимает более 1 минуты.
Я использую код Python в качестве API и передаю приведенные ниже данные.
Данные API:
{
"child_rolls": [
{
"roll": 3,
"size": 1490
},
{
"roll": 8,
"size": 1490
},
{
"roll": 23,
"size": 1500
},
{
"roll": 9,
"size": 1500
},
{
"roll": 8,
"size": 1480
},
{
"roll": 30,
"size": 1480
}
],
"parent_rolls": [
{
"roll": null,
"size": 4470
}
]
}
Когда я передал вышеуказанные данные в API, возврат вывода вышеуказанных данных занял более 1 минуты. Это означает, что когда я передаю большие данные в свой скрипт GCP Python, я получаю медленный ответ. Итак, мне нужна ваша помощь, чтобы улучшить производительность для всех типов данных. Не могли бы вы помочь мне решить эту проблему?
Код Python:
import pdb
import math
from ortools.linear_solver import pywraplp
from math import ceil
from random import randint
import json
# from read_lengths import get_data
# import typer
from typing import Optional
from flask import Flask
from flask_cors import CORS
from flask import request
def newSolver(name, integer=False):
return pywraplp.Solver(name,
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING
if integer else
pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
'''
return a printable value
'''
def SolVal(x):
if type(x) is not list:
return 0 if x is None \
else x if isinstance(x, (int, float)) \
else x.SolutionValue() if x.Integer() is False \
else int(x.SolutionValue())
elif type(x) is list:
return [SolVal(e) for e in x]
def ObjVal(x):
return x.Objective().Value()
def gen_data(num_orders):
R = [] # small rolls
# S=0 # seed?
for i in range(num_orders):
R.append([randint(1, 12), randint(5, 40)])
return R
def solve_model(demands, parent_width=100,parent_main_width=0):
'''
demands = [
[1, 3], # [quantity, width]
[3, 5],
...
]
parent_width = integer
'''
num_orders = len(demands)
solver = newSolver('Cutting Stock', True)
k, b = bounds(demands, parent_width)
# array of boolean declared as int, if y is 1,
# then y Big roll is used, else it was not used
y = [solver.IntVar(0, 1, f'y_{i}') for i in range(k[1])]
# x[j] = 3 means that small-roll width specified by i-th order
# must be cut from j-th order, 3 tmies
x = [[solver.IntVar(0, b, f'x_{i}_{j}') for j in range(k[1])]
for i in range(num_orders)]
# unused_widths = [solver.NumVar(0, parent_width, f'w_{j}')
# for j in range(k[1])]
unused_widths = []
for j in range(k[1]):
print("J",j)
var_name = f'w_{j}'
var = solver.NumVar(0, parent_width, var_name)
unused_widths.append(var)
print(f"Created variable {var_name} with domain [0, {parent_width}] and value {var}.")
#print("SolVal",SolVal(unused_widths))
# will contain the number of big rolls used
nb = solver.IntVar(k[0], k[1], 'nb')
print('1st of nb when intilize',nb)
# consntraint: demand fullfilment
for i in range(num_orders):
# small rolls from i-th order must be at least as many in quantity
# as specified by the i-th order
solver.Add(sum(x[j] for j in range(k[1])) >= demands[0])
# constraint: max size limit
for j in range(k[1]):
# total width of small rolls cut from j-th big roll,
# must not exceed big rolls width
solver.Add(
sum(demands[1]*x[j] for i in range(num_orders))
=
# totall small rolls of i-th order cut from j+1-th big roll
solver.Add(sum(x[j] for i in range(num_orders))
>= sum(x[j+1] for i in range(num_orders)))
# find & assign to nb, the number of big rolls used
solver.Add(nb == solver.Sum(y[j] for j in range(k[1])))
print('2nd nb while executing',nb)
'''
minimize total big rolls used
let's say we have y = [1, 0, 1]
here, total big rolls used are 2. 0-th and 2nd. 1st one is not used. So we want our model to use the
earlier rolls first. i.e. y = [1, 1, 0].
The trick to do this is to define the cost of using each next roll to be higher. So the model would be
forced to used the initial rolls, when available, instead of the next rolls.
So instead of Minimize ( Sum of y ) or Minimize( Sum([1,1,0]) )
we Minimize( Sum([1*1, 1*2, 1*3]) )
'''
'''
Book Author's note from page 201:
There are alternative objective functions. For example, we could have minimized the sum of the waste. This makes sense, especially if the demand constraint is formulated as an inequality. Then minimizing the sum of waste Chapter 7 advanCed teChniques
will spend more CPU cycles trying to find more efficient patterns that over-satisfy demand. This is especially good if the demand widths recur regularly and storing cut rolls in inventory to satisfy future demand is possible. Note that the running time will grow quickly with such an objective function
'''
Cost = solver.Sum((j+1)*y[j] for j in range(k[1]))
# print("Cost == ",Cost)
solver.Minimize(Cost)
# solver.Add(Cost)
#print("COST DATA = ",solver.Minimize(Cost))
status = solver.Solve()
numRollsUsed = SolVal(nb)
#nb, x, w, demands
return status, \
numRollsUsed, \
rolls(numRollsUsed, SolVal(x), SolVal(unused_widths), demands), \
SolVal(unused_widths), \
solver.WallTime()
def bounds(demands, parent_width=100):
'''
b = [sum of widths of individual small rolls of each order]
T = local var. stores sum of widths of adjecent small-rolls. When the width reaches 100%, T is set to 0 again.
k = [k0, k1], k0 = minimum big-rolls requierd, k1: number of big rolls that can be consumed / cut from
TT = local var. stores sum of widths of of all small-rolls. At the end, will be used to estimate lower bound of big-rolls
'''
num_orders = len(demands)
b = []
T = 0
k = [0, 1]
TT = 0
for i in range(num_orders):
# q = quantity, w = width; of i-th order
quantity, width = demands[i][0], demands[i][1]
# TODO Verify: why min of quantity, parent_width/width?
# assumes widths to be entered as percentage
# int(round(parent_width/demands[i][1])) will always be >= 1, because widths of small rolls can't exceed parent_width (which is width of big roll)
b.append( min(demands[i][0], int(round(parent_width / demands[i][1]))) )
#b.append(min(quantity, int(round(parent_width / width))))
# if total width of this i-th order + previous order's leftover (T) is less than parent_width
# it's fine. Cut it.
if T + quantity*width 0] # if i-th order has some cuts from j-th order, x[i][j] would be > 0
print("RR ",RR)
consumed_big_rolls.append(RR)
return consumed_big_rolls
'''
this model starts with some patterns and then optimizes those patterns
'''
def solve_large_model(demands, parent_width=100):
num_orders = len(demands)
iter = 0
patterns = get_initial_patterns(demands)
# print('method#solve_large_model, patterns', patterns)
# list quantities of orders
quantities = [demands[i][0] for i in range(num_orders)]
print('quantities', quantities)
while iter < 20:
status, y, l = solve_master(
patterns, quantities, parent_width=parent_width)
iter += 1
# list widths of orders
widths = [demands[i][1] for i in range(num_orders)]
new_pattern, objectiveValue = get_new_pattern(
l, widths, parent_width=parent_width)
# print('method#solve_large_model, new_pattern', new_pattern)
# print('method#solve_large_model, objectiveValue', objectiveValue)
for i in range(num_orders):
# add i-th cut of new pattern to i-thp pattern
patterns[i].append(new_pattern[i])
status, y, l = solve_master(
patterns, quantities, parent_width=parent_width, integer=True)
return status, \
patterns, \
y, \
rolls_patterns(patterns, y, demands, parent_width=parent_width)
'''
Dantzig-Wolfe decomposition splits the problem into a Master Problem MP and a sub-problem SP.
The Master Problem: provided a set of patterns, find the best combination satisfying the demand
C: patterns
b: demand
'''
def solve_master(patterns, quantities, parent_width=100, integer=False):
title = 'Cutting stock master problem'
num_patterns = len(patterns)
n = len(patterns[0])
# print('**num_patterns x n: ', num_patterns, 'x', n)
# print('**patterns recived:')
# for p in patterns:
# print(p)
constraints = []
solver = newSolver(title, integer)
# y is not boolean, it's an integer now (as compared to y in approach used by solve_model)
y = [solver.IntVar(0, 1000, '') for j in range(n)] # right bound?
# minimize total big rolls (y) used
Cost = sum(y[j] for j in range(n))
solver.Minimize(Cost)
# for every pattern
for i in range(num_patterns):
# add constraint that this pattern (demand) must be met
# there are m such constraints, for each pattern
constraints.append(solver.Add(
sum(patterns[i][j]*y[j] for j in range(n)) >= quantities[i]))
status = solver.Solve()
y = [int(ceil(e.SolutionValue())) for e in y]
l = [0 if integer else constraints[i].DualValue()
for i in range(num_patterns)]
# sl = [0 if integer else constraints[i].name() for i in range(num_patterns)]
# print('sl: ', sl)
# l = [0 if integer else u[i].Ub() for i in range(m)]
toreturn = status, y, l
# l_to_print = [round(dd, 2) for dd in toreturn[2]]
# print('l: ', len(l_to_print), '->', l_to_print)
# print('l: ', toreturn[2])
return toreturn
def get_new_pattern(l, w, parent_width=100):
solver = newSolver('Cutting stock sub-problem', True)
n = len(l)
new_pattern = [solver.IntVar(0, parent_width, '') for i in range(n)]
# maximizes the sum of the values times the number of occurrence of that roll in a pattern
Cost = sum(l[i] * new_pattern[i] for i in range(n))
solver.Maximize(Cost)
# ensuring that the pattern stays within the total width of the large roll
solver.Add(sum(w[i] * new_pattern[i] for i in range(n)) 0:
RR.extend([demands[i][1]] * int(patterns[i][j]))
used_width = sum(RR)
R.append([parent_width - used_width, RR])
return R
'''
checks if all small roll widths (demands) smaller than parent roll's width
'''
def checkWidths(demands, parent_width):
for quantity, width in demands:
if width > parent_width:
print(
f'Small roll width {width} is greater than parent rolls width {parent_width}. Exiting')
return False
return True
'''
params
child_rolls:
list of lists, each containing quantity & width of rod / roll to be cut
e.g.: [ [quantity, width], [quantity, width], ...]
parent_rolls:
list of lists, each containing quantity & width of rod / roll to cut from
e.g.: [ [quantity, width], [quantity, width], ...]
'''
def StockCutter1D(child_rolls, parent_rolls, output_json=True, large_model=True):
# at the moment, only parent one width of parent rolls is supported
# quantity of parent rolls is calculated by algorithm, so user supplied quantity doesn't matter?
# TODO: or we can check and tell the user the user when parent roll quantity is insufficient
# pdb.set_trace()
parent_width_main = parent_rolls[0][1]
qua_arr = []
for item in range(len(child_rolls)):
qua_arr.append(child_rolls[item][1])
# # print(item)
# # print(qua_arr)
# #
if min(qua_arr) parent_width_main:
parent_width = parent_width_main
else:
parent_width = parent_width_second
print("parent_width_main==",parent_width_main)
print("parent_width_second==",parent_width_second)
print("parent_width==",parent_width)
if not checkWidths(demands=child_rolls, parent_width=parent_width):
return []
print('child_rolls', child_rolls)
print('parent_rolls', parent_rolls)
if not large_model:
print('Running Small Model...')
status, numRollsUsed, consumed_big_rolls, unused_roll_widths, wall_time = \
solve_model(demands=child_rolls, parent_width=parent_width,parent_main_width=parent_width_main)
# convert the format of output of solve_model to be exactly same as solve_large_model
print('consumed_big_rolls before adjustment: ', consumed_big_rolls)
new_consumed_big_rolls = []
for big_roll in consumed_big_rolls:
if len(big_roll) < 2:
# sometimes the solve_model return a solution that contanis an extra [0.0] entry for big roll
consumed_big_rolls.remove(big_roll)
continue
unused_width = big_roll[0]
subrolls = []
for subitem in big_roll[1:]:
if isinstance(subitem, list):
# if it's a list, concatenate with the other lists, to make a single list for this big_roll
subrolls = subrolls + subitem
else:
# if it's an integer, add it to the list
subrolls.append(subitem)
new_consumed_big_rolls.append([unused_width, subrolls])
print('consumed_big_rolls after adjustment: ', new_consumed_big_rolls)
consumed_big_rolls = new_consumed_big_rolls
else:
print('Running Large Model...')
status, A, y, consumed_big_rolls = solve_large_model(
demands=child_rolls, parent_width=parent_width)
numRollsUsed = len(consumed_big_rolls)
# print('A:', A, '\n')
# print('y:', y, '\n')
STATUS_NAME = ['OPTIMAL',
'FEASIBLE',
'INFEASIBLE',
'UNBOUNDED',
'ABNORMAL',
'NOT_SOLVED'
]
output = {
"statusName": STATUS_NAME[status],
"numSolutions": '1',
"numUniqueSolutions": '1',
"numRollsUsed": numRollsUsed,
"solutions": consumed_big_rolls # unique solutions
}
# print('Wall Time:', wall_time)
print('numRollsUsed', numRollsUsed)
print('Status:', output['statusName'])
print('Solutions found :', output['numSolutions'])
print('Unique solutions: ', output['numUniqueSolutions'])
if output_json:
return output
else:
return consumed_big_rolls
'''
Draws the big rolls on the graph. Each horizontal colored line represents one big roll.
In each big roll (multi-colored horizontal line), each color represents small roll to be cut from it.
If the big roll ends with a black color, that part of the big roll is unused width.
TODO: Assign each child roll a unique color
'''
if __name__ == '__main__':
app = Flask(__name__)
# Enable the CORS
CORS(app, resources={r"/*": {"origins": "*"}})
@app.route("/")
def index():
return "This is index page, please go ahead...! "
@app.route("/track", methods=['POST'])
def track():
try:
print('request.data==', request.get_json())
req_data = request.get_json()
child_rolls = []
parent_rolls = []
child_rolls_obj = req_data.get('child_rolls', [])
for item in child_rolls_obj:
data = list(item.values())
# data.reverse()
child_rolls.append(data)
parent_rolls_obj = req_data.get('parent_rolls', [])
parent_rolls.append(list(parent_rolls_obj[0].values()))
# pdb.set_trace()
# number_of_cut = req_data.get('number_of_cut', [])
if(not(len(child_rolls) and len(parent_rolls))):
return {"success": False, "message": "Request data is not enough!"}
consumed_big_rolls = StockCutter1D(
child_rolls, parent_rolls, output_json=True, large_model=False)
# return {"success": True, "data": {"solutions": consumed_big_rolls}}
return consumed_big_rolls
except Exception as error:
return {"success": False, "message": "Something went wrong!", "error": error}
# raise error
app.config["FLASK_APP"] = 'main.py'
app.config["FLASK_ENV"] = 'development'
app.run(host="0.0.0.0", debug=True, port=5000, use_reloader=False)
Ожидаемый результат будет таким:
{
"numRollsUsed": 29,
"numSolutions": "1",
"numUniqueSolutions": "1",
"solutions": [ < b r / > [ < b r / > 0 . 0 , < b r / > [ < b r / > 1 4 9 0 , < b r / > 1 5 0 0 , < b r / > 1 4 8 0 < b r / > ]
],
[
0.0,
[
1490,
1500,
1480
]
],
[
29.999999999999957,
[
1480,
1480,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
0.0,
[
1490,
1500,
1480
]
],
[
0.0,
[
1490,
1500,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
0.0,
[
1490,
1500,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
0.0,
[
1490,
1500,
1480
]
],
[
0.0,
[
1490,
1500,
1480
]
],
[
29.999999999999957,
[
1480,
1480,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
0.0,
[
1490,
1500,
1480
]
],
[
10.000000000000151,
[
1500,
1480,
1480
]
],
[
0.0,
[
1490,
1490,
1490
]
],
[
1469.9999999999998,
[
1500,
1500
]
],
[
1469.9999999999998,
[
1500,
1500
]
],
[
1469.9999999999998,
[
1500,
1500
]
],
[
1469.9999999999998,
[
1500,
1500
]
],
[
1469.9999999999998,
[
1500,
1500
]
],
[
1469.9999999999998,
[
1500,
1500
]
]
],
"statusName": "OPTIMAL"
}
Подробнее здесь: https://stackoverflow.com/questions/759 ... e-or-tools
