Review of WVLPSolver: A Java-based Linear Programming Library

Pure Java based optimization tools released under benign licenses are popular in decision-analytics embedded industrial applications. They reduce maintenance efforts and deployment costs, keeping IT managers, analytical support engineers, and developers happy. No platform-specific issues to deal with. No license and patent infringement headaches.... It's a win-win for everybody, provided these 'free' analytical tools withstand the rigors of a production environment.

Recap: This tab summarized a set of pure Java tools a while ago here, talked about a DIY Java solver here that gets you to within a factor of 10-20 of CPLEX on combinatorial LPs, and chatted about "GooPLEX v1.0" some years ago here.

The new WVLPSolver library is introduced here (courtesy:  Bharath Krishnan, data scientist at CQuotient). This new solver is worth a look because its v1.0 appears to be more well thought out compared to the initial version of 'Gooplex'. In particular, WVLPSolver seems to employ a revised simplex scheme that would allow it to work with a minimal simplex tableau (see an old but remarkable (if extreme) illustration of this advantage). Per the introductory post, it employs the reliable Colt library, and is released under the Apache license. These three factors alone may allow this tool to become a useful workhorse in specific situations ("think small"). Great work by the developers, and hope they continue to improve upon this initial release.

Big Data produces a variety of decision problems (recent post related to this topic). In some situations, and depending on the problem structure, you may end up needing to solve tons of small but independent optimization problems, and in other cases, relatively fewer giant monoliths where a considerable amount of sophistication is required to produce consistently good answers. In the former case, an IT manager has to decide whether he needs to budget for a million-instance licensed version of an industrial-strength solver that works cross-platform, or hack-a-heuristic that generates "user-optimal solutions" but may end up confusing users, or go with a nice, pure Java LP brew. Each option has its advantages and disadvantages depending on the context. For analytics start-ups that offer solutions having a relatively small OR footprint, the last option may sound appealing.

GooPLEX: Go Google! Wake up COIN-OR!

The first release of Google's open-source simplex solver (which this tab dubs 'GooPLEX') appears to be a simple toy version of the simplex method for Linear Programs. GooPLEX appears to be missing all the basic ingredients of a practically viable solver such as the revised simplex method, dual simplex, sparse LU factorization, etc. The good news is that we finally have an open-source solver whose license (Apache) is actually useful in the real world.

COIN-OR has a dedicated team, and a fantastic repository of solvers and other OR stuff. Unfortunately, its licensing (CPL and now EPL) is still uncomfortably and frustratingly restrictive for companies to use commercially, and thereby also improve by contributing to it. Consequently, it is likely that COIN-OR is going to be popular mainly within the OR-academic bubble. Ironically, most OR/IE departments will already have GUROBI or CPLEX licenses and thus wont be dependent on such *PL license based LP/MIP solvers. We OR folks need to stop shooting ourselves in the foot.

The smartest course of action for IBM and the COIN-OR team is to do what Google did and make the COIN-OR available under Apache/BSD. On the other hand, one hopes Google's developers and the OR community will improve upon GooPLEX and make it a scalable product. Go Google, and welcome to the world of O.R!

Google releases open-source Simplex Solver

good news for O.R practitioners. I wish COIN-OR would make their license as friendly as google's simplex solver. We'll have to look into the code to see if it's an efficient and effective implementation (e.g., dual simplex with LU factorization) for large LPs.


Here's the license details cut-and-pasted from the source.

1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */