如何使用 Python 库 PuLP 在线性规划中执行等配给

Question

我将借助以下示例来解释我的问题。

在这个问题中，我有 4 个播放器，数量显示为数量，价格显示为价格。我也有估计的数量作为估计。目标是使用四名玩家的可用数量来完成估计数量。并且选择政策是，价格低的玩家优先供应数量。

price = [140, 50, 80, 60]

quantity = [100, 150, 200, 400]

estimate = 400

所以，对于这道题，每个玩家提供的数量是，

supply = [0, 150, 0, 250]

这只是一个简单的例子，实际数组的大小不止于此。我正在使用 Python 的 PuLP 库来解决这个线性规划问题。

但问题是当所有价格都相等时，它会根据索引给出答案，即index0 的玩家将首先提供，然后是index1 的玩家，依此类推。但是，我的实际要求是在平等定价的情况下，将估计数量平均分配给所有玩家。看例子，

price = [60, 60, 60, 60]

quantity = [100, 150, 200, 400]

estimate = 400

输出是，

supply = [100 , 150, 150, 0]

而我的要求是，

supply = [100, 100, 100, 100]

那么，我的问题是，如何解决均等配给问题？

Answer 1

两个想法：

LP

将加权 penalty-component 引入 objective，它是 supply-vars 的所有 pairwise-differences（absolute-value！）的总和。

优点：

可以公式化为LP

缺点：

这个惩罚的权重是 problem-dependent，需要调整！
对数呈指数增长（关于#supplies）
- 导致 auxiliary-variables 和约束
- 给出一个快速公式，求解器将开始与 N >> 100 作斗争（例如 N=150 需要 10 秒 solve-time；取决于 bigM)
需要 absolute-value re-formulation (lpsolve docs)
- 需要在纸浆中手动完成

SOCP

将加权 penalty-component 引入 objective，即 supply-vars 的 euclidean-norm。

优点：

变量/约束没有指数增长

缺点：

这个惩罚的权重是 problem-dependent，需要调整！
不再是线性的：SOCP-solver 需要（不太稳健）
需要一个 norm-formulation（但如果可以访问 SOCP-solver，这是很自然的）

我没有使用太多的纸浆，并且会从概念上（bigM 未调整；缓慢制定）使用 cvxpy 展示这两种方法，这会自动给我们 abs 和 norm 函数（重新表述）。

代码

import numpy as np
import cvxpy as cvx
from itertools import combinations
np.set_printoptions(suppress=True, precision=6)

# price = np.array([140, 50, 80, 60])
# quantity = np.array([100, 150, 200, 400])

price = np.array([60, 60, 60, 60])
quantity = np.array([100, 150, 200, 400])

estimate = 400

# LP approach
def solve_lp(penalty=True):
    bigM = 1e-3

    N = len(price)
    pairs = list(combinations(range(N), 2))

    x = cvx.Variable(N)
    constraints = [x >= 0,
                   cvx.sum_entries(x) >= estimate,
                   x <= quantity]
    obj_costs = price * x
    obj_penalty = sum([cvx.abs(x[a] - x[b]) for (a,b) in pairs])
    objective = obj_costs + bigM * float(penalty) * obj_penalty

    problem = cvx.Problem(cvx.Minimize(objective), constraints)
    problem.solve(solver='CBC')  # Warning: solver not shipped by default
                                 #          same solver as shipped by pulp
                                 #          = Clp/Cbc
    print(problem.status)
    print(problem.value)
    print(x.value.T)

# QP approach
def solve_socp(penalty=True):
    bigM = 1e-3

    N = len(price)
    est_avg = estimate / N

    x = cvx.Variable(N)
    constraints = [x >= 0,
                   cvx.sum_entries(x) >= estimate,
                   x <= quantity]
    obj_costs = price * x
    obj_penalty = cvx.norm(x - est_avg)
    objective = obj_costs + bigM * float(penalty) * obj_penalty

    problem = cvx.Problem(cvx.Minimize(objective), constraints)
    problem.solve(solver='ECOS')
    print(problem.status)
    print(problem.value)
    print(x.value.T)

print('LP a')
solve_lp(penalty=False)
print('LP b')
solve_lp(penalty=True)
print('SOCP a')
solve_socp(penalty=False)
print('SOCP b')
solve_socp(penalty=True)

输出

LP a
optimal
24000.0
[[100. 100. 200.   0.]]
LP b
optimal
24000.0
[[100. 100. 100. 100.]]
SOCP a
optimal
24000.000032013406
[[ 44.92762   69.401923  93.878797 191.791661]]
SOCP b
optimal
24000.000001071123
[[ 99.999423  99.999973  99.999959 100.000645]]

备注：SOCP 是通过interior-point 方法求解的，该方法近似解（理论上：尽可能准确）。因此值不完全是 100。

如何使用 Python 库 PuLP 在线性规划中执行等配给

How to perform equal rationing in Linear Programming using Python library PuLP

python

linear-programming

LP

SOCP

代码

输出