mathematical-optimization - GLPK( PuLP 包装机)中的约束违规

Question

我正在使用带有 GLPK 求解器的 Pulp 并具有以下约束:

-1000000*f1 + v1 + 1000000*f2 - v2 >= -10.999

求解器:

problem.solve(GLPK(options=['--mipgap', '0.000001', '--cuts']))

但结果我解决了违反约束的问题(状态“最佳”):

f1 = 0
v1 = 11
f2 = 1
v2 = 1000000

那么，在这种情况下我能做什么呢？我可以以某种方式提高准确性或使用其他解决方案吗？

Answer 1

我认为，您遇到了数值准确性问题。您的系数为 1.e7(并且您需要 1.e-6 的解)。该解决方案至少需要在 1.e11 中正确才能保持约束，并且根据参数，您需要最大 1.e-14 相对误差。

对于纯数值求解器来说，这实在是太多了。 (预计最大 1.e-6 到 1.e-7 能够可靠地运行 LP 求解器)有像 QSopt 这样的精确求解器，我也认为，soplex 现在有了这些功能。

这是 QSopt 的链接 http://www.math.uwaterloo.ca/~bico/qsopt/downloads/downloads.htm

这是这个复杂内容的链接。 http://soplex.zib.de/doc/html/EXACT.php

QSopt 仅以二进制形式提供(我认为)，SoPlex 可免费用于研究(据我了解)。

此外，您还可以将 SCIP 与 SoPLex 一起使用。他们已经或曾经有过一些确切的知识产权项目。因此，如果许可证适合您，在这种情况下我会选择 SCIP。

也许，您可以更深入地了解您的应用程序，以便可以重新制定您的限制。