.NET/C#线性编程库

Question

.NET/C#线性编程库

c#.netmonomathematical-optimizationlinear-programming

11

我需要解决一个欠定的线性方程和约束系统，并找到最小化成本函数的特定解。这需要在纯便携式托管代码中完成，可在.NET和Mono中运行。有哪些免费可用的库可以用来实现这一点？

我发现的所有免费库提供的优化算法仅支持单个变量的区间约束，例如0 < x < 1，而不是像x + 2y < 4这样的约束。我还发现，线性方程求解器通常仅支持具有单个解的线性系统。

到目前为止我发现最接近的是DotNumerics，它包括奇异值分解（Singular Value Decomposition），用于解决欠定线性系统，但其优化算法仅支持单变量约束（据我所知）。

还有几个问题询问线性规划，但我的主要要求是多变量约束和解决欠定系统。我尚未找到支持多变量约束的免费库。

- Dylan

你尝试过Alglib吗？ - Marc Gravell

@MarcGravell 经过仔细检查，看起来这符合我的要求。非常感谢你。把它放在答案里，我会接受的。我不知道为什么之前没有注意到它。 - Dylan

4个回答

7

ALGLIB是通常用于线性求解器等的库。在绝望之前，我建议你好好研究一下它。

- Marc Gravell

3

对于那些寻找的人，Google已经发布了他们的or-tools https://developers.google.com/optimization/。我能够快速地在.NET中将其连接起来，并且它支持OP所需要的功能。 - randomsolutions

4

线性规划正是用于您提出的问题的。多变量约束在线性规划中非常普遍。例如，可以查找免费的求解器，如lpsolve (http://sourceforge.net/projects/lpsolve/), glpk (http://www.gnu.org/software/glpk/) 或 CBC (https://projects.coin-or.org/Cbc)。

我知道上述建议不是使用C#和托管的.NET程序集。如果这对您很重要，那么您可以尝试从这些库的源代码构建自己的版本。不过可能需要相当多的工作-我没有尝试过。

此外，从您最初的问题中不清楚您要解决的问题有多大或复杂。如果您的变量必须取离散值，则需要一个能够执行分支和界限或类似操作的求解器库；否则，如果它纯粹是线性和连续的，则可以使用单纯形算法。如果您找不到预构建的版本，则可以在许多教科书中找到相关内容。

如果问题非常小（几十个变量和约束）或者只是线性和连续的，那么您可能可以使用自己的全新（便携式，纯托管代码）实现来解决问题，但如果您有数千个约束和变量，则可能无法获得所需的性能。如果您有一个大而复杂的问题，那么您可能需要商业求解器才能获得所需的答案。

- TimChippingtonDerrick

1

GLPK的.NET封装器：https://www.nuget.org/packages/Optimization.Solver.GLPK - Mauricio Scheffer

2

没有人提到Solver Foundation。这是一个不错的选择。

- Naresh

1

一个好的例子，解释了一些问题。Express（免费）许可证允许执行具有多达1000个决策变量的问题。给定的链接已经失效，但如果您感兴趣，可以在此处找到它：http://msdn.microsoft.com/en-us/library/ff524509(v=vs.93).aspx - krzychu

1

对于指数问题来说，这非常有限，我甚至不认为它是完全自由的。例如，像TSP这样的问题仅限于45个点。 - Max Izrin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anders Gustafsson · Accepted Answer

如果您正在开发.NET（即非Windows Store、Windows Phone或Silverlight），那么我强烈建议您查看lpsolve，它适用于大型LP和/或MILP问题。下载包含相应的lpsolve DLL的x86或x64开发档案，然后下载包含C#文件的.NET API档案，其中包含对lpsolve API中所有相关函数的P/Invoke调用。

另一个选择是使用COIN-OR项目中的CLP求解器，通过CoinMP预编译二进制文件。这里提供了一个C#包装器DLL here。

如果您需要纯管理代码，则ALGLIB可能是您最好的选择（如Marc Gravell所建议的），但请注意，ALGLIB开源许可证使用GPL。如果您想在自己的代码中使用ALGLIB而不向开源社区披露它，您需要购买商业ALGLIB许可证。

一次快速的互联网搜索也可以找到一个纯C#实现的Simplex LP算法here。我无法确定作者，也不知道这个实现是否正确或者质量如何。不过代码似乎高度可移植，即使在Windows Store、Windows Phone、Silverlight和Mono环境中也是如此。