Six New JSR-331 Implementations with Linear Solvers

As we planned from the very beginning, now we’ve successfully added 6 more JSR-331 implementations using various open source and commercial Linear Programming (LP) tools. 

JSR-331 provides a standard Java API for constraint satisfaction and optimization problems. When an optimization problem uses only linear constraints, it may be successfully resolved with various LP solvers available on the today market. In accordance with the JSR-331 specification, the same linear problem definition should work with any underlying solver without changing a character in the Java code. To switch between different implementations a user only needs to change a jar file in the project’s classpath. For example, to switch between Choco, Cplex, or Gurobi implementations, a user may simply replace “jsr331.choco.jar” to “jsr331.cplex.jar” or “jsr331.gurobi.jar”. The same code for a linear problem should work with a Choco, Constrainer, Cplex, Glpk, or any other underlying solver (of course, performance may be completely different). This is our objective. Now I will describe how I added six LP Solvers to the current JSR-331.

The situation with LP standardization is much better to compare with CP. The LP community uses standardized file formats for linear optimization problem for years. The most popular formats (MPS and LP) are used as an input for all major LP solvers, e.g. MPS has been successfully used since the time of punch cards. All LP solvers support command-line interfaces that allow reading a problem definition from a unified MPS-file and saving the produced solution in another file (using a solver specific format). It gives us a quite generic approach for JSR-331 implementations described on the picture below:

Here we use only one generic (solver-independent) implementation for any linear solver called LinearSolver. It does the following:

  1. creates all variables and linear constraints (and rejects all non-linear constraints)
  2. generates an MPS-file
  3. executes any LP solver as an external process using this MPS-file as an input
  4. reads the produced solution from an output file and use it to create the standard JSR-331 solution

For every particular LP solver we need a small implementation inherited from the generic Java class LinearSolver  and which implements only two solver-specific functions:

  1. return a command line with the name and parameters of a particular LP solver
  2. read a produced file with a solution in a solver specific format into a Java array of values that correspond to the problem constrained variables.

Any LP solver can be downloaded and installed in accordance with its own installation and licensing requirements. You just need to make sure that a solver’s command-line interface works on the same machine (from DOS or Linux prompts).

In accordance with the Specification, any JSR-331 implementation follows a certain naming convention for implementation packages and classes. A generic (solver-independent) JSR-331 linear implementation was created as a separate project “org.jcp.jsr331.linear”. This package implements basic JSR-331 classes such as Problem, Var, Constraint, Solver, and Solution inside a package “javax.constraints.impl”.  We also added several classes like LinearSolver, LinearSolveFactory.and  MpsGenerator to the common Java package “javax.constraints.linear”. These classes cover functionality of the “Solver Independent Implementation” on the picture above.

To create a solver-dependent implementation, for each selected LP solver we did the following:

1)    Installed a solver and made sure that we can execute it from a command line using automatically generated mps-files

2)    Create a Java project “org.jcp.jsr331.<solver>”, for example for the open source LP solver “COIN” we created  a project “org.jcp.jsr331.coin”. Its package “javax.constraints.linear.impl” contains only one class LinearSolver inherited from our generic class javax.constraints.linear.LinearSolver. This class implements two methods:

  • public String getCommanLine()
  • public int[] readResultValues()

It also sets the default optimization direction using JSR-331 constants Objective.MINIMIZE or Objective.MAXIMIZE.

This way we created six JSR-331 implementations for the following LP tools:

Commercial

Open Source

All these LP tools (with an exception of ojAlgo) are written in C/C++: that’s why it is easy to use their executables during invocation from Java.  We used ojAlgo to demonstrate how a pure Java LP solver can be integrated with JSR-331: it is not necessary to produce and parse an external file with solver’s results: being implemented in Java, ojAlgo provides a Java object with a solution that can be directly converted to a JSR-331 solution object. More LP solvers can be added in the same simple manner.

All LP solvers use their default settings. However, a user may always setup different solver-specific option using an environment variable LP_SOLVER_OPTIONS.

We have used free evaluation versions of these tools on a set of small and large tests. Currently, JSR-331 works only with integer variables but we plan to add real variables too – actually LP solver implementations make this task much easier. The initial test show different performance results, in particular as one may expect, linear solvers frequently outperform constraint solvers requiring less memory. We did not do bench-marking (yet), but having a rich choice of solver will certainly empower Java application developers without forcing them to become CP or LP experts.

New 6 implementations are available for free downloads as  a beta version from http://openrules.com/jsr331.  An official Release 1.1.0 will be available soon and will include a detailed User Guide for JSR-331 LP.

This release also includes several additional improvements and a new constraint solver implementation based on JSetL from the University of Parma. You may try to run provided or your own examples. Any questions? Post them at the JSR-331 Discussion Group and contact me directly at jacobfeldman@openrules.com.

Advertisements

About jacobfeldman

CTO at www.openrules.com http://www.linkedin.com/in/jacobfeldmanopenrules
This entry was posted in Uncategorized. Bookmark the permalink.

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