线性规划 - 最大值优化
Gal*_*lgo 7 python optimization linear-programming maximize pandas
我试图找到可以最大化我的总和值的最佳组合，但它必须在 2 个特定约束下，因此我假设线性规划将是最合适的。
问题是这样的：一些教育世界事件希望聚集世界上最聪明的青少年学生。每个州都对 10 万名学生进行了以下考试：“数学”、“英语”、“计算机”、“历史”、“物理”……并且在每次考试中都获得了 0-100 分。
每个州都被要求从经过测试的 100K 学生中发送他们最好的 10K 参加此次活动。
您作为法国代表，被要求从您所在国家/地区的 10 万名学生中选出前 1 万名学生。为此，您需要优化它们的 MAX VALUE 以获得最佳的 TOTAL SCORE。
但是有两个主要限制：
1- 从总共 10K 选择的学生中，您需要分配特定的学生，这些学生将仅在上述 5 个科目中的 1 个特定科目上进行测试。所需的分配是： ['MATH': 4000, 'ENGLISH':3000,'COMPUTERS':2000, 'HISTORY':750,'PHYSICS':250]
2- 每个“考试科目”的分数必须有不同的权重。对于 exp：97 是数学在历史上的价值超过 97。wheights 是：['数学'：1.9，'英文'：1.7，'计算机'：1.5，'历史'：1.3，'物理'：1.1]
我的解决方案： 我尝试使用 PULP (python) 作为 LP 库并正确解决了它，但运行时间超过 2 小时。 你能找到更好（更快、更简单……）的方法来解决它吗？ 有一些 NUMPY LP 函数可以用来代替，也许会更快？它应该是一个简单的优化问题，因为我让它变得太慢和复杂。 -- 解决方案只需要在 Python 中
例如，让我们小规模地看一下同一问题：有 30 名学生，您只需要选择 15 名学生，这将为我们提供与以下学科分配需求相关的最佳组合。所需的分配是- ['数学'：5，'英文'：4，'计算机'：3，'历史'：2，'物理'：1]
这是所有 30 名学生及其成绩：
运行算法后，输出解决方案将是：
这是我原始问题的完整代码（10 万名学生）：
import pandas as pd
import numpy as np
import pulp as p
import time
t0=time.time()
demand = [4000, 3000, 2000, 750,250]
weight = [1.9,1.7, 1.5, 1.3, 1.1]
original_data= pd.read_csv('GRADE_100K.csv') #created simple csv file with random scores
data_c=original_data.copy()
data_c.index = np.arange(1, len(data_c)+1)
data_c.columns
data_c=data_c[['STUDENT_ID', 'MATH', 'ENGLISH', 'COMPUTERS', 'HISTORY','PHYSICS']]
#DataFrame Shape
m=data_c.shape[1]
n=data_c.shape[0]
data=[]
sublist=[]
for j in range(0,n):
for i in range(1,m):
sublist.append(data_c.iloc[j,i])
data.append(sublist)
sublist=[]
def _get_num_students(data):
return len(data)
def _get_num_subjects(data):
return len(data[0])
def _get_weighted_data(data, weight):
return [
[a*b for a, b in zip(row, weight)]
for row in data
]
data = _get_weighted_data(data, weight)
num_students = _get_num_students(data)
num_subjects = _get_num_subjects(data)
# Create a LP Minimization problem
Lp_prob = p.LpProblem('Problem', p.LpMaximize)
# Create problem Variables
variables_matrix = [[0 for i in range(num_subjects)] for j in range(num_students)]
for i in range(0, num_students):
for j in range(0, num_subjects):
variables_matrix[i][j] = p.LpVariable(f"X({i+1},{j+1})", 0, 1, cat='Integer')
df_d=pd.DataFrame(data=data)
df_v=pd.DataFrame(data=variables_matrix)
ml=df_d.mul(df_v)
ml['coeff'] = ml.sum(axis=1)
coefficients=ml['coeff'].tolist()
# DEALING WITH TARGET FUNCTION VALUE
suming=0
k=0
sumsum=[]
for z in range(len(coefficients)):
suming +=coefficients[z]
if z % 2000==0:
sumsum.append(suming)
suming=0
if z<2000:
sumsum.append(suming)
sumsuming=0
for s in range(len(sumsum)):
sumsuming=sumsuming+sumsum[s]
Lp_prob += sumsuming
# DEALING WITH the 2 CONSTRAINS
# 1-subject constraints
con1_suming=0
for e in range(num_subjects):
L=df_v.iloc[:,e].to_list()
for t in range(len(L)):
con1_suming +=L[t]
Lp_prob += con1_suming <= demand[e]
con1_suming=0
# 2- students constraints
con2_suming=0
for e in range(num_students):
L=df_v.iloc[e,:].to_list()
for t in range(len(L)):
con2_suming +=L[t]
Lp_prob += con2_suming <= 1
con2_suming=0
print("time taken for TARGET+CONSTRAINS %8.8f seconds" % (time.time()-t0) )
t1=time.time()
status = Lp_prob.solve() # Solver
print("time taken for SOLVER %8.8f seconds" % (time.time()-t1) ) # 632 SECONDS
print(p.LpStatus[status]) # The solution status
print(p.value(Lp_prob.objective))
df_v=pd.DataFrame(data=variables_matrix)
# Printing the final solution
lst=[]
val=[]
for i in range(0, num_students):
lst.append([p.value(variables_matrix[i][j]) for j in range(0, num_subjects)])
val.append([sum([p.value(variables_matrix[i][j]) for j in range(0, num_subjects)]),i])
ones_places=[]
for i in range (0, len(val)):
if val[i][0]==1:
ones_places.append(i+1)
len(ones_places)
data_once=data_c[data_c['STUDENT_ID'].isin(ones_places)]
IDs=[]
for i in range(len(ones_places)):
IDs.append(data_once['STUDENT_ID'].to_list()[i])
course=[]
sub_course=[]
for i in range(len(lst)):
j=0
sub_course='x'
while j<len(lst[i]):
if lst[i][j]==1:
sub_course=j
j=j+1
course.append(sub_course)
coures_ones=[]
for i in range(len(course)):
if course[i]!= 'x':
coures_ones.append(course[i])
# adding the COURSE name to the final table
# NUMBER OF DICTIONARY KEYS based on number of COURSES
col=original_data.columns.values[1:].tolist()
dic = {0:col[0], 1:col[1], 2:col[2], 3:col[3], 4:col[4]}
cc_name=[dic.get(n, n) for n in coures_ones]
one_c=[]
if len(IDs)==len(cc_name):
for i in range(len(IDs)):
one_c.append([IDs[i],cc_name[i]])
prob=[]
if len(IDs)==len(cc_name):
for i in range(len(IDs)):
prob.append([IDs[i],cc_name[i], data_once.iloc[i][one_c[i][1]]])
scoring_table = pd.DataFrame(prob,columns=['STUDENT_ID','COURES','SCORE'])
scoring_table.sort_values(by=['COURES', 'SCORE'], ascending=[False, False], inplace=True)
scoring_table.index = np.arange(1, len(scoring_table)+1)
print(scoring_table)
以下是关于我使用最小成本流的想法的更多想法。
我们通过采用 4 层有向图来模拟这个问题，其中每一层都完全连接到下一层。
节点
s第一层：将作为我们的源的单个节点。第二层：每个学生一个节点。
第三层：每个主题一个节点。
第四层：OA单节点
t，这将是我们的漏斗。
边缘容量
第一 -> 第二：所有边的容量均为 1。
第二 -> 第三：所有边的容量均为 1。
第三 -> 第四：所有边的容量都与必须分配给该科目的学生人数相对应。
边缘成本
第一 -> 第二：所有边的成本均为 0。
第二 -> 第三：请记住，该层中的边缘将学生与主题连接起来。这些费用的选择将与学生在该科目上的加权分数成反比。
cost = -subject_weight*student_subject_score。第三 -> 第四：所有边的成本均为 0。
s然后我们要求从到 的流量t等于我们必须选择的学生数量。
为什么这有效？
通过将第三层和第四层之间的所有边作为分配，最小成本流问题的解决方案将对应于您的问题的解决方案。
每个学生最多可以选择一门科目，因为对应的节点只有一条传入边。
每个科目都有所需的学生人数，因为传出容量对应于我们必须为该科目选择的学生人数，并且我们必须使用这些边的全部容量，否则我们无法满足流量需求。
MCF 问题的最小解对应于问题的最大解，因为成本对应于它们给出的值。
当您在 python 中寻求解决方案时，我使用 ortools 实现了最小成本流问题。在我的 Colab 笔记本中找到解决方案只花了不到一秒钟的时间。需要“长时间”的是溶液的提取。但包括设置和解提取在内，对于完整的 100000 个学生问题，我的运行时间仍然少于 20 秒。
代码
# imports
from ortools.graph import pywrapgraph
import numpy as np
import pandas as pd
import time
t_start = time.time()
# setting given problem parameters
num_students = 100000
subjects = ['MATH', 'ENGLISH', 'COMPUTERS', 'HISTORY','PHYSICS']
num_subjects = len(subjects)
demand = [4000, 3000, 2000, 750, 250]
weight = [1.9,1.7, 1.5, 1.3, 1.1]
# generating student scores
student_scores_raw = np.random.randint(101, size=(num_students, num_subjects))
# setting up graph nodes
source_nodes = [0]
student_nodes = list(range(1, num_students+1))
subject_nodes = list(range(num_students+1, num_subjects+num_students+1))
drain_nodes = [num_students+num_subjects+1]
# setting up the min cost flow edges
start_nodes = [int(c) for c in (source_nodes*num_students + [i for i in student_nodes for _ in subject_nodes] + subject_nodes)]
end_nodes = [int(c) for c in (student_nodes + subject_nodes*num_students + drain_nodes*num_subjects)]
capacities = [int(c) for c in ([1]*num_students + [1]*num_students*num_subjects + demand)]
unit_costs = [int(c) for c in ([0.]*num_students + list((-student_scores_raw*np.array(weight)*10).flatten()) + [0.]*num_subjects)]
assert len(start_nodes) == len(end_nodes) == len(capacities) == len(unit_costs)
# setting up the min cost flow demands
supplies = [sum(demand)] + [0]*(num_students + num_subjects) + [-sum(demand)]
# initialize the min cost flow problem instance
min_cost_flow = pywrapgraph.SimpleMinCostFlow()
for i in range(0, len(start_nodes)):
min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i], capacities[i], unit_costs[i])
for i in range(0, len(supplies)):
min_cost_flow.SetNodeSupply(i, supplies[i])
# solve the problem
t_solver_start = time.time()
if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:
print('Best Value:', -min_cost_flow.OptimalCost()/10)
print('Solver time:', str(time.time()-t_solver_start)+'s')
print('Total Runtime until solution:', str(time.time()-t_start)+'s')
#extracting the solution
solution = []
for i in range(min_cost_flow.NumArcs()):
if min_cost_flow.Flow(i) > 0 and min_cost_flow.Tail(i) in student_nodes:
student_id = min_cost_flow.Tail(i)-1
subject_id = min_cost_flow.Head(i)-1-num_students
solution.append([student_id, subjects[subject_id], student_scores_raw[student_id, subject_id]])
assert(len(solution) == sum(demand))
solution = pd.DataFrame(solution, columns = ['student_id', 'subject', 'score'])
print(solution.head())
else:
print('There was an issue with the min cost flow input.')
print('Total Runtime:', str(time.time()-t_start)+'s')
通过以下列表理解替换上述代码中解决方案提取的 for 循环（也不是每次迭代都不使用列表查找），可以显着改善运行时间。但出于可读性的原因，我也将这个旧的解决方案留在这里。这是新的：
solution = [[min_cost_flow.Tail(i)-1,
subjects[min_cost_flow.Head(i)-1-num_students],
student_scores_raw[min_cost_flow.Tail(i)-1, min_cost_flow.Head(i)-1-num_students]
]
for i in range(min_cost_flow.NumArcs())
if (min_cost_flow.Flow(i) > 0 and
min_cost_flow.Tail(i) <= num_students and
min_cost_flow.Tail(i)>0)
]
以下输出给出了新的更快实现的运行时间。
输出
Best Value: 1675250.7
Solver time: 0.542395830154419s
Total Runtime until solution: 1.4248979091644287s
student_id subject score
0 3 ENGLISH 99
1 5 MATH 98
2 17 COMPUTERS 100
3 22 COMPUTERS 100
4 33 ENGLISH 100
Total Runtime: 1.752336025238037s
请指出我可能犯的任何错误。
我希望这有帮助。;)