如何选择整数线性编程求解器？

Question

我是整数线性编程的新手.我计划使用整数线性编程求解器来解决我的组合优化问题.我更熟悉IDE上的C++ /面向对象编程.现在我使用NetBeans和Cygwin一起编写我的应用程序.

我可以问一下,对我来说是否有一个简单易用的ILP求解器？或者这取决于我想解决的问题？我正在尝试做一些资源映射优化.如果需要任何进一步的信息,请告诉我.

非常感谢,Cassie.

Answer 1

如果你想要的是线性混合整数编程,那么我会指向Coin-OR(特别是模块CBC).它是免费软件(作为语音)您可以使用特定语言,也可以使用C++.

如果数据需要大量预处理,或者想要将手放入求解器(选择轴点,列生成,添加切割等等),请使用C++.

如果您想将求解器用作黑盒子,请使用集成语言(您只对结果感兴趣并且问题很简单或经典,无需调整即可解决).

但是在标签中你提到了遗传算法和图形算法.也许你应该从更好地解决你的问题开始...对于图形我喜欢很多Boost :: Graph

那么,这种调度本身就是一个完整的研究领域.一些问题可以通过最短路径算法解决(如果您对同时任务没有约束).如果你的机器是可以预先设置的,那么就有简单的多项式算法.否则,你有一个很难的问题.尝试使用CBC作为黑盒子(但你需要学习如何在线性模型中建模这些问题),或尝试编写自己的分支代码:) (2认同)

Answer 2

我曾多次使用lp_solve(http://lpsolve.sourceforge.net/5.5/)取得成功.它是成熟的,功能丰富,如果您的线性编程技能生疏,则会提供很多好的建议.整数线性编程不只是一个附加功能,但强调此包.

刚注意到你说你是个"新手".那么,我强烈推荐这个包,因为文档中充满了示例和温和的教程.我尝试过的其他软件包往往会占用很多用户.

Answer 3

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

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

Answer 4

维基百科的线性编程涵盖了几种不同的算法，您可以深入研究这些算法，看看哪种算法最适合您。这有帮助吗？还是您想要更具体的东西？