opensource.google.com

Menu

Introducing Apache Commons Math SimplexSolver

Wednesday, July 1, 2009

SimplexSolver is an easy-to-use, object-oriented method of solving linear programming problems. We're happy to announce today that we've Open Sourced the code that runs the newly released Google Spreadsheets Solve Feature and made it a part of Apache Commons Math 2.0.

While numerous other libraries are available that run linear optimization problems, SimplexSolver is the first written in Java with a commercially-friendly license.

Let's say we have the following LP:

MIN -2x + y - 5
S.T.
x + 2y <= 6
3x + 2y <= 12
y >= 0

We could solve the problem in Java using the SimplexSolver:

// describe the optimization problem
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { -2, 1 }, -5);
Collection constraints = new ArrayList();
constraints.add(new LinearConstraint(new double[] { 1, 2 }, Relationship.LEQ, 6));
constraints.add(new LinearConstraint(new double[] { 3, 2 }, Relationship.LEQ, 12));
constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.GEQ, 0));

// create and run the solver
RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MINIMIZE, false);

// get the solution
double x = solution.getPoint()[0];
double y = solution.getPoint()[1];
double min = solution.getValue();

Looking at the LP problem and Java code side-by-side, we can see how easy it is to describe the problem in the Apache Commons Math API. More examples can be viewed in the SimplexSolverTest source code. Apache Commons Math 2.0 is not quite released yet, so for the time being if you want to use the SimplexSolver, you'll need to compile it from source.

So that's SimplexSolver: a clean, fast method of solving LP problems. We hope you like it as much as we do! Thanks to Luc Maisonobe and the rest of the Apache Team who helped integrate the SimplexSolver into the Apache codebase.

.