ILP Part 28 — Using ILP in .NET

~ afish

This is the twenty eighth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hi! Today we are going to use ILP in .NET. We will check few C# libraries for defining and solving linear constraints. Let’s begin.

Microsoft Solver Foundation

Microsoft Solver Foundation is a set of development tools for mathematical simulation, optimization, and modeling that relies on a managed execution environment and the common language runtime (CLR). You can use any CLR language, you can also use multiple solvers (like Gurobi or CPLEX) because MSF supports plug-in mechanism. It is also possible to use MSF in Excel.

MSF supports not only linear programs but also a great variety of other optimization languages. You can build model using code or load it from file.

In order to build model from code you can use two different approaches: first one is based on matrix creation like in this example, second one is based on Solver Foundation Services.

It is very easy to build a model and solve it, you can also add different solvers without recompiling the application (you need to edit xml configuration file). This makes MSF very efficient and easy to use. Unfortunately, there are few drawbacks:

  • MSF is not developed anymore. There will be no more version
  • Built-int solver is slow and does not always handle integer constraints (yes, you can get non-integer results)
  • It is not free for non-academic use

lp_solve

Mixed Integer Linear Programming solver lp_solve solves pure linear, (mixed) integer/binary, semi-cont and special ordered sets (SOS) models. lp_solve is written in ANSI C and can be compiled on many different platforms like Linux and Windows.

It is free, you can compile it on your own or just download binary, you can also use it in many languages. In order to use it in .NET you can plug it to MSF. You can also use it without MSF, just download MSF plugin code and extract LpSolveNativeInterface (or take it directly from here).

Well, this one also have drawbacks:

  • It is much slower than Gurobi or CPLEX
  • It has problems with floating point numbers so you can get weird solutions very fast
  • It uses more memory than other solvers (Gurobi or CPLEX)

Still this is a good choice if you just want to make a proof of concept.

OR-Tools

Google OR-Tools is free suite for solving combinatorial and optimization problems. It is free, open source, still alive, portable (can be used on Windows and Linux), and can support many solvers. This is very good choice for writing proof of concepts and more sophisticated applications.

OR-Tools supports 32 and 64-bit applications so you can use it basically everywhere. It also has binding for C#, for more information check the samples or this blog post.

I was using this library and it worked quite well. It was not as good as CPLEX binding in terms of memory consumption and obtained results, however, it is free.

CPLEX

IBM CPLEX is the ILP solver for enterprise usage. It is able to handle very complicated models and solve them very fast. It also has binding for C#.

This is one of the fastest solver for ILP problems. Unfortunately, it is not free for non-academic use.

Gurobi

Gurobi is another one solver for enterprise usage. It is the fastest solver I have ever used, it can handle problems with hundreds of thousand variables and constraints. It can be run in cluster mode and handles multiple cores easily. Unfortunately, it is not free. Also the licensing mechanism is very cumbersome because licenses are tied to the machine so it is not easy to move application to other machine without breaking the license.

Gurobi has .NET interface so you can easily embed solver in C# applications.

NEOS Solvers

If you don’t want to invest in computer power and configure solvers manually you can use NEOS solvers. It is a cloud for solving optimization problems with common solvers (e.g., Gurobi) and you can use it for free. In order to solve a problem you need to upload it in some common format (like MPS) and grab a solution after a few minutes. It doesn’t have a binding for C# but you can use submission tool or XML-RPC.

This is really great tool for solving even large problems for free. It has limit for 8 hours of solving time and about 5MB size of a problem, but it is not a problem in most situations. You can notification about solved problem on e-mail.

MilpManager

All these bindings are very good for building models, however, they usually do not support more sophisticated constructs which we developed throughout this series. In order to use them easily, you can download Nuget package called MilpManager. It is a library for Mixed Integer Linear Programming containing abstraction for pluggable solvers and implementation of common mathematical functions. It is developed on a GitHub as well as are bindings for solvers: MSF, lp_solve, OR-Tools,, Gurobi, and CPLEX. You can also extend it by binding custom solver.

Summary

There are multiple tools for building ILP models in .NET. This means that it is very easy to solve optimization problems in memory which is sometimes much easier than implementing custom algorithms. What’s more, ILP approach is very well known and the solvers are greatly optimized so they can handle models with thousands of variables.