Tur*_*ion 9 linear-programming
我有一个整数线性优化问题,我对可行的,好的解决方案感兴趣.据我所知,例如Gnu线性编程工具包只返回最优解(假设存在).这需要无休止的时间,并不是我正在寻找的东西:我会对任何好的解决方案感到满意,而不仅仅是最优的解决方案.
因此,一个LP解算器,例如在一段时间后停止并返回他到目前为止找到的最佳解决方案,将完成这项工作.
有没有这样的软件？如果该软件是开源的,或者至少像啤酒一样免费,那将是很棒的.
或者:有没有其他方法通常可以加速整数LP问题？这是正确的地方吗？
许多求解器提供时间限制参数; 如果设置了时间限制参数,它们将在达到时间限制后停止.如果找到了整数可行解,那么它将返回找到的最佳可行解.
您可能知道,整数编程是NP难的,并且有一个真正的艺术,即快速找到最佳解决方案以及良好可行的解决方案.要比较不同的求解器,请参阅Hans Mittelmann教授的优化软件基准.MILP基准 - 尤其是MIPLIB2010和可行性基准应该是最相关的.
除了选择一个好的求解器之外,还有许多事情可以用来改善求解时间,包括调整求解器的参数和模型重构.研究和工业领域的许多人 - 包括我自己 - 都在我们的职业生涯中致力于改善MIP模型的解决时间,包括一般模型和特定模型.
如果您是学术用户,请注意CPLEX和Gurobi等顶级商业系统可免费用于学术用途.有关详细信息,请参阅相应网站
最后,您可能需要查看OR-Exchange,它是Stack Overflow的姊妹站点,专注于运营研究领域.
(免责声明:我目前在Gurobi Optimization工作,之前曾在提供CPLEX的ILOG工作).
如果你想快速得到可行的整数解并且不需要最优解，你可以尝试
增加相对或绝对差距。通常求解器的相对间隙较小，例如 0.0001%。这意味着求解器将继续搜索 MIP 解，直到 MIP 解与最优解的距离不超过 0.0001%。将这个 gab 增加到例如 1%，这样你就得到了好的解决方案，但求解器不会花费很长时间来证明最优性。
尝试有关MIP 启发式的求解器参数的不同值。
CPLEX和GUROBI有参数可以控制，MIP强调。这意味着求解器将更加注重寻找可行的解决方案或证明最优性。重点关注可行的 MIP 解决方案。
大多数求解器（例如 CPLEX、Gurobi、MOPS 或 GLPK）都具有间隙和启发式设置。据我所知，MIP 重点只能在 CPLEX 和 Gurobi 中设置。