Author: tn
Date: Sun Jan 20 10:04:45 2013
New Revision: 1435810
URL: http://svn.apache.org/viewvc?rev=1435810&view=rev
Log:
[MATH-930] Add new constructors to override the hard-coded cut-off value,
further improve javadoc and update failing unit test.
Modified:
commons/proper/math/trunk/src/changes/changes.xml
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java
Modified: commons/proper/math/trunk/src/changes/changes.xml
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1435810&r1=1435809&r2=1435810&view=diff
==============================================================================
--- commons/proper/math/trunk/src/changes/changes.xml (original)
+++ commons/proper/math/trunk/src/changes/changes.xml Sun Jan 20 10:04:45 2013
@@ -56,9 +56,9 @@ This is a minor release: It combines bug
way such as to allow drop-in replacement of the v3.1[.1] JAR file.
">
<action dev="tn" type="fix" issue="MATH-930">
- Improved class javadoc wrt convergence criteria and added an
- additional constructor to override the default epsilon value in class
- "SimplexSolver".
+ Improved class javadoc wrt convergence criteria and added
+ additional constructors to override the default epsilon and cut-off
+ values in class "SimplexSolver".
</action>
<action dev="erans" type="fix" issue="MATH-929" due-to="Piotr Wydrych">
Fixed truncated value in "MultivariateNormalDistribution".
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java?rev=1435810&r1=1435809&r2=1435810&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
Sun Jan 20 10:04:45 2013
@@ -34,8 +34,15 @@ import org.apache.commons.math3.util.Pre
* <ul>
* <li>Algorithm convergence: 1e-6</li>
* <li>Floating-point comparisons: 10 ulp</li>
+ * <li>Cut-Off value: 1e-12</li>
* </ul>
* <p>
+ * The cut-off value has been introduced to zero out very small numbers in the
Simplex tableau,
+ * as these may lead to numerical instabilities due to the nature of the
Simplex algorithm
+ * (the pivot element is used as a denominator). If the problem definition is
very tight, the
+ * default cut-off value may be too small, thus it is advised to increase it
to a larger value,
+ * in accordance with the chosen epsilon.
+ * <p>
* It may also be counter-productive to provide a too large value for {@link
MaxIter}
* as parameter in the call of {@link
#optimize(org.apache.commons.math3.optim.OptimizationData...)},
* as the {@link SimplexSolver} will use different strategies depending on the
current iteration
@@ -46,12 +53,15 @@ import org.apache.commons.math3.util.Pre
* @since 2.0
*/
public class SimplexSolver extends LinearOptimizer {
+ /** Default amount of error to accept in floating point comparisons (as
ulps). */
+ static final int DEFAULT_ULPS = 10;
+
+ /** Default cut-off value. */
+ static final double DEFAULT_CUT_OFF = 1e-12;
+
/** Default amount of error to accept for algorithm convergence. */
private static final double DEFAULT_EPSILON = 1.0e-6;
- /** Default amount of error to accept in floating point comparisons (as
ulps). */
- private static final int DEFAULT_ULPS = 10;
-
/** Amount of error to accept for algorithm convergence. */
private final double epsilon;
@@ -59,10 +69,16 @@ public class SimplexSolver extends Linea
private final int maxUlps;
/**
+ * Cut-off value for entries in the tableau: values smaller than the
cut-off
+ * are treated as zero to improve numerical stability.
+ */
+ private final double cutOff;
+
+ /**
* Builds a simplex solver with default settings.
*/
public SimplexSolver() {
- this(DEFAULT_EPSILON, DEFAULT_ULPS);
+ this(DEFAULT_EPSILON, DEFAULT_ULPS, DEFAULT_CUT_OFF);
}
/**
@@ -71,7 +87,17 @@ public class SimplexSolver extends Linea
* @param epsilon Amount of error to accept for algorithm convergence.
*/
public SimplexSolver(final double epsilon) {
- this(epsilon, DEFAULT_ULPS);
+ this(epsilon, DEFAULT_ULPS, DEFAULT_CUT_OFF);
+ }
+
+ /**
+ * Builds a simplex solver with a specified accepted amount of error.
+ *
+ * @param epsilon Amount of error to accept for algorithm convergence.
+ * @param maxUlps Amount of error to accept in floating point comparisons.
+ */
+ public SimplexSolver(final double epsilon, final int maxUlps) {
+ this(epsilon, maxUlps, DEFAULT_CUT_OFF);
}
/**
@@ -79,11 +105,12 @@ public class SimplexSolver extends Linea
*
* @param epsilon Amount of error to accept for algorithm convergence.
* @param maxUlps Amount of error to accept in floating point comparisons.
+ * @param cutOff Values smaller than the cutOff are treated as zero.
*/
- public SimplexSolver(final double epsilon,
- final int maxUlps) {
+ public SimplexSolver(final double epsilon, final int maxUlps, final double
cutOff) {
this.epsilon = epsilon;
this.maxUlps = maxUlps;
+ this.cutOff = cutOff;
}
/**
@@ -258,7 +285,8 @@ public class SimplexSolver extends Linea
getGoalType(),
isRestrictedToNonNegative(),
epsilon,
- maxUlps);
+ maxUlps,
+ cutOff);
solvePhase1(tableau);
tableau.dropPhase1Objective();
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java?rev=1435810&r1=1435809&r2=1435810&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java
Sun Jan 20 10:04:45 2013
@@ -66,12 +66,6 @@ class SimplexTableau implements Serializ
/** Column label for negative vars. */
private static final String NEGATIVE_VAR_COLUMN_LABEL = "x-";
- /** Default amount of error to accept in floating point comparisons (as
ulps). */
- private static final int DEFAULT_ULPS = 10;
-
- /** The cut-off threshold to zero-out entries. */
- private static final double CUTOFF_THRESHOLD = 1e-12;
-
/** Serializable version identifier. */
private static final long serialVersionUID = -1369660067587938365L;
@@ -105,6 +99,9 @@ class SimplexTableau implements Serializ
/** Amount of error to accept in floating point comparisons. */
private final int maxUlps;
+ /** Cut-off value for entries in the tableau. */
+ private final double cutOff;
+
/**
* Builds a tableau for a linear problem.
*
@@ -120,7 +117,8 @@ class SimplexTableau implements Serializ
final GoalType goalType,
final boolean restrictToNonNegative,
final double epsilon) {
- this(f, constraints, goalType, restrictToNonNegative, epsilon,
DEFAULT_ULPS);
+ this(f, constraints, goalType, restrictToNonNegative, epsilon,
+ SimplexSolver.DEFAULT_ULPS, SimplexSolver.DEFAULT_CUT_OFF);
}
/**
@@ -138,11 +136,32 @@ class SimplexTableau implements Serializ
final boolean restrictToNonNegative,
final double epsilon,
final int maxUlps) {
+ this(f, constraints, goalType, restrictToNonNegative, epsilon,
maxUlps, SimplexSolver.DEFAULT_CUT_OFF);
+ }
+
+ /**
+ * Build a tableau for a linear problem.
+ * @param f linear objective function
+ * @param constraints linear constraints
+ * @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 when checking for optimality
+ * @param maxUlps amount of error to accept in floating point comparisons
+ * @param cutOff the cut-off value for tableau entries
+ */
+ SimplexTableau(final LinearObjectiveFunction f,
+ final Collection<LinearConstraint> constraints,
+ final GoalType goalType,
+ final boolean restrictToNonNegative,
+ final double epsilon,
+ final int maxUlps,
+ final double cutOff) {
this.f = f;
this.constraints = normalizeConstraints(constraints);
this.restrictToNonNegative = restrictToNonNegative;
this.epsilon = epsilon;
this.maxUlps = maxUlps;
+ this.cutOff = cutOff;
this.numDecisionVariables = f.getCoefficients().getDimension() +
(restrictToNonNegative ? 0 : 1);
this.numSlackVariables =
getConstraintTypeCounts(Relationship.LEQ) +
@@ -462,8 +481,8 @@ class SimplexTableau implements Serializ
final double multiple) {
for (int i = 0; i < getWidth(); i++) {
double result = tableau.getEntry(minuendRow, i) -
tableau.getEntry(subtrahendRow, i) * multiple;
- // cut-off values smaller than the CUTOFF_THRESHOLD, otherwise may
lead to numerical instabilities
- if (FastMath.abs(result) < CUTOFF_THRESHOLD) {
+ // cut-off values smaller than the cut-off threshold, otherwise
may lead to numerical instabilities
+ if (FastMath.abs(result) < cutOff) {
result = 0.0;
}
tableau.setEntry(minuendRow, i, result);
Modified:
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java?rev=1435810&r1=1435809&r2=1435810&view=diff
==============================================================================
---
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java
(original)
+++
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java
Sun Jan 20 10:04:45 2013
@@ -420,11 +420,11 @@ public class SimplexSolverTest {
double[] objFunctionCoeff = new double[33];
objFunctionCoeff[3] = 1;
LinearObjectiveFunction f = new
LinearObjectiveFunction(objFunctionCoeff, 0);
- SimplexSolver solver = new SimplexSolver(1e-4, 10);
+ SimplexSolver solver = new SimplexSolver(1e-4, 10, 1e-6);
PointValuePair solution = solver.optimize(new MaxIter(1000), f, new
LinearConstraintSet(constraints),
GoalType.MINIMIZE, new
NonNegativeConstraint(true));
- Assert.assertEquals(0.3752298, solution.getValue(), 1e-6);
+ Assert.assertEquals(0.3752298, solution.getValue(), 1e-4);
}
@Test