Details

Type: Bug

Status: Closed

Priority: Major

Resolution: Fixed

Affects Version/s: 2.0

Fix Version/s: 2.1

Labels:None

Environment:
Java 1.6.0_13 on Windows XP 32bit
Description
I guess (but I could be wrong) that SimplexSolver does not always return the optimal solution, nor satisfies all the constraints...
Consider this LP:
max: 0.8 x0 + 0.2 x1 + 0.7 x2 + 0.3 x3 + 0.6 x4 + 0.4 x5;
r1: x0 + x2 + x4 = 23.0;
r2: x1 + x3 + x5 = 23.0;
r3: x0 >= 10.0;
r4: x2 >= 8.0;
r5: x4 >= 5.0;
LPSolve returns 25.8, with x0 = 10.0, x1 = 0.0, x2 = 8.0, x3 = 0.0, x4 = 5.0, x5 = 23.0;
The same LP expressed in Apache commons math is:
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[]
{ 0.8, 0.2, 0.7, 0.3, 0.6, 0.4 }, 0 );
Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
constraints.add(new LinearConstraint(new double[]
, Relationship.EQ, 23.0));
constraints.add(new LinearConstraint(new double[]
, Relationship.EQ, 23.0));
constraints.add(new LinearConstraint(new double[]
, Relationship.GEQ, 10.0));
constraints.add(new LinearConstraint(new double[]
, Relationship.GEQ, 8.0));
constraints.add(new LinearConstraint(new double[]
, Relationship.GEQ, 5.0));
RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
that returns 22.20, with x0 = 15.0, x1 = 23.0, x2 = 8.0, x3 = 0.0, x4 = 0.0, x5 = 0.0;
Is it possible SimplexSolver is buggy that way? The returned value is 22.20 instead of 25.8, and the last constraint (x4 >= 5.0) is not satisfied...
Am I using the interface wrongly?

 patch.zip
 4 kB
 Benjamin McCann

 simplex.txt
 3 kB
 Benjamin McCann

 SimplexSolver.patch
 6 kB
 Benjamin McCann

 SimplexSolverTest.patch
 5 kB
 Benjamin McCann

 SimplexSolverTest.patch
 1 kB
 Benjamin McCann

 SimplexSolverTestAndrea.patch
 0.9 kB
 Andrea

 SimplexTableau.patch
 4 kB
 Benjamin McCann

 SimplexTableau.patch
 4 kB
 Benjamin McCann
