commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject 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/
Date Mon, 18 Nov 2013 21:24:32 GMT
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);
+        }
+    }
+
 }



Mime
View raw message