Introducing Apache Commons Math SimplexSolver
Posted:
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:
We could solve the problem in Java using the SimplexSolver:
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.
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
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();
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { -2, 1 }, -5);
Collection
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.
how about Discrete Optimization (aka Integer Programming), is this kind of computaion planned? with integers it is quite simple to express some problems like "binary knapsack problem" or scheduling.
ReplyDeleteGDocs Widgets that could do such things would really shadow MS Excel.
I double the previous request! Implementation of Gomory's algorithm or branch-and-cut algorithm to get integer results would be extremely welcome.
ReplyDeleteWe have discussed adding support for MILP or nonlinear optimizations and are interested in doing so, but I can't make any promises on when it would happen. If anyone out there wants to extend the Commons Math API I'd be happy to help make sure it gets reviewed and tested :o)
ReplyDeleteFYI, if you're interested in using the SimplexSolver you should compile from the Subversion repository since there are a number of fixes and improvements that have gone in for the unreleased version 2.1
ReplyDeleteMany thanks for open sourcing this Ben, that's terrific. I just got the snapshot code and it built first time on my Mac. Always a nice way to start :)
ReplyDeleteAnyway to get this outside of commons? I was hoping to get a minimal implementation so it could be rewritten using code that does not require JDK 5. I have an excellent use for this, but it would have to run without generics or autoboxing in a JDK 1.4.2 environment.
ReplyDeletetcole6, you would have to check out the source code from the commons subversion repository and create your own copy of the code without java 5 features. alternatively, you could upgrade to a newer version of the jvm, which is what i'd recommend if at all possible
ReplyDeleteHow would I handle a constraint that is < or > and not <= or >=?
ReplyDeletetcole6,
ReplyDelete< and > don't make much sense when dealing with doubles. the difference in the answer between <= and < will be infinitely small. for example let's say you're maximizing x such that it's less than 3. then you'll come up with 2.99999999999999999999999999999999999999999 which is really no different than the 3 you would have come up with using <=
In that sample code in the original post, when I change
ReplyDeleteconstraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.GEQ, 0));
to
constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.GEQ, -1));
(i.e. I changed the 0 to a -1) then I get a NullPointerException. I'm using Commons Math 2.0, is this bug fixed in the 2.1 version in the SVN repository?
To follow up on my previous post, with the SVN head version the error that I mentioned (y >= -1) went away. Thanks for the SimplexSolver, it's great!
ReplyDeleteConcerning the API, I like the following approach better:
ReplyDeletehttp://javailp.sourceforge.net/
The problem mentioned in your post would look like this in Java ILP API:
// obj function: MIN -2x + y - 5
Linear linear = new Linear();
linear.add(-2, "x");
linear.add(1, "y");
problem.setObjective(linear, OptType.MIN);
// constraint: x + 2y <= 6
linear = new Linear();
linear.add(1, "x");
linear.add(2, "y");
problem.add(linear, Operator.LE, 6);
// constraint: 3x + 2y <= 12
linear = new Linear();
linear.add(3, "x");
linear.add(2, "y");
problem.add(linear, Operator.LE, 12);
// variable bound: y >= 0
problem.setVarLowerBound("y", 0);
// solve
solver = factory.get();
result = solver.solve(problem);
System.out.println(result);
In my previous comment, I hadn't mentioned that Java ILP is not a solver itself but a universal wrapper to several LP java interfaces (lp_solve, GLPK, CPLEX, ...). Still, I find Java ILP very useful since one can freely switch the underlying solver without having to redefine the LP problem.
ReplyDeleteAdditionally having a pure java solver implementation in Java ILP would surely increase the value of this project.
Hi! I have a question!
ReplyDeleteIf I solver the problem:
f(X) = 2x+3y-z-0.5t-->MIN;
x-y+z+0.5t=9;
y-4z+8t<=4;
-2y+2z-3t<=10;
x,y,x,t>=0;
I got the only one solution (0,0,8,2).
However the problem have multiplicity (infinite) solution!!!
Please give me ideal to solver it. Thanks.
Can the Simplex Solver be used to provide all the possible solutions?
ReplyDeleteI have the following Linear problem. and I want to evaluate each possible solution
to this problem
Minimize N = a+b+c+d+e subject to
5a + 4b + 1c + 2d + 3e >= 25
a <= 1
b <= 5
c <= 15
d <= 5
e <= 5
Le Van and suvidha: you cannot use linear programming to find all the optimal solutions: it is sometimes possible to write code that, on receiving a solution, resubmits the problem with a new constraint that eliminates the current solution to find out whether there is another, equally good solution. In suvidha's problem:
ReplyDelete/* Objective function */
min: a + b + c + d + e;
/* Variable bounds */
c1: a <= 1;
c2: b <= 5;
c3: c <= 15;
c4: d <= 5;
c5: e <= 5;
5 a + 4 b + 1 c + 2 d + 3 e >= 25;
The solution is 6 (a=1, b=5, other values zero). If you had guessed that most values would be zero, then constrain the non zero values thus:
test: a + b <= 5;
This yields an answer that is higher than 6 - so the previous solution is the only optimal one.
btw - after all these years, the world is still awaiting a free Java integer programming solver that is free of native code...
how could I express a relationship " >" ? the only one close to this is GEQ, which has an extra equal sign.
ReplyDeleteIn a linear program, you can't directly express a ">" relationship. You have got to use a constant, say "k" and express your constraint a1x2 + a2x2 + ... + anxn > z as a1x2 + a2x2 + ... + anxn >= z+k. As far as I know, there is no other mathematically possible way due to convergence issues.
DeleteIs it possible to use SimplexSolver also for getting the solutions on the right side of the constraints in the optimum Tableau? For my purpose i would need those "Shadow-values", but it seems to me that i can only get the optimum values of the target function? Can somebody help me, it would be very kind.
ReplyDelete