将步长添加到线性优化

Question

我正在处理类似于 pulp example

的混合问题

我有这个限制，以确保生产的数量符合要求

prob += lpSum([KG[i] * deposit_vars[i] for i in deposit]) == 64, "KGRequirement"

但我还需要为不同于零的最小值添加另一个约束，这是因为我不方便，例如，0.002KG 的一种成分，我必须取 0 或至少 2 公斤，因此有效的案例是例如0、2、2.3、6、3.23。

我试过这样做：

for i in deposit:
    prob += (KG[i] * deposit_vars[i] == 0) or (TM[i] * deposit_vars[i] >= 30)

但这不起作用，只会使问题不可行

编辑

这是我当前的代码：

import pulp
from pulp import *
import pandas as pd

food = ["f1","f2","f3","f4"]
KG = [10,20,50,80]
Protein =       [18,12,16,18]
Grass = [13,14,13,16]
price_per_kg =  [15,11,10,22]

##            protein,carbohydrates,kg

df = pd.DataFrame({"tkid":food,"KG":KG,"Protein":Protein,"Grass":Grass,"value":price_per_kg})


deposit =  df["tkid"].values.tolist()

factor_volumen = 1



costs =  dict((k,v) for k,v in zip(df["tkid"],df["value"]))
Protein =  dict((k,v) for k,v in zip(df["tkid"],df["Protein"]))
Grass =  dict((k,v) for k,v in zip(df["tkid"],df["Grass"]))
KG =  dict((k,v) for k,v in zip(df["tkid"],df["KG"]))

prob = LpProblem("The Whiskas Problem", LpMinimize)
deposit_vars = LpVariable.dicts("Ingr",deposit,0)
prob += lpSum([costs[i]*deposit_vars[i] for i in deposit]), "Total Cost of Ingredients per can"

#prob += lpSum([deposit_vars[i] for i in deposit]) == 1.0, "PercentagesSum"
prob += lpSum([Protein[i] *KG[i] * deposit_vars[i] for i in deposit]) >= 17.2*14, "ProteinRequirement"
prob += lpSum([Grass[i] *KG[i] * deposit_vars[i] for i in deposit]) >= 12.8*14, "FatRequirement"
prob += lpSum([KG[i] * deposit_vars[i] for i in deposit]) == 14, "KGRequirement"
prob += lpSum([KG[i] * deposit_vars[i] for i in deposit]) <= 80, "KGRequirement1"

prob.writeLP("WhiskasModel.lp")
prob.solve()
# The status of the solution is printed to the screen
print ("Status:", LpStatus[prob.status])

# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
    print (v.name, "=", v.varValue)

# The optimised objective function value is printed to the screen
print ("Total Cost of Ingredients per can = ", value(prob.objective))

我要添加的新约束在这部分：

prob += lpSum([KG[i] * deposit_vars[i] for i in deposit]) <= 80, "KGRequirement1"

我希望产品 KG[i] * deposit_vars[i] 为 0 或介于 a 和 b[= 之间36=]

Answer 1

'or' 不是您可以直接在 LP / MIP 模型中使用的东西。请记住，LP/MIP 由线性 objective 和线性约束组成。

要建模 x=0 or x≥L，您可以使用所谓的 半连续变量 。大多数高级求解器都支持它们。然而，我不认为 Pulp 支持这一点。作为解决方法，您还可以使用 二进制变量 δ:

δ*L ≤ x ≤ δ*U

其中 U 是 x 的上限。很容易看出这个作品：

δ = 0   ⇒   x = 0
δ = 1   ⇒   L ≤ x ≤ U

半连续变量不需要这些约束。只需告诉求解器变量 x 是半连续的，边界为 [L,U]（如果没有上限，则为 L）。

约束条件

a*x=0   or   L ≤ a*x ≤ U

可以改写为

δ*L ≤ x*a ≤ δ*U
δ binary variable

这是一个相当标准的公式。半连续变量经常用于金融（投资组合模型）以防止小额分配。

所有这些都使模型保持完美线性（不是二次方），因此可以使用标准 MIP 求解器和标准 LP/MIP 建模工具，例如 Pulp。

Answer 2

在传统的线性规划公式中，所有变量、objective 函数和约束都需要是连续的。您要问的是如何使该变量成为离散变量，即它只能接受值 a、b、... 而不是介于两者之间的任何值。当您有连续变量和离散变量的组合时，这称为混合整数问题 (MIP)。 See PuLP documentation that reflects this explanation. 我建议您仔细阅读 "integers;" 中提到的混合问题，它们散布在页面各处。根据 PuLP 的文档，它可以通过调用外部 MIP 求解器来解决 MIP 问题，其中一些已经包含在内。

没有最小工作示例，解释如何实现它有点棘手。一种方法是将变量指定为整数，其值可以作为字典使用。保留默认求解器 COIN-OR's CBC solver 求解器，然后求解 MIP。同时，这里有一些资源可以帮助您继续前进：

https://www.toptal.com/algorithms/mixed-integer-programming#example-problem-scheduling
- 请注意它是如何使用默认求解器 CBC 求解器来解决这个问题的
http://yetanothermathprogrammingconsultant.blogspot.com/2018/08/scheduling-easy-mip.html
- 关于他们如何设置整数变量和调用 CBC 求解器的更明确的示例

将步长添加到线性优化

Add step size to a linear optimization

python

optimization

linear-programming

pulp