Using CLP with Java

The COIN-OR project provides a home to a number of open source software projects useful in operations research, primarily optimization programs and libraries. Possibly the most "senior" of these projects is CLP, a single-threaded linear program solver. Quoting the project description:

CLP is a high quality open-source LP solver. Its main strengths are its Dual and Primal Simplex algorithms. It also has a barrier algorithm for Linear and Quadratic objectives. There are limited facilities for Nonlinear and Quadratic objectives using the Simplex algorithm. It is available as a library and as a standalone solver. It was written by John Forrest, jjforre at us.ibm.com.

Like most of the projects at COIN-OR, CLP is coded in C++, which can make it a bit of a pain to use from Java. So I was quite interested when Nils Löhndorf wrote to me that he had written a Java interface to CLP, clp-java, which he has released as open source. I have an academic license for CPLEX, so I'm not really motivated to switch to CLP, but in the past I've found myself working on open source projects in which I would like to have embedded an LP solver. Since the intent is that people be able to use the program at no cost, embedding a somewhat expensive commercial solver is clearly a non-starter.

So I downloaded clp-java and took it for a test drive. I coded a basic assignment model in Java, with randomly generated assignment costs and a user-selectable dimension. (By "dimension" I mean number of slots and number of assignees.) Each run solves a single assignment problem twice, once with CLP and once with CPLEX. Since CLP is limited to a single thread, I throttled CPLEX to a single thread as well.

My primary objective was not to see which was faster. Hans Mittelmann at Arizona State University maintains solver benchmarks in his Decision Tree for Optimization Software. You can see there that CLP sometimes beats CPLEX (rather handily) but frequently is slower. (The same can be said for CLP in comparison to Gurobi.) What I wanted to know was the following:

• is clp-java easy to use (yes!) and well-documented (pretty well);
• does it produce correct answers (yes, at least on my tests -- CLP and CPLEX obtained identical solutions on all tests);
• is there any performance penalty for using the clp-java interface (not that I can see).

I started with a dimension of 5 and doubled it with each new run, up to 1280 for the final run. Here's a log-log plot of total end-to-end solution times:

CPLEX beat CLP consistently, but as problem dimension grew the ratio of times seemed fairly steady, and the difference (a bit over 25 seconds on my quad-core PC) doesn't strike me as horrible. IMPORTANT DISCLAIMER: We're looking at one replication at each problem size of one particular LP (assignment problem). Ascribe any significance to anything I say at your own peril. Also, I repeated a few replications, and the times varied significantly, even though the seed for the random number generator was held constant (meaning the repeated problems should have been identical to the original versions). So the teeny sample size is exacerbated by fairly high variance.

I broke the timing down into three parts: setting up the model; solving the model; and recovering the solution (getting the solver to cough up the values of the assignment variables). Here are log-log plots for each.

Setup

CPLEX seemed to be a bit faster creating a model object than CLP was, but the difference was pretty minimal (2.3 seconds with 1,280 assignees).

Solution

The bulk of the time for either program is spent solving the problem, so this plot resembles the plot of overall execution times.

Recovery

For the small models, both program returned the variables values so quickly that the recorded time (in milliseconds) was zero. Interestingly (at least to me), on the larger instances CLP returned solution values faster than did CPLEX.

Again, the takeaway from the experiments is not which solver is better; it's that Nils's interface works correctly and does not seem to introduce any glaring inefficiencies. Overall, I am quite impressed with Nils's creation. He provides an all-in-one jar file that contains not only his code but also CLP and some third-party libraries. You only have to import clp-java into your project and put the jar in the class path. When you run your program, the necessary libraries are unpacked into a temporary directory. Before the program exits, it cleans up after itself, deleting the temporary directory. (I confirmed that it left no digital artifacts behind.)

There is one bug yet to be worked out (as of this writing). At least on Ubuntu 14.04 and Linux Mint 17.2 (based on Ubuntu 14.04), "out of the box" you get linking errors at run time. Apparently, despite the fact that the COIN libraries CLP uses are sitting in the same temporary directory that CLP is sitting in, it looks for them elsewhere and can't find them. The workaround is to install the coinor-clp package (and a couple of dependencies) from the Canonical repositories, using apt or Synaptic. That fixed the linking problem for me and one other user. I have no idea if the same problem crops up in other operating systems.

So if you are programming in Java and looking for an open-source LP solver that you can build into a project, check out clp-java and CLP.