python - PuLP - 如何指定求解器的精度

Question

我会尽量让我的问题简短。如果您需要任何进一步的信息，请告诉我。

我有一个 MIP，使用 PuLP 包在 Python 中实现。 (大约 100 个变量和约束)问题的数学公式来自一篇研究论文。本文还包括一项数值研究。但是，我的结果与作者的结果不同。

我的问题变量叫做prob

prob = LpProblem("Replenishment_Policy", LpMinimize)

我用 prob.solve() 解决了这个问题LpStatus 返回 Optimal

当我添加一些最优(论文)结果作为约束条件时，我得到了稍微更好的目标值。将目标函数限制为稍低的值也是如此。 LpStatus 保持Optimal。

original objective value: total = 1704.20
decision variable: stock[1] = 370

adding constraints: prob += stock[1] == 379
new objective value: 1704.09

adding constraints: prob += prob.objective <= 1704
new objective value: 1702.81

我的假设是 PuLP 的求解器近似解。计算速度很快，但显然不是很准确。 有什么方法可以提高 PuLP 使用的求解器的准确性吗？我正在寻找类似的东西:prob.solve(accuracy=100%)。我有一个看看 documentation但不知道该怎么做。有什么想法可能是什么问题吗？

感谢任何帮助。谢谢。

Answer 1

我的问题的答案 ayhan 给出了:要指定求解器的精度，您可以使用所选求解器的 fracGap 参数。

prob.solve(solvers.PULP_CBC_CMD(fracGap=0.01))

但是，我问的问题与我遇到的问题不一致。结果的偏差确实不是求解器准确性的问题(正如 sascha 在评论中指出的那样)。

我的问题的原因:我实现的算法是在非平稳、随机需求下优化 (Rn, Sn) 策略的顺序策略参数。上面提到的论文是:Tarim, S.A., & Kingsman, B.G. (2006)。具有非平稳随机需求的库存系统的建模和计算(R n，S n)策略。欧洲运筹学杂志，174(1)，581-599。

该算法有两个二进制变量delta[t] 和P[t][j]。以下两个约束只允许 P[t][j] 的值为 0 和 1，只要 delta[t] 定义为二进制即可。

for t in range(1, T+1):
    prob += sum([P[t][j] for j in range(1, t+1)]) == 1

    for j in range(1, t+1):
        prob += P[t][j] >= delta[t-j+1] - sum([delta[k] for k in range(t-j+2, t+1)])

由于 P[t][j] 只能取 0 或 1 的值，因此是一个二进制变量，我声明如下:

for t in range(1, T+1):
    for j in range(1, T+1):
        P[t][j] = LpVariable(name="P_"+str(t)+"_"+str(j), lowBound=0, upBound=1, cat="Integer")

最小化返回的目标值:1704.20

在研究了一段时间的解决方案后，我注意到论文的一部分是这样说的:

... it follows that P_tj must still take a binary value even if it is declared as a continuous variable. Therefore, the total number of binary variables reduces to the total number of periods, N.

因此我将 P[t][j] 变量的 cat 参数更改为 cat="Continuous"。在不更改任何其他内容的情况下，我得到了 1702.81 的较低目标值。结果的状态在两种情况下均显示:Optimal

我仍然不确定所有这些方面是如何相互关联的，但我想这周对我来说很有效。对于针对此问题的其他所有人，可能会通过本文顶部给出的答案找到必要的帮助。