cplex - 当我修改约束 (GLPK) 的 RHS 时会发生什么？

Question

我正在增加GLPK 的 MIP 问题的小于或等于约束的 RHS。但是，有时，在重新优化后，GLPK 在时限内找不到任何可行的解决方案。所以我猜它不会检查以前的解决方案是否可行。有没有人有这方面的经验？或者可以将我指向一个不是源代码本身的文档？

此外，我想知道在为任何其他求解器（例如 Gurobi、Cplex、SCIP、CBC）添加约束后的工作流程是什么，因此任何信息都会有所帮助。

干杯!

Answer 1

更改模型中的某些内容后，通常会丢弃所有解决信息，并从头开始解决问题。即使您放松了问题，但这并不一定意味着 MIP 求解器更容易求解，特别是，它可能总是导致不同的 LP 解决方案，这会导致不同的分支、原始启发式从不同的起点开始，并且是最后倒霉。所以最后，你可能只是不走运，求解器现在需要更长的时间。

在 MIP 求解器中执行“热启动”非常困难。SCIP 提供了这样的功能，请参阅http://scip.zib.de/doc-5.0.1/html/REOPT.php，但这仅在您更改客观系数或收紧约束时才有效（它基于假设所有之前不可行现在仍然不可行，所以你只需要在树的可行部分再次搜索）。

但是，在您的特定情况下，仅存储可行的解决方案并在下一次运行中尝试它们已经有所帮助。这是 SCIP 默认执行的操作。此外，SCIP（以及您提到的所有替代方案）应该比 GLPK 更加稳定和高性能。请参阅http://plato.asu.edu/ftp/milpc.html以获取 MIPLIB 2010 上 MIP 求解器的基准，标准 MIP 基准集：GLPK 能够在 2 小时的时间限制内求解 87 个实例中的 2 个，而 CBC 解决了 53，SCIP 解决了 76，CPLEX 和 Gurobi 都解决了所有 87 个实例。Xpress 和 SAS 在基准测试集上也表现出色。

Answer 2

显然，如果你放宽公式，问题不会变得不可行（如果以前可行的话）。因此，要么您误解了某些内容，要么代码有错误。

我认为您还没有尝试其他求解器。你绝对应该这样做。一般来说，您在问题中提到的所有内容都被认为比 GLPK 更可靠/稳定。