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

Question

我正在使用 GNU glpk 求解器解决混合整数规划 (MIP) 问题。该问题包含大约 1,625 列和 507 行，我认为这不是一个大规模问题。但是glpk在解决问题9个多小时后仍未能给出解决方案。

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

Answer 1

首先，偶smaller比你的 MIP 更难求解。 glpk 通常得分为底部混合整数 benchmarks .如果您正在寻找免费的求解器，您可能应该尝试基准测试中提到的其他求解器之一，例如 coin-or 的 cbc。 ，或部分免费 scip .

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

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