Activity
Here's a smaller version of the problem that also fails:
max 0.8 x0 + 0.2 x1 + 0.7 x2 + 0.3 x3
s.t.
x0 + x2 = 23.0
x1 + x3 = 23.0
@Test
public void testMath268() throws OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[]
, 0 );
Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
constraints.add(new LinearConstraint(new double[]
, Relationship.EQ, 23.0));
constraints.add(new LinearConstraint(new double[]
, Relationship.EQ, 23.0));
SimplexSolver solver = new SimplexSolver();
RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
assertEquals(25.3, solution.getValue(), .0000001);
}
And a yet smaller version that is failing:
max 0.2 x1 + 0.3 x3
s.t.
x1 + x3 = 23.0
@Test
public void testMath268() throws OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[]
, 0 );
Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
constraints.add(new LinearConstraint(new double[]
, Relationship.EQ, 23.0));
SimplexSolver solver = new SimplexSolver();
RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
assertEquals(6.9, solution.getValue(), .0000001);
}
Hi Ben,
Your test here above is wrong, the GoalType should be MAXIMIZE and not MINIMIZE...
The MINIMIZE returns 4.6 which is the expected value.
Whoops, right you are. Thanks for catching that.
This should be a better example for debugging:
max 0.2 x1 + 0.3 x3
s.t.
x1 + x3 = 23.0
@Test
public void testMath268() throws OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[]
, 0 );
Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
constraints.add(new LinearConstraint(new double[]
, Relationship.EQ, 23.0));
RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
assertEquals(6.9, solution.getValue(), .0000001);
}
The solution is being calculated correctly, but the wrong thing is being returned. The bug is in SimplexTableau.getSolution()
Here's the fix.
Note that the test case I posted in the comment was named dyslexically. It should be math286 not math268.
Fixed in subversion repository as of r806753.
Patch applied.
Thanks to Andrea for the report and thanks to Ben for the fix
Hi all,
Maybe I'm doing something wrong extracting the latest version from the SVN repository, but the original issue is still not working on my apache commons math working copy
Here is what I did:
I extracted the latest version from the SVN repository
I executed the original problematic LP for this bug and it still fails. Anyway, the simplified version (but maybe incompatible) succeeds...
Could please anyone look at that?
Thanks
Andrea
Yes, there is still an error with this example. The bug for the smaller example was fixed, but there's something still affecting the larger one. I haven't been able to figure it out yet, but here's another smaller example that is also failing:
@Test
public void testMath286Reopened() throws OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[]
, 0 );
Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
constraints.add(new LinearConstraint(new double[]
, Relationship.LEQ, 18.0));
constraints.add(new LinearConstraint(new double[]
, Relationship.GEQ, 10.0));
constraints.add(new LinearConstraint(new double[]
, Relationship.GEQ, 8.0));
SimplexSolver solver = new SimplexSolver();
RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
assertEquals(13.6, solution.getValue(), .0000001);
}
Here are the corresponding Simplex tableaus. Let me know if you spot the error.
Hi all,
What I wrote before doesn't really make sense...
Look at this LP simplex solver:
why after the first phase is over the coefficients for x1 and x2 are set to 0.8 and 0.7 while here they are 0? Couldn't be the SimplexTableau's discardArtificialVariables doesn't do everything correct?
Just guessing...
If I remember correctly phpsimplex formed the tableau a bit differently. Instead of creating the tableau from the beginning with two objective functions, they only use one at the beginning, and then insert the phase 2 objective function later. As a result, the tableaus aren't directly comparable.
I emailed Professor Chinneck at Carleton University for some help because I retaught myself a lot of this using a draft of a book he's working on. He suggested looking into ways to deal with degenerate solutions, so I'll see if I can read up on that a bit:
"You've hit a degeneracy (which means that there are multiple solutions with the same value of objective function). The problem came when, in your second tableau, you pivoted on the third row (corresponding to s1) instead of the last row (corresponding to a2). Understandable since the minimum ratio test came out tied."
phpsimplex said that when there's a tie, they make the artificial variable leave the basis, which we're not doing and would solve the problem in this case:
http://www.phpsimplex.com/en/simplex_method_theory.htm#anomalous
i'll try putting together a patch, likely this weekend, to do that
Happy Labor Day! To celebrate, here's a new set of patches that adds the ability to deal with degeneracy in the SimplexTableau.
The test includes four tests: the two bugs in MATH286, the bug from MATH288, and the bug from MATH290. I think they should all go in to prevent a regression in the future. They all run very quickly and there are a lot of edge cases in the Simplex algorithm, so I'd prefer to be safe.
resolved in subversion repository as of r812390
Benjamin's patches from 20090907 have been committed with very slight changes
(an == test between Integer instances replaced by a call to equals)
thanks for the patches
Hi all,
I'm still not convinced the original problem is correct... Could you please try?
I would add the original LP with 6 variables and 5 restrictions to the test cases, since I'm not completely sure the "smaller examples" address exactly the same problem I posted weeks ago.
Wow, sorry, I'll take another look and make sure to test against the original problem this time as well.
The problem still exists when we are dropping columns moving between phase 1 and phase 2. I was pointed towards this book for possible solutions (p8082):
http://www.amazon.com/LinearProgrammingIntroductionOperationsEngineering/dp/0387948333#reader
Here's a patch that correctly solves the problem Andrea posted (sorry for not completely fixing the problem with my earlier patches.) It's mostly refactoring to make the solution easier, which was to drop positive cost nonartificial variables and nonbasic artificial variables at the end of phase 1 instead of all artificial variables.
There are some practical problems with degeneracy and redundant constraints that were not obvious to me from the theory when I first started working on this. We should really test this a bit more with constraints outnumbering variables and redundant constraints to really be comfortable that all the issues are addressed, but we're certainly pretty close now if not there yet.
Andrea, thanks for the reports and validating fixes (or lack there of). Luc, thanks for quickly getting these into SVN and letting me know about the problems.
The patch from 20090908 has been applied in subversion repository as of r812831.
After the patch, an existing test (SimplexTableauTest.testdiscardArtificialVariables) failed, so I had to update the expected matrix to prevent this failure. This should be validated as I really don't know if the failure were expected after the change or if something wrong occurred. Ben, could you have a look at this ?
This time, I'm not marking the issue as resolved, Andrea I'll wait until you consider it solved by yourself.
Thanks to everybody for their time on this issue, I'm sure we are gradually improving things.
Hi Luc, hi Ben,
This time I can confirm Ben's patch fixes the original problem.
If I find something else related to this bug (or not) I will let you know, but I'm pretty sure this time the SimplexSolver is much more robust it was a couple of weeks ago!
I "improved" the JUnit test case for this bug, I attach the patch to this message. There are 5 new assertions that check all the constraints are really satisfied.
Thanks again for all the commitment
Andrea
PS: I don't know if this is somehow related, but I found another bug MATH293... Ben, please look at that as well.
I applied Andrea's patch in subversion as of r812921, thanks for providing it.
I'll wait for Ben's acknowledgement about the changes I've made in SimplexTableauTest.testdiscardArtificialVariables before marking the issue as resolved.
Thanks Luc. You can close this issue. A note, we might want to rename testdiscardArtificialVariables to testDropPhase1Objective to match the updated method name. I overlooked this earlier. I look at MATH293.
fixed now (we hope)
I have confirmed this is an issue.