c++ - 如何选择整数线性规划求解器？

Question

我是整数线性规划的新手。我计划使用整数线性规划求解器来解决我的组合优化问题。我更熟悉 IDE 上的 C++/面向对象编程。现在我大部分时间都在使用带有 Cygwin 的 NetBeans 来编写我的应用程序。

请问是否有适合我的易于使用的 ILP 求解器？还是取决于我要解决的问题？我正在尝试做一些资源映射优化。如果需要任何进一步的信息，请告诉我。

非常感谢你，卡西。

score 8 · Accepted Answer

我曾多次成功使用 lp_solve ( http://lpsolve.sourceforge.net/5.5/ )。如果你的线性编程技能生疏，它是成熟的、功能丰富的，并且有很多很好的建议。整数线性规划不仅仅是一个附加功能，而且在这个包中得到了强烈的强调。

刚刚注意到你说你是一个“新手”。好吧，那么我强烈推荐这个包，因为文档中充满了示例和温和的教程。我尝试过的其他软件包倾向于假设很多用户。

score 8 · Accepted Answer

如果你想要的是线性混合整数规划，那么我会指向 Coin-OR（特别是模块 CBC）。它是免费软件（作为语音）您可以将它与特定语言一起使用，也可以使用 C++。

如果您的数据需要大量预处理，或者如果您想将双手投入求解器（选择枢轴点、列生成、添加切割等），请使用 C++。

如果您想将求解器用作黑匣子，请使用集成语言（您只对结果感兴趣，并且问题很简单或足够经典，无需调整即可解决）。

但是在标签中，您提到了遗传算法和图形算法。也许你应该从更好地定义你的问题开始......对于我非常喜欢的图表 Boost::Graph

score 4 · Accepted Answer

对于大问题，您可以查看AMPL，它是一个优化解释器，有许多可用的后端求解器。它作为一个单独的进程运行；C++ 将用于写出输入数据。

然后，您可以尝试各种最先进的求解器。

score 2 · Accepted Answer

查看GLPK。附带一些示例，并与 AMPL 的一个子集一起使用，尽管恕我直言，当您坚持使用 C/C++ 进行模型设置时效果最好。也可以处理相当大的模型。

score 1 · Accepted Answer

来自 Wikipedia 的线性规划涵盖了一些不同的算法，您可以深入研究一下，看看哪种算法最适合您。这有帮助还是您想要更具体的东西？

5 回答 5