Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. MATH-293

Matrix's "OutOfBoundException" in SimplexSolver

    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 on Windows XP 32-Bit

      Description

      Hi all,
      This bug is somehow related to incident MATH-286, but not necessarily...

      Let's say I have an LP and I solve it using SimplexSolver. Then I create a second LP similar to the first one, but with "stronger" constraints. The second LP has the following properties:

      • the only point in the feasible region for the second LP is the solution returned for the first LP
      • the solution returned for the first LP is also the (only possible) solution to the second LP

      This shows the problem:

      LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
      Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
      constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
      constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
      constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
      
      RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
      
      double valA = 0.8 * solution.getPoint()[0] + 0.2 * solution.getPoint()[1];
      double valB = 0.7 * solution.getPoint()[2] + 0.3 * solution.getPoint()[3];
      double valC = 0.4 * solution.getPoint()[4] + 0.6 * solution.getPoint()[5];
      
      f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
      constraints = new ArrayList<LinearConstraint>();
      constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
      constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
      constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
      
      solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
      

      Instead of returning the solution, SimplexSolver throws an Exception:

       Exception in thread "main" org.apache.commons.math.linear.MatrixIndexException: no entry at indices (0, 7) in a 6x7 matrix
      	at org.apache.commons.math.linear.Array2DRowRealMatrix.getEntry(Array2DRowRealMatrix.java:356)
      	at org.apache.commons.math.optimization.linear.SimplexTableau.getEntry(SimplexTableau.java:408)
      	at org.apache.commons.math.optimization.linear.SimplexTableau.getBasicRow(SimplexTableau.java:258)
      	at org.apache.commons.math.optimization.linear.SimplexTableau.getSolution(SimplexTableau.java:336)
      	at org.apache.commons.math.optimization.linear.SimplexSolver.doOptimize(SimplexSolver.java:182)
      	at org.apache.commons.math.optimization.linear.AbstractLinearOptimizer.optimize(AbstractLinearOptimizer.java:106)

      I was too optimistic with the bug MATH-286

        Attachments

        1. SimplexTableau.patch
          4 kB
          Benjamin McCann
        2. SimplexSolverTest.patch
          3 kB
          Benjamin McCann

          Activity

            People

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

              Dates

              • Created:
                Updated:
                Resolved: