You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2013/11/18 22:24:32 UTC
svn commit: r1543169 - in /commons/proper/math/trunk/src: changes/
main/java/org/apache/commons/math3/optim/linear/
test/java/org/apache/commons/math3/optim/linear/
Author: tn
Date: Mon Nov 18 21:24:32 2013
New Revision: 1543169
URL: http://svn.apache.org/r1543169
Log:
[MATH-970] Added SolutionCallback to SimplexSolver to retrieve the best solution found.
Added:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SolutionCallback.java (with props)
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/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=1543169&r1=1543168&r2=1543169&view=diff
==============================================================================
--- commons/proper/math/trunk/src/changes/changes.xml (original)
+++ commons/proper/math/trunk/src/changes/changes.xml Mon Nov 18 21:24:32 2013
@@ -51,6 +51,12 @@ If the output is not quite correct, chec
</properties>
<body>
<release version="3.3" date="TBD" description="TBD">
+ <action dev="tn" type="add" issue="MATH-970">
+ Added possibility to retrieve the best found solution of the "SimplexSolver" in case
+ the iteration limit has been reached. The "optimize(OptimizationData...)" method now
+ supports a "SolutionCallback" which provides access to the best solution if
+ a feasible solution could be found (phase 2 of the Two-Phase simplex method has been reached).
+ </action>
<action dev="tn" type="update" issue="MATH-1031" due-to="Thorsten Schäfer">
Added new class "ClusterEvaluator" to evaluate the result of a clustering algorithm
and refactored existing evaluation code in "MultiKMeansPlusPlusClusterer"
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=1543169&r1=1543168&r2=1543169&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 Mon Nov 18 21:24:32 2013
@@ -18,7 +18,9 @@ package org.apache.commons.math3.optim.l
import java.util.ArrayList;
import java.util.List;
+
import org.apache.commons.math3.exception.TooManyIterationsException;
+import org.apache.commons.math3.optim.OptimizationData;
import org.apache.commons.math3.optim.PointValuePair;
import org.apache.commons.math3.util.Precision;
@@ -76,6 +78,12 @@ public class SimplexSolver extends Linea
private final double cutOff;
/**
+ * The solution callback to access the best solution found so far in case
+ * the optimizer fails to find an optimal solution within the iteration limits.
+ */
+ private SolutionCallback solutionCallback;
+
+ /**
* Builds a simplex solver with default settings.
*/
public SimplexSolver() {
@@ -115,6 +123,53 @@ public class SimplexSolver extends Linea
}
/**
+ * {@inheritDoc}
+ *
+ * @param optData Optimization data. In addition to those documented in
+ * {@link LinearOptimizer#optimize(OptimizationData...)
+ * LinearOptimizer}, this method will register the following data:
+ * <ul>
+ * <li>{@link SolutionCallback}</li>
+ * </ul>
+ *
+ * @return {@inheritDoc}
+ * @throws TooManyIterationsException if the maximal number of iterations is exceeded.
+ */
+ @Override
+ public PointValuePair optimize(OptimizationData... optData)
+ throws TooManyIterationsException {
+ // Set up base class and perform computation.
+ return super.optimize(optData);
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * @param optData Optimization data.
+ * In addition to those documented in
+ * {@link LinearOptimizer#parseOptimizationData(OptimizationData[])
+ * LinearOptimizer}, this method will register the following data:
+ * <ul>
+ * <li>{@link SolutionCallback}</li>
+ * </ul>
+ */
+ @Override
+ protected void parseOptimizationData(OptimizationData... optData) {
+ // Allow base class to register its own data.
+ super.parseOptimizationData(optData);
+
+ // reset the callback before parsing
+ solutionCallback = null;
+
+ for (OptimizationData data : optData) {
+ if (data instanceof SolutionCallback) {
+ solutionCallback = (SolutionCallback) data;
+ continue;
+ }
+ }
+ }
+
+ /**
* Returns the column with the most negative coefficient in the objective function row.
*
* @param tableau Simple tableau for the problem.
@@ -278,6 +333,13 @@ public class SimplexSolver extends Linea
throws TooManyIterationsException,
UnboundedSolutionException,
NoFeasibleSolutionException {
+
+ // reset the tableau to indicate a non-feasible solution in case
+ // we do not pass phase 1 successfully
+ if (solutionCallback != null) {
+ solutionCallback.setTableau(null);
+ }
+
final SimplexTableau tableau =
new SimplexTableau(getFunction(),
getConstraints(),
@@ -290,6 +352,11 @@ public class SimplexSolver extends Linea
solvePhase1(tableau);
tableau.dropPhase1Objective();
+ // after phase 1, we are sure to have a feasible solution
+ if (solutionCallback != null) {
+ solutionCallback.setTableau(tableau);
+ }
+
while (!tableau.isOptimal()) {
doIteration(tableau);
}
Added: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SolutionCallback.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SolutionCallback.java?rev=1543169&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SolutionCallback.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SolutionCallback.java Mon Nov 18 21:24:32 2013
@@ -0,0 +1,55 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.math3.optim.linear;
+
+import org.apache.commons.math3.optim.OptimizationData;
+import org.apache.commons.math3.optim.PointValuePair;
+
+/**
+ * A constraint for a linear optimization problem indicating whether all
+ * variables must be restricted to non-negative values.
+ *
+ * @version $Id$
+ * @since 3.3
+ */
+public class SolutionCallback implements OptimizationData {
+ /** The SimplexTableau used by the SimplexSolver. */
+ private SimplexTableau tableau;
+
+ /**
+ * Set the simplex tableau used during the optimization once a feasible
+ * solution has been found.
+ *
+ * @param tableau the simplex tableau containing a feasible solution
+ */
+ void setTableau(final SimplexTableau tableau) {
+ this.tableau = tableau;
+ }
+
+ /**
+ * Retrieve the best solution found so far.
+ * <p>
+ * <b>Note:</b> the returned solution may not be optimal, e.g. in case
+ * the optimizer did reach the iteration limits.
+ *
+ * @return the best solution found so far by the optimizer, or {@code null} if
+ * no feasible solution could be found
+ */
+ public PointValuePair getSolution() {
+ return tableau != null ? tableau.getSolution() : null;
+ }
+}
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SolutionCallback.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SolutionCallback.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SolutionCallback.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
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=1543169&r1=1543168&r2=1543169&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 Mon Nov 18 21:24:32 2013
@@ -18,7 +18,10 @@ package org.apache.commons.math3.optim.l
import java.util.ArrayList;
import java.util.Collection;
+import java.util.Collections;
import java.util.List;
+
+import org.apache.commons.math3.exception.TooManyIterationsException;
import org.apache.commons.math3.optim.MaxIter;
import org.apache.commons.math3.optim.nonlinear.scalar.GoalType;
import org.apache.commons.math3.optim.PointValuePair;
@@ -318,7 +321,20 @@ public class SimplexSolverTest {
@Test
public void testMath930() {
- Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
+ Collection<LinearConstraint> constraints = createMath930Constraints();
+
+ double[] objFunctionCoeff = new double[33];
+ objFunctionCoeff[3] = 1;
+ LinearObjectiveFunction f = new LinearObjectiveFunction(objFunctionCoeff, 0);
+ 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-4);
+ }
+
+ private List<LinearConstraint> createMath930Constraints() {
+ List<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
constraints.add(new LinearConstraint(new double[] {1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 0}, Relationship.GEQ, 0.0));
constraints.add(new LinearConstraint(new double[] {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1}, Relationship.GEQ, 0.0));
constraints.add(new LinearConstraint(new double[] {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1}, Relationship.LEQ, 0.0));
@@ -416,15 +432,7 @@ public class SimplexSolverTest {
constraints.add(new LinearConstraint(new double[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, Relationship.GEQ, 0.0));
constraints.add(new LinearConstraint(new double[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -0.028754}, Relationship.LEQ, 0.0));
constraints.add(new LinearConstraint(new double[] {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, Relationship.EQ, 1.0));
-
- double[] objFunctionCoeff = new double[33];
- objFunctionCoeff[3] = 1;
- LinearObjectiveFunction f = new LinearObjectiveFunction(objFunctionCoeff, 0);
- 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-4);
+ return constraints;
}
@Test
@@ -710,6 +718,49 @@ public class SimplexSolverTest {
Assert.assertEquals(7518.0, solution.getValue(), .0000001);
}
+ @Test
+ public void testSolutionCallback() {
+ // re-use the problem from testcase for MATH-930
+ // it normally requires 186 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-4, 10, 1e-6);
+
+ 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 DeterministicLinearConstraintSet(constraints),
+ GoalType.MINIMIZE, new NonNegativeConstraint(true), callback);
+ 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(180), f, new DeterministicLinearConstraintSet(constraints),
+ GoalType.MINIMIZE, 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);
+ }
+
/**
* Converts a test string to a {@link LinearConstraint}.
* Ex: x0 + x1 + x2 + x3 - x12 = 0
@@ -772,4 +823,42 @@ public class SimplexSolverTest {
return true;
}
+
+ /**
+ * Needed for deterministic tests, as the original LinearConstraintSet uses as HashSet.
+ */
+ public class DeterministicLinearConstraintSet extends LinearConstraintSet {
+ /** Set of constraints. */
+ private final List<LinearConstraint> linearConstraints = new ArrayList<LinearConstraint>();
+
+ /**
+ * Creates a set containing the given constraints.
+ *
+ * @param constraints Constraints.
+ */
+ public DeterministicLinearConstraintSet(LinearConstraint... constraints) {
+ for (LinearConstraint c : constraints) {
+ linearConstraints.add(c);
+ }
+ }
+
+ /**
+ * Creates a set containing the given constraints.
+ *
+ * @param constraints Constraints.
+ */
+ public DeterministicLinearConstraintSet(Collection<LinearConstraint> constraints) {
+ linearConstraints.addAll(constraints);
+ }
+
+ /**
+ * Gets the set of linear constraints.
+ *
+ * @return the constraints.
+ */
+ public Collection<LinearConstraint> getConstraints() {
+ return Collections.unmodifiableList(linearConstraints);
+ }
+ }
+
}