You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2009/04/08 23:41:48 UTC
svn commit: r763412 - in /commons/proper/math/trunk/src:
java/org/apache/commons/math/optimization/linear/
test/org/apache/commons/math/optimization/linear/
Author: luc
Date: Wed Apr 8 21:41:47 2009
New Revision: 763412
URL: http://svn.apache.org/viewvc?rev=763412&view=rev
Log:
added a threshold for comparisons in Simplex solver
Jira: MATH-246
Modified:
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java?rev=763412&r1=763411&r2=763412&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java Wed Apr 8 21:41:47 2009
@@ -33,7 +33,7 @@
private static final long serialVersionUID = -4886937648715323786L;
/** Default amount of error to accept in floating point comparisons. */
- private static final double DEFAULT_EPSILON = 1.0e-10;
+ private static final double DEFAULT_EPSILON = 1.0e-6;
/** Amount of error to accept in floating point comparisons. */
protected final double epsilon;
@@ -62,7 +62,7 @@
double minValue = 0;
Integer minPos = null;
for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++) {
- if (tableau.getEntry(0, i) < minValue) {
+ if (MathUtils.compareTo(tableau.getEntry(0, i), minValue, epsilon) < 0) {
minValue = tableau.getEntry(0, i);
minPos = i;
}
@@ -81,7 +81,7 @@
Integer minRatioPos = null;
for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getHeight(); i++) {
double rhs = tableau.getEntry(i, tableau.getWidth() - 1);
- if (tableau.getEntry(i, col) >= 0) {
+ if (MathUtils.compareTo(tableau.getEntry(i, col), 0, epsilon) >= 0) {
double ratio = rhs / tableau.getEntry(i, col);
if (ratio < minRatio) {
minRatio = ratio;
@@ -133,7 +133,7 @@
return true;
}
for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++) {
- if (tableau.getEntry(0, i) < 0) {
+ if (MathUtils.compareTo(tableau.getEntry(0, i), 0, epsilon) < 0) {
return false;
}
}
@@ -150,7 +150,7 @@
return false;
}
for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++) {
- if (tableau.getEntry(0, i) < 0) {
+ if (MathUtils.compareTo(tableau.getEntry(0, i), 0, epsilon) < 0) {
return false;
}
}
@@ -186,7 +186,7 @@
public RealPointValuePair doOptimize()
throws OptimizationException {
final SimplexTableau tableau =
- new SimplexTableau(f, constraints, goalType, restrictToNonNegative);
+ new SimplexTableau(f, constraints, goalType, restrictToNonNegative, epsilon);
solvePhase1(tableau);
tableau.discardArtificialVariables();
while (!isOptimal(tableau)) {
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java?rev=763412&r1=763411&r2=763412&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java Wed Apr 8 21:41:47 2009
@@ -27,6 +27,7 @@
import org.apache.commons.math.linear.RealVector;
import org.apache.commons.math.optimization.GoalType;
import org.apache.commons.math.optimization.RealPointValuePair;
+import org.apache.commons.math.util.MathUtils;
/**
* A tableau for use in the Simplex method.
@@ -79,6 +80,9 @@
/** Number of artificial variables. */
protected int numArtificialVariables;
+ /** Amount of error to accept in floating point comparisons. */
+ protected final double epsilon;
+
/**
* Build a tableau for a linear problem.
* @param f linear objective function
@@ -86,13 +90,16 @@
* @param goalType type of optimization goal: either {@link GoalType#MAXIMIZE}
* or {@link GoalType#MINIMIZE}
* @param restrictToNonNegative whether to restrict the variables to non-negative values
+ * @param epsilon amount of error to accept in floating point comparisons
*/
SimplexTableau(final LinearObjectiveFunction f,
final Collection<LinearConstraint> constraints,
- final GoalType goalType, final boolean restrictToNonNegative) {
+ final GoalType goalType, final boolean restrictToNonNegative,
+ final double epsilon) {
this.f = f;
this.constraints = constraints;
this.restrictToNonNegative = restrictToNonNegative;
+ this.epsilon = epsilon;
this.numDecisionVariables = getNumVariables() + (restrictToNonNegative ? 0 : 1);
this.numSlackVariables = getConstraintTypeCounts(Relationship.LEQ) +
getConstraintTypeCounts(Relationship.GEQ);
@@ -259,7 +266,7 @@
private Integer getBasicRow(final int col) {
Integer row = null;
for (int i = getNumObjectiveFunctions(); i < getHeight(); i++) {
- if (getEntry(i, col) != 0.0) {
+ if (!MathUtils.equals(getEntry(i, col), 0.0, epsilon)) {
if (row == null) {
row = i;
} else {
Modified: commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java?rev=763412&r1=763411&r2=763412&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java (original)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java Wed Apr 8 21:41:47 2009
@@ -31,7 +31,6 @@
public class SimplexSolverTest extends TestCase {
public void testSimplexSolver() throws OptimizationException {
-
LinearObjectiveFunction f =
new LinearObjectiveFunction(new double[] { 15, 10 }, 7);
Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
@@ -143,6 +142,22 @@
assertEquals(1438556.7491409, solution.getValue(), .0000001);
}
+ public void testEpsilon() throws OptimizationException {
+ LinearObjectiveFunction f =
+ new LinearObjectiveFunction(new double[] { 10, 5, 1 }, 0);
+ Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
+ constraints.add(new LinearConstraint(new double[] { 9, 8, 0 }, Relationship.EQ, 17));
+ constraints.add(new LinearConstraint(new double[] { 0, 7, 8 }, Relationship.LEQ, 7));
+ constraints.add(new LinearConstraint(new double[] { 10, 0, 2 }, Relationship.LEQ, 10));
+
+ SimplexSolver solver = new SimplexSolver();
+ RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
+ assertEquals(1.0, solution.getPoint()[0]);
+ assertEquals(1.0, solution.getPoint()[1]);
+ assertEquals(0.0, solution.getPoint()[2]);
+ assertEquals(15.0, solution.getValue());
+ }
+
public void testTrivialModel() throws OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 1, 1 }, 0);
Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
Modified: commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java?rev=763412&r1=763411&r2=763412&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java (original)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java Wed Apr 8 21:41:47 2009
@@ -30,7 +30,7 @@
LinearObjectiveFunction f = createFunction();
Collection<LinearConstraint> constraints = createConstraints();
SimplexTableau tableau =
- new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false);
+ new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false, 1.0e-6);
double[][] expectedInitialTableau = {
{-1, 0, -1, -1, 2, 0, 0, 0, -4},
{ 0, 1, -15, -10, 25, 0, 0, 0, 0},
@@ -45,7 +45,7 @@
LinearObjectiveFunction f = createFunction();
Collection<LinearConstraint> constraints = createConstraints();
SimplexTableau tableau =
- new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false);
+ new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false, 1.0e-6);
double[][] expectedTableau = {
{ 1, -15, -10, 25, 0, 0, 0},
{ 0, 1, 0, -1, 1, 0, 2},
@@ -63,7 +63,7 @@
constraints.add(new LinearConstraint(new double[] {0, 1}, Relationship.LEQ, 3));
constraints.add(new LinearConstraint(new double[] {1, 1}, Relationship.LEQ, 4));
SimplexTableau tableau =
- new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false);
+ new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false, 1.0e-6);
double[][] initialTableau = {
{1, -15, -10, 25, 0, 0, 0, 0},
{0, 1, 0, -1, 1, 0, 0, 2},