Author: tn
Date: Fri Dec 20 19:33:03 2013
New Revision: 1552792
URL: http://svn.apache.org/r1552792
Log:
[MATH-1082] Improve cutOff mechanism in SimplexSolver, adapt unit tests.
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java
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=1552792&r1=1552791&r2=1552792&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
Fri Dec 20 19:33:03 2013
@@ -36,7 +36,7 @@ import org.apache.commons.math3.util.Pre
* <li>type of optimization: {@link
org.apache.commons.math3.optim.nonlinear.scalar.GoalType GoalType}
* - optional, default: {@link
org.apache.commons.math3.optim.nonlinear.scalar.GoalType#MINIMIZE MINIMIZE}</li>
* <li>whether to allow negative values as solution: {@link
NonNegativeConstraint} - optional, default: true</li>
- * <li>pivot selection rule: {@link PivotSelectionRule} - optional, default
{@link PivotSelectionRule#Dantzig}</li>
+ * <li>pivot selection rule: {@link PivotSelectionRule} - optional, default
{@link PivotSelectionRule#DANTZIG}</li>
* <li>callback for the best solution: {@link SolutionCallback} -
optional</li>
* <li>maximum number of iterations: {@link MaxIter} - optional, default:
{@link Integer#MAX_VALUE}</li>
* </ul>
@@ -51,13 +51,14 @@ import org.apache.commons.math3.util.Pre
* <li>Algorithm convergence: 1e-6</li>
* <li>Floating-point comparisons: 10 ulp</li>
* <li>Cut-Off value: 1e-10</li>
- * </ul>
+ * </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 for certain problems, thus it is
advised to increase it
- * to a larger value, in accordance with the chosen epsilon.
+ * The cut-off value has been introduced to handle the case of very small
pivot elements
+ * in the Simplex tableau, as these may lead to numerical instabilities and
degeneracy.
+ * Potential pivot elements smaller than this value will be treated as if they
were zero
+ * and are thus not considered by the pivot selection mechanism. The default
value is safe
+ * for many problems, but may need to be adjusted in case of very small
coefficients
+ * used in either the {@link LinearConstraint} or {@link
LinearObjectiveFunction}.
*
* @version $Id$
* @since 2.0
@@ -228,7 +229,8 @@ public class SimplexSolver extends Linea
for (int i = tableau.getNumObjectiveFunctions(); i <
tableau.getHeight(); i++) {
final double entry = tableau.getEntry(i, col);
- if (Precision.compareTo(entry, 0d, maxUlps) > 0) {
+ // do the same check as in getPivotRow
+ if (Precision.compareTo(entry, 0d, cutOff) > 0) {
return true;
}
}
@@ -250,12 +252,10 @@ public class SimplexSolver extends Linea
final double rhs = tableau.getEntry(i, tableau.getWidth() - 1);
final double entry = tableau.getEntry(i, col);
- // zero-out tableau entries that are too close to zero to avoid
- // numerical instabilities as these entries might be used as
divisor
- if (FastMath.abs(entry) < cutOff) {
- tableau.setEntry(i, col, 0);
- } else if (Precision.compareTo(entry, 0d, maxUlps) > 0) {
- final double ratio = rhs / entry;
+ // only consider pivot elements larger than the cutOff threshold
+ // selecting others may lead to degeneracy or numerical
instabilities
+ if (Precision.compareTo(entry, 0d, cutOff) > 0) {
+ final double ratio = FastMath.abs(rhs / entry);
// check if the entry is strictly equal to the current min
ratio
// do not use a ulp/epsilon check
final int cmp = Double.compare(ratio, minRatio);
@@ -389,6 +389,20 @@ public class SimplexSolver extends Linea
while (!tableau.isOptimal()) {
doIteration(tableau);
}
- return tableau.getSolution();
+
+ // check that the solution respects the nonNegative restriction in case
+ // the epsilon/cutOff values are too large for the actual linear
problem
+ // (e.g. with very small constraint coefficients), the solver might
actually
+ // find a non-valid solution (with negative coefficients).
+ final PointValuePair solution = tableau.getSolution();
+ if (isRestrictedToNonNegative()) {
+ final double[] coeff = solution.getPoint();
+ for (int i = 0; i < coeff.length; i++) {
+ if (Precision.compareTo(coeff[i], 0, epsilon) < 0) {
+ throw new NoFeasibleSolutionException();
+ }
+ }
+ }
+ return solution;
}
}
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=1552792&r1=1552791&r2=1552792&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
Fri Dec 20 19:33:03 2013
@@ -749,48 +749,34 @@ public class SimplexSolverTest {
@Test
public void testSolutionCallback() {
- // re-use the problem from testcase for MATH-930
- // it normally requires 144 iterations
- final List<LinearConstraint> constraints = createMath930Constraints();
-
- double[] objFunctionCoeff = new double[33];
- objFunctionCoeff[3] = 1;
- LinearObjectiveFunction f = new
LinearObjectiveFunction(objFunctionCoeff, 0);
- SimplexSolver solver = new SimplexSolver(1e-2, 10, 1e-6);
+ // re-use the problem from testcase for MATH-288
+ // it normally requires 5 iterations
+ LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {
7, 3, 0, 0 }, 0 );
+
+ List<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
+ constraints.add(new LinearConstraint(new double[] { 3, 0, -5, 0 },
Relationship.LEQ, 0.0));
+ constraints.add(new LinearConstraint(new double[] { 2, 0, 0, -5 },
Relationship.LEQ, 0.0));
+ constraints.add(new LinearConstraint(new double[] { 0, 3, 0, -5 },
Relationship.LEQ, 0.0));
+ constraints.add(new LinearConstraint(new double[] { 1, 0, 0, 0 },
Relationship.LEQ, 1.0));
+ constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 0 },
Relationship.LEQ, 1.0));
+
+ final SimplexSolver solver = new SimplexSolver();
final SolutionCallback callback = new SolutionCallback();
-
- // 1. iteration limit is too low to reach phase 2 -> no feasible
solution
- try {
- // we need to use a DeterministicLinearConstraintSet to always get
the same behavior
- solver.optimize(new MaxIter(100), f, new
LinearConstraintSet(constraints),
- GoalType.MINIMIZE, new
NonNegativeConstraint(true), callback,
- PivotSelectionRule.BLAND);
- Assert.fail("expected TooManyIterationsException");
- } catch (TooManyIterationsException ex) {
- // expected
- }
-
- final PointValuePair solution1 = callback.getSolution();
- Assert.assertNull(solution1);
- // 2. iteration limit allows to reach phase 2, but too low to find an
optimal solution
try {
- // we need to use a DeterministicLinearConstraintSet to always get
the same behavior
- solver.optimize(new MaxIter(140), f, new
LinearConstraintSet(constraints),
- GoalType.MINIMIZE, new
NonNegativeConstraint(true), callback,
- PivotSelectionRule.DANTZIG);
- System.out.println(solver.getIterations());
+ solver.optimize(new MaxIter(3), f, new
LinearConstraintSet(constraints),
+ GoalType.MAXIMIZE, new
NonNegativeConstraint(true), callback);
Assert.fail("expected TooManyIterationsException");
} catch (TooManyIterationsException ex) {
// expected
}
- final PointValuePair solution2 = callback.getSolution();
- Assert.assertNotNull(solution2);
- Assert.assertTrue(validSolution(solution2, constraints, 1e-4));
- // the solution is clearly not optimal
- Assert.assertEquals(0.3752298, solution2.getValue(), 5e-1);
+ final PointValuePair solution = callback.getSolution();
+ Assert.assertNotNull(solution);
+ Assert.assertTrue(validSolution(solution, constraints, 1e-4));
+ // the solution is clearly not optimal: optimal = 10.0
+ Assert.assertEquals(7.0, solution.getValue(), 1e-4);
}
/**
