Linear programming library for .NET / C# [closed]

问题:

I need to solve an under-determined linear system of equations and constraints, then find the particular solution that minimises a cost function. This needs to be done in purely portable managed code that will run in .NET and Mono. What freely available libraries are there that I can use to implement this?

All of the optimisation algorithms provided by free libraries I have found only support interval constraints on single variables, e.g. 0 < x < 1, not constraints like x + 2y < 4. I have also found that often the linear equations solvers only support linear systems with one solution.

The closest I have found so far is DotNumerics, which includes Singular Value Decomposition for solving under-determined linear systems, but its optimisation algorithms only support single-variable constraints (as far as I can tell).

There are several other questions asking about linear programming, but my key requirements are multi-variable constraints and solving under-determined systems. I have yet to find a free library that supports multi-variable constraints.

回答1:

ALGLIB is the usual go-to library for things like linear solvers. I would give that a good look before despairing.

回答2:

If you are developing for .NET (i.e. not Windows Store, Windows Phone or Silverlight), then I would definitely recommend that you take a look at lpsolve, that is suitable for large LP and/or MILP problems. Download the x86 or x64 development archives that contain the respective lpsolve DLL:s, and then download the .NET API archive that contains a C# file with P/Invoke calls to all relevant functions in the lpsolve API.

Another alternative is to use the CLP solver from the COIN-OR projects, via the CoinMP precompiled binaries. There is a C# wrapper DLL available here.

If you do require purely managed code, ALGLIB is probably your best bet (as suggested by Marc Gravell above), but be aware that the ALGLIB open-source license uses GPL. If you want to use ALGLIB in your own code without disclosing it to the open-source community, you would need to purchase a commercial ALGLIB license.

A quick Internet search also reveals a pure C# implementation of the Simplex LP algorithm here. I cannot identify the author, and I have no idea whether this implementation is correct or of any quality. The code does seem highly portable though, even in terms of Windows Store, Windows Phone, Silverlight and Mono contexts.

回答3:

Linear programming is intended for doing exactly what you are asking. Multi-variable constraints are absolutely normal in linear programming. Look for free solvers like lpsolve (http://sourceforge.net/projects/lpsolve/), glpk (http://www.gnu.org/software/glpk/) or CBC (https://projects.coin-or.org/Cbc) for example.

I accept that the above suggestions are not in C# and not managed .net assemblies out-of-the-box. If that is a deal breaker for you, then maybe you can try building a version yourself from the source code of one of these libraries. Might require quite a bit of work though - I haven't tried it.

It is also unclear from your original question how big or complex a problem you are trying to solve. If you have variables that must take discrete values, then you would need a solver library that will do branch and bound or similar, otherwise if its purely linear and continuous then you can just use a simplex algorithm. Its in lots of textbooks if you can't find a pre-built version.

If its a really tiny problem (tens of variables and constraints) or just linear and continuous then you may be able to get away with your own fresh (portable, pure managed code) implementation, but if you have thousands of constraints and variables, you may struggle to get the performance you need. If you have a big and complex problem you may be out of luck as you may need a commercial solver to get the answers you need.

回答4:

no one mentioned solver foundation. It is a good option.