python - 选择总和为一个值同时最小化另一个值的最佳列

Question

我有一个来自机器学习模型的预测网格。我想选择遵循 3 个标准的最佳预测集。

1. 该id列不能重复
2. 列的总和x需要尽可能x_goal接近
3. 的每个值y都应最小化

示例数据

import numpy as np
import pandas as pd
np.random.seed(10)

x_goal = 20

df = pd.DataFrame({'x':np.random.uniform(1,10,20), 
                   'y':np.random.uniform(0,1,20),
                   'id':list(range(0,4)) * 5})

df.head(10)

          x         y  id
0  7.941886  0.542544   0
1  1.186768  0.142170   1
2  6.702834  0.373341   2
3  7.739235  0.674134   3
4  5.486563  0.441833   0
5  3.023170  0.434014   1
6  2.782566  0.617767   2
7  7.844776  0.513138   3
8  2.521998  0.650397   0
9  1.795058  0.601039   1

示例输出

在这个例子中，我达到了第一个和第三个标准。但是当我希望它尽可能接近 20 时，总和是 24。

opt_1 = df.sort_values(['id', 'y']).groupby('id').first()

print(opt_1['x'].sum())
opt_1

24.455267105201795

           x         y
id
0   7.495798  0.113984
1   1.186768  0.142170
2   9.259967  0.046896
3   6.512735  0.300700

到目前为止，我已经尝试随机选择行，然后检查它是否匹配，x_goal但这很慢并且不能保证找到最佳集合。

欢迎任何建议或帮助！谢谢！

标签： pythonpandasoptimizationdata-science

Answer 1

我对此的解释是：

• 每个 id 最多选择一行
• 这样我们优化了以下两个目标：

1. 所选 x 值的总和应尽可能接近 20
2. 所选 y 值的总和应尽可能小。

这是一个多目标问题。所以一种方法是引入两个权重来确定这两个目标之间的权衡。

我们可以制定以下 MIP 模型：

min w1*absv + w2*ysum
subject to
   xsum = sum(i, df.x[i]*select[i])
   ysum = sum(i, df.y[i]*select[i])
   sum(i, select[i]) <= 1  for each id
   -absv <= xsum - 20 <= absv
   select[i] ∈ {0,1}

这是一些可以使用的 Python 代码：

import pulp as lp

n = df.shape[0] # number of rows in data frame
w = [0.9, 0.1] # weights on objectives
xtarget = 20
K = max(df.id)

prob = lp.LpProblem("SelectRows", lp.LpMinimize)

select = [lp.LpVariable("select{}".format(i),cat=lp.LpBinary) for i in range(n)] 
absv = lp.LpVariable("absv")
ysum = lp.LpVariable("ysum")
xsum = lp.LpVariable("xsum")

prob += w[0]*absv + w[1]*ysum

prob += ysum == lp.lpSum([df.y[i]*select[i] for i in range(n)])
prob += xsum == lp.lpSum([df.x[i]*select[i] for i in range(n)])
prob += -absv <= xsum-20
prob += xsum-20 <= absv
for k in range(K+1):
    prob += lp.lpSum([select[i] for i in range(n) if df.id[i]==k]) <= 1

prob.solve(lp.PULP_CBC_CMD())
print("Status:", lp.LpStatus[prob.status])

print("xsum:{}".format(xsum.value()))
print("ysum:{}".format(ysum.value()))

df["select"] = [round(select[i].value()) for i in range(n)]

输出如下所示：

Status: Optimal
xsum:20.027275
ysum:0.71071352

选定的行是：