为什么GLPSOL（GLPK）需要很长时间才能解决大型MIP？

Question

我有一个很大的MIP问题，我在GLPK中使用GLPSOL来解决它。然而，解决LP弛豫问题需要很多迭代，并且每次迭代obj和infeas值都是相同的。我认为它已经找到了最佳的解决方案，但它不会停止并持续运行数小时。这会发生在每个大型MIP/LP问题上吗？我该如何处理这种情况？任何人都可以给我任何建议吗？谢谢！

Answer 1

解决MIPs的问题一般是NP完全的，这意味着有些实例不能有效解决。但是我们的问题经常有足够的结构，所以启发式可以帮助解决这些模型。这在过去十年​​的解决能力中获得了巨大的收益。

为了解基本方法和理解你的情况究竟是什么问题（上限没有进展，下限没有进展......），请阅读Practical Guidelines for Solving Difficult Mixed Integer Linear Programs。请注意，像Gurobi/Cplex这样的商业解决方案与一般的非商业解决方案（尤其是MIP解决方案）之间存在巨大差距。有大量的基准here。

还有很多参数要调整。古罗比例如有不同的参数模板：一个目标是可行解决方案的快速发现;一个目标是证明界限。

我的个人意见：与cbc（开源）相比& scip（开源但非商业用途免费），glpk是相当糟糕的。