Q

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

2010-05-07 176 views 22 likes

22

我是整数线性规划的新手。我打算使用整数线性规划求解器来解决我的组合优化问题。我更熟悉IDE上的C++ /面向对象编程。现在我正在使用Cygwin的NetBeans在大多数时间编写我的应用程序。如何选择整数线性规划求解器？

我可以问我是否有一个简单的ILP求解器？或者这取决于我想解决的问题？我正在尝试做一些资源映射优化。请让我知道是否需要进一步的信息。

非常感谢Cassie。

2010-05-07 Cassie

A

回答

1

Linear Programming来自维基百科涵盖了几种不同的算法，你可以做一些挖掘，看看哪些可能最适合你。这是否有帮助，或者你想要更具体的东西？

2010-05-07 20:46:47

4

对于大问题，您可能会看到AMPL，这是一个优化解释器，其中有许多可用的backend solvers。它运行为a separate process; C++将用于写出输入数据。

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

2010-05-07 20:58:23 Potatoswatter

8

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

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

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

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

2010-05-07 21:08:30

+0

非常感谢。我的问题基本上是作业映射到任务图上的计算机进行调度。因此，我有一个任务图。每个节点代表需要在机器上运行的作业。作业与机器的不同映射会导致关键路径上的总调度时间不同。我的目标是找到某些作业到机器作业的最小调度时间。所以有谁知道任何简单的解决方案，不需要强大的编程背景给我使用？非常感谢你。Cassie – Cassie 2010-05-10 19:12:30

+2

那么，这种调度本身就是一个完整的研究领域。一些问题可以通过最短路径算法来解决（如果你对同时任务没有限制）。如果你的机器是可预处理的，那么就有简单的多项式算法。否则，你有一个困难的问题很可能是好的。尝试使用CBC作为黑盒（但您需要学习如何在线性模型中对这些问题进行建模），或尝试编写自己的分支代码:) – 2010-05-10 20:03:48

8

我已经在几次成功使用lp_solve（http://lpsolve.sourceforge.net/5.5/）。它是成熟的，功能丰富的，并且如果你的线性编程技巧是生锈的，那么它有很多很好的建议。整数线性规划不仅仅是一个附加，而是强调这个包。

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

2010-10-29 14:51:06 ravenspoint

2

调查GLPK。附带一些例子，并与AMPL的子集一起工作，尽管当您坚持使用C/C++进行模型设置时，恕我直言最适用。也应对相当大的模型。

2011-02-27 08:13:17 Pete

相关问题