Commons Math
  1. Commons Math
  2. MATH-286

SimplexSolver not working as expected?

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 2.0
    • Fix Version/s: 2.1
    • Labels:
      None
    • Environment:

      Java 1.6.0_13 on Windows XP 32-bit

      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[]

      { 1, 0, 1, 0, 1, 0 }

      , Relationship.EQ, 23.0));
      constraints.add(new LinearConstraint(new double[]

      { 0, 1, 0, 1, 0, 1 }

      , Relationship.EQ, 23.0));
      constraints.add(new LinearConstraint(new double[]

      { 1, 0, 0, 0, 0, 0 }

      , Relationship.GEQ, 10.0));
      constraints.add(new LinearConstraint(new double[]

      { 0, 0, 1, 0, 0, 0 }

      , Relationship.GEQ, 8.0));
      constraints.add(new LinearConstraint(new double[]

      { 0, 0, 0, 0, 1, 0 }

      , 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?

      1. SimplexTableau.patch
        4 kB
        Benjamin McCann
      2. SimplexSolverTest.patch
        1 kB
        Benjamin McCann
      3. simplex.txt
        3 kB
        Benjamin McCann
      4. SimplexSolver.patch
        6 kB
        Benjamin McCann
      5. SimplexSolverTest.patch
        5 kB
        Benjamin McCann
      6. SimplexTableau.patch
        4 kB
        Benjamin McCann
      7. patch.zip
        4 kB
        Benjamin McCann
      8. SimplexSolverTest-Andrea.patch
        0.9 kB
        Andrea

        Activity

        Hide
        Benjamin McCann added a comment -

        I have confirmed this is an issue.

        Show
        Benjamin McCann added a comment - I have confirmed this is an issue.
        Hide
        Benjamin McCann added a comment -

        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.8, 0.2, 0.7, 0.3 }

        , 0 );
        Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
        constraints.add(new LinearConstraint(new double[]

        { 1, 0, 1, 0 }

        , Relationship.EQ, 23.0));
        constraints.add(new LinearConstraint(new double[]

        { 0, 1, 0, 1 }

        , Relationship.EQ, 23.0));

        SimplexSolver solver = new SimplexSolver();
        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
        assertEquals(25.3, solution.getValue(), .0000001);
        }

        Show
        Benjamin McCann added a comment - 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.8, 0.2, 0.7, 0.3 } , 0 ); Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>(); constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0 } , Relationship.EQ, 23.0)); constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1 } , Relationship.EQ, 23.0)); SimplexSolver solver = new SimplexSolver(); RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true); assertEquals(25.3, solution.getValue(), .0000001); }
        Hide
        Benjamin McCann added a comment -

        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.2, 0.3 }

        , 0 );
        Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
        constraints.add(new LinearConstraint(new double[]

        { 1, 1 }

        , Relationship.EQ, 23.0));

        SimplexSolver solver = new SimplexSolver();
        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
        assertEquals(6.9, solution.getValue(), .0000001);
        }

        Show
        Benjamin McCann added a comment - 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.2, 0.3 } , 0 ); Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>(); constraints.add(new LinearConstraint(new double[] { 1, 1 } , Relationship.EQ, 23.0)); SimplexSolver solver = new SimplexSolver(); RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true); assertEquals(6.9, solution.getValue(), .0000001); }
        Hide
        Andrea added a comment - - edited

        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.

        Show
        Andrea added a comment - - edited 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.
        Hide
        Benjamin McCann added a comment -

        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.2, 0.3 }

        , 0 );
        Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
        constraints.add(new LinearConstraint(new double[]

        { 1, 1 }

        , Relationship.EQ, 23.0));

        RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
        assertEquals(6.9, solution.getValue(), .0000001);
        }

        Show
        Benjamin McCann added a comment - 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.2, 0.3 } , 0 ); Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>(); constraints.add(new LinearConstraint(new double[] { 1, 1 } , Relationship.EQ, 23.0)); RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true); assertEquals(6.9, solution.getValue(), .0000001); }
        Hide
        Benjamin McCann added a comment -

        The solution is being calculated correctly, but the wrong thing is being returned. The bug is in SimplexTableau.getSolution()

        Show
        Benjamin McCann added a comment - The solution is being calculated correctly, but the wrong thing is being returned. The bug is in SimplexTableau.getSolution()
        Hide
        Benjamin McCann added a comment -

        Here's the fix.
        Note that the test case I posted in the comment was named dyslexically. It should be math286 not math268.

        Show
        Benjamin McCann added a comment - Here's the fix. Note that the test case I posted in the comment was named dyslexically. It should be math286 not math268.
        Hide
        Luc Maisonobe added a comment -

        Fixed in subversion repository as of r806753.
        Patch applied.
        Thanks to Andrea for the report and thanks to Ben for the fix

        Show
        Luc Maisonobe added a comment - Fixed in subversion repository as of r806753. Patch applied. Thanks to Andrea for the report and thanks to Ben for the fix
        Hide
        Andrea added a comment -

        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

        Show
        Andrea added a comment - 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
        Hide
        Benjamin McCann added a comment -

        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.8, 0.7 }

        , 0 );
        Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
        constraints.add(new LinearConstraint(new double[]

        { 1, 1 }

        , Relationship.LEQ, 18.0));
        constraints.add(new LinearConstraint(new double[]

        { 1, 0 }

        , Relationship.GEQ, 10.0));
        constraints.add(new LinearConstraint(new double[]

        { 0, 1 }

        , Relationship.GEQ, 8.0));

        SimplexSolver solver = new SimplexSolver();
        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
        assertEquals(13.6, solution.getValue(), .0000001);
        }

        Show
        Benjamin McCann added a comment - 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.8, 0.7 } , 0 ); Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>(); constraints.add(new LinearConstraint(new double[] { 1, 1 } , Relationship.LEQ, 18.0)); constraints.add(new LinearConstraint(new double[] { 1, 0 } , Relationship.GEQ, 10.0)); constraints.add(new LinearConstraint(new double[] { 0, 1 } , Relationship.GEQ, 8.0)); SimplexSolver solver = new SimplexSolver(); RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true); assertEquals(13.6, solution.getValue(), .0000001); }
        Hide
        Benjamin McCann added a comment -

        Here are the corresponding Simplex tableaus. Let me know if you spot the error.

        Show
        Benjamin McCann added a comment - Here are the corresponding Simplex tableaus. Let me know if you spot the error.
        Hide
        Andrea added a comment - - edited

        Hi all,
        What I wrote before doesn't really make sense...

        Look at this LP simplex solver:

        http://www.phpsimplex.com/simplex/page2.php?objetivo=max&x1=0.8&x2=0.7&restricciones=3&variables=2&l=en&x11=1&x12=1&desigualdad1=-1&y1=18&x21=1&x22=0&desigualdad2=1&y2=10&x31=0&x32=1&desigualdad3=1&y3=8&Submit=Continue

        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...

        Show
        Andrea added a comment - - edited Hi all, What I wrote before doesn't really make sense... Look at this LP simplex solver: http://www.phpsimplex.com/simplex/page2.php?objetivo=max&x1=0.8&x2=0.7&restricciones=3&variables=2&l=en&x11=1&x12=1&desigualdad1=-1&y1=18&x21=1&x22=0&desigualdad2=1&y2=10&x31=0&x32=1&desigualdad3=1&y3=8&Submit=Continue 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...
        Hide
        Benjamin McCann added a comment -

        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."

        Show
        Benjamin McCann added a comment - 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."
        Hide
        Benjamin McCann added a comment -

        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

        Show
        Benjamin McCann added a comment - 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
        Hide
        Benjamin McCann added a comment -

        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 MATH-286, the bug from MATH-288, and the bug from MATH-290. 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.

        Show
        Benjamin McCann added a comment - 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 MATH-286 , the bug from MATH-288 , and the bug from MATH-290 . 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.
        Hide
        Luc Maisonobe added a comment -

        resolved in subversion repository as of r812390
        Benjamin's patches from 2009-09-07 have been committed with very slight changes
        (an == test between Integer instances replaced by a call to equals)
        thanks for the patches

        Show
        Luc Maisonobe added a comment - resolved in subversion repository as of r812390 Benjamin's patches from 2009-09-07 have been committed with very slight changes (an == test between Integer instances replaced by a call to equals) thanks for the patches
        Hide
        Andrea added a comment -

        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.

        Show
        Andrea added a comment - 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.
        Hide
        Benjamin McCann added a comment -

        Wow, sorry, I'll take another look and make sure to test against the original problem this time as well.

        Show
        Benjamin McCann added a comment - Wow, sorry, I'll take another look and make sure to test against the original problem this time as well.
        Hide
        Benjamin McCann added a comment -

        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 (p80-82):
        http://www.amazon.com/Linear-Programming-Introduction-Operations-Engineering/dp/0387948333#reader

        Show
        Benjamin McCann added a comment - 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 (p80-82): http://www.amazon.com/Linear-Programming-Introduction-Operations-Engineering/dp/0387948333#reader
        Hide
        Benjamin McCann added a comment -

        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 non-artificial 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.

        Show
        Benjamin McCann added a comment - 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 non-artificial 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.
        Hide
        Luc Maisonobe added a comment -

        The patch from 2009-09-08 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.

        Show
        Luc Maisonobe added a comment - The patch from 2009-09-08 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.
        Hide
        Andrea added a comment - - edited

        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 MATH-293... Ben, please look at that as well.

        Show
        Andrea added a comment - - edited 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 MATH-293 ... Ben, please look at that as well.
        Hide
        Luc Maisonobe added a comment -

        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.

        Show
        Luc Maisonobe added a comment - 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.
        Hide
        Benjamin McCann added a comment -

        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 MATH-293.

        Show
        Benjamin McCann added a comment - 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 MATH-293 .
        Hide
        Luc Maisonobe added a comment -

        fixed now (we hope)

        Show
        Luc Maisonobe added a comment - fixed now (we hope)

          People

          • Assignee:
            Unassigned
            Reporter:
            Andrea
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development