[MATH-302] Bugs in Simplex Implementation

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 2.0
• Fix Version/s: 2.1
• Assignee: Unassigned
• Reporter: Christian Winter
• Created: 14/Oct/09 13:58
• Updated: 14/Apr/10 00:09
• Resolved: 15/Oct/09 08:56

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));
    }
}