Linear Programming open source tools

I’ve been working with some linear programming (LP) lately, and have looked at a bunch of non-commercial, non-Academic-use tools for LP, and in particular IP (integer programming). Open source solvers I’ve looked at include:

COIN-OR’s CBC
COIN-OR’s CLP
COIN-OR’s SYMPHONY
Gnu GLPK’s glpsol
lp_solve

Some considerations in choosing an open source solver:

1. Higher-level modeling language. If you’re going to do any serious linear programming, you’ll want to use a higher-level mathematical language like AMPL, GAMS, GMPL, or ZIMPL*. The alternative, working at the low-level rows/columns level, is insane for anything other than a small system of equations.

AMPL and GAMS are commercial products, which ruled them out for this project. ZIMPL is open-source, but GMPL is also open source and has two important advantages: 1) it’s directly read by several solvers, and 2) it’s a subset of AMPL so if you ever get to the point that you’re moving up to commercial products you’re ahead of the curve. With ZIMPL, you’d need to run your model through the ZIMPL processor to output MPS (a primitive, row/column format), which is implemented in most every solver, creating a two-step process, and possibly losing some accounting information along the way.

2. Ability to solve solvable problems. I found a couple of comparisons of commercial and non-commercial solvers, where they threw a suite of test problems at each product. The commercial solvers couldn’t solve about 20% of the test suite, but several of the open source solvers couldn’t solve 80%+ of the test suite. The open source CBC was more comparable to the commercial solvers.

3. Speed. Open source solvers lag far, far behind commercial solvers. Of the non-commercial solvers was SCIP far and away the fastest, but SCIP must be licensed if used for non-academic purposes, so that ruled it out for my purposes. Of the remaining open source solvers, CBC stood out for its speed, being twice as fast as glpsol, lp_solve, etc.

4. Standalone? Do you intend to use the solver via an API, or do you want to use it as a standalone solver? Only gnu’s glpsol supports all of the I/O features of GMPL, including the display and printf statements, which means you can make fairly nice reports and can more easily read/write CSV or databases. CBC has some output options. And lp_solve seems to have I/O options with its XLI plugins, but I couldn’t get them to work.

CBC is the fastest and most powerful open source solver that might be used in a non-academic setting, it directly reads GMPL, and its output capabilities are acceptable, so it’s my winner. (It can also be compiled to take advantage of multi-core CPUs, though I’ve not hit it hard enough yet to see how well it scales.)

One trick that’s totally non-obvious is how you get the CBC standalone solver to read a GMPL file. The obscure answer is that in the command line, you add a percent sign to the end of the model file’s name:

cbc mymodel.mod% -threads 4 -printi csv -solve -solu mymodel.csv

which runs it on 4 cores, outputting the results in a CSV-formatter file called my model.csv, using the GMPL model file my model.mod. The trailing percent sign is not part of the file’s name, it’s just a flag. I can see a reason why they might’ve done it this obscure way, but it’s not clearly spelled out in the documentation.

You can also obtain glpsol and SYMPHONY, which both also read GMPL models, so you can triple-check results if you want. Hope this was helpful!

* In a more Seussian mode, this sentence should be, “AMPLE, GAMS, GMPL, and ZIMPL; ROFL, GUZL, TRMPL, and ZOOFL.” Or something like that. The last four “products” don’t exist, as far as I know. Though of course, there are actual (non-linear-programming) products called Hadoop, Mahout, Scalding, Pootle, and Django.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s