optimization - 如何加速 GLPK 求解 MIP 模型

Question

我正在使用 GNU glpk 求解器解决混合整数规划(MIP) 问题。该问题包含大约 1,625 列和 507 行，我认为这不是一个大规模的问题。但是，glpk 在解决问题超过 9 小时后无法提供解决方案。

我想知道是否有人遇到过类似的问题或有任何建议来加快计算速度。否则，您是否有任何其他 MIP 求解器建议我可以尝试对源代码进行少量更改？

Answer 1

首先，即使比您的 MIP 更小的MIP 也很难解决。glpk 通常会在混合整数基准测试中得分。如果您正在寻找免费的求解器，您可能应该尝试基准中提到的其他求解器之一，例如 coin-or 的cbc或部分免费的scip。

如果您是一名学者，或者问题对您来说很重要，您可以尝试其中一个商业求解器。 Gurobi对学者免费。它、cplex (IBM) 和xpress (FICO) 是主要的商业求解器。

求解 MIP 的求解时间是配方质量的重要函数。您没有关于您的模型的任何细节，但根据您要解决的模型类型，可能有很多关于您的问题的良好 MIP 公式的出版物。

Answer 2

我不保证有解决方案，但可能是数值不稳定问题。

正如您所描述的，我已经看到一个 MIP 模型无限期地运行，但查看日志它在最佳值的 1e-7 范围内。就我而言，更改数据会导致问题立即运行（<2 秒）。有些数据集会很快终止，有些则永远不会结束。我相信这是 glpk（和 python）的一个已知问题。

或者，尝试一次删除约束 1。如果它加快了速度，您就知道在哪里进行重新制定。