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

Bugs in Simplex Implementation

    XMLWordPrintableJSON

Details

    • Bug
    • Status: Closed
    • Major
    • Resolution: Fixed
    • 2.0
    • 2.1
    • None

    Description

      Simplex routine may return infeasible solution:

      Bug1.java
      import java.util.ArrayList;
      import org.apache.commons.math.linear.ArrayRealVector;
      import org.apache.commons.math.optimization.GoalType;
      import org.apache.commons.math.optimization.OptimizationException;
      import org.apache.commons.math.optimization.linear.*;
      
      public class Bug1 {
          
          public static void main(String[] args) throws OptimizationException {
              
              LinearObjectiveFunction c = new LinearObjectiveFunction(new double[7], 0.0d);
              
              ArrayList<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(5);
              LinearConstraint cnst;
              cnst = new LinearConstraint(new double[] {1.00d, 1.00d, 0.00d, 0.00d, 0.0d, 0.00d, 0.00d}, Relationship.EQ, 1.0d);
              cnsts.add(cnst);
              cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 1.00d, 1.00d, 1.0d, 0.00d, 0.00d}, Relationship.EQ, 1.0d);
              cnsts.add(cnst);
              cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 0.00d, 0.00d, 0.0d, 1.00d, 1.00d}, Relationship.EQ, 1.0d);
              cnsts.add(cnst);
              cnst = new LinearConstraint(new double[] {0.54d, 0.00d, 0.34d, 0.00d, 0.0d, 0.12d, 0.00d}, Relationship.EQ, 0.54d);
              cnsts.add(cnst);
              cnst = new LinearConstraint(new double[] {0.00d, 0.54d, 0.00d, 0.34d, 0.0d, 0.00d, 0.12d}, Relationship.EQ, 0.34d);
              cnsts.add(cnst);
              System.out.println("Constraints:");
              for(LinearConstraint con : cnsts) {
                  System.out.println(con.getCoefficients().toString() + " " + con.getRelationship() + " " + con.getValue());
              }
              
              SimplexSolver simplex = new SimplexSolver();
              double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE, true).getPointRef();
              System.out.println("Solution:\n" + new ArrayRealVector(sol));
              System.out.println("Third constraint is violated!");
          }
      }
      

      or may find no solution where some exist:

      Bug1.java
      import java.util.ArrayList;
      import org.apache.commons.math.linear.ArrayRealVector;
      import org.apache.commons.math.optimization.GoalType;
      import org.apache.commons.math.optimization.OptimizationException;
      import org.apache.commons.math.optimization.linear.*;
      
      public class Bug2 {
          
          public static void main(String[] args) throws OptimizationException {
              
              LinearObjectiveFunction c = new LinearObjectiveFunction(new double[13], 0.0d);
              
              ArrayList<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(5);
              LinearConstraint cnst;
              cnst = new LinearConstraint(new double[] {1.00d, 1.00d, 1.0d, 0.00d, 0.00d, 0.00d, 0.0d, 0.0d, 0.0d, 0.0d, 0.00d, 0.00d, 0.0d}, Relationship.EQ, 1.0d);
              cnsts.add(cnst);
              cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 0.0d, 1.00d, 1.00d, 1.00d, 1.0d, 0.0d, 0.0d, 0.0d, 0.00d, 0.00d, 0.0d}, Relationship.EQ, 1.0d);
              cnsts.add(cnst);
              cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 0.0d, 0.00d, 0.00d, 0.00d, 0.0d, 1.0d, 1.0d, 1.0d, 0.00d, 0.00d, 0.0d}, Relationship.EQ, 1.0d);
              cnsts.add(cnst);
              cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 0.0d, 0.00d, 0.00d, 0.00d, 0.0d, 0.0d, 0.0d, 0.0d, 1.00d, 1.00d, 1.0d}, Relationship.EQ, 1.0d);
              cnsts.add(cnst);
              cnst = new LinearConstraint(new double[] {0.54d, 0.00d, 0.0d, 0.32d, 0.00d, 0.00d, 0.0d, 0.1d, 0.0d, 0.0d, 0.02d, 0.00d, 0.0d}, Relationship.EQ, 0.54d);
              cnsts.add(cnst);
              cnst = new LinearConstraint(new double[] {0.00d, 0.54d, 0.0d, 0.00d, 0.32d, 0.00d, 0.0d, 0.0d, 0.1d, 0.0d, 0.00d, 0.02d, 0.0d}, Relationship.EQ, 0.32d);
              cnsts.add(cnst);
              cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 0.0d, 0.00d, 0.00d, 0.32d, 0.0d, 0.0d, 0.0d, 0.0d, 0.00d, 0.00d, 0.0d}, Relationship.EQ, 0.1d);
              cnsts.add(cnst);
              System.out.println("Constraints:");
              for(LinearConstraint con : cnsts) {
                  System.out.println(con.getCoefficients().toString() + " " + con.getRelationship() + " " + con.getValue());
              }
              
              System.out.println("verifying a known solution:");
              ArrayRealVector sol = new ArrayRealVector(new double[] {4.0d/9.0d, 5.0d/9.0d, 0.0d, 11.0d/16.0d, 0.0d, 5.0d/16.0d, 0.0d, 4.0d/5.0d, 0.0d, 1.0d/5.0d, 0.0d, 1.0d, 0.0d});
              System.out.println("sol = " + sol);
              for(LinearConstraint con : cnsts) {
                  System.out.println(sol.dotProduct(con.getCoefficients()) + " = " + con.getValue());
              }
              
              SimplexSolver simplex = new SimplexSolver();
              double[] newsol = simplex.optimize(c, cnsts, GoalType.MINIMIZE, true).getPointRef();
              System.out.println("Solution:\n" + new ArrayRealVector(newsol));
          }
      }
      

      Attachments

        Activity

          People

            Unassigned Unassigned
            cwinter Christian Winter
            Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: