Return-Path: X-Original-To: apmail-commons-commits-archive@minotaur.apache.org Delivered-To: apmail-commons-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 2552A1002A for ; Mon, 18 Nov 2013 21:24:55 +0000 (UTC) Received: (qmail 71252 invoked by uid 500); 18 Nov 2013 21:24:54 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 71187 invoked by uid 500); 18 Nov 2013 21:24:54 -0000 Mailing-List: contact commits-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list commits@commons.apache.org Received: (qmail 71180 invoked by uid 99); 18 Nov 2013 21:24:54 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 18 Nov 2013 21:24:54 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 18 Nov 2013 21:24:52 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id D219A238889B; Mon, 18 Nov 2013 21:24:32 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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 -0000 To: commits@commons.apache.org From: tn@apache.org X-Mailer: svnmailer-1.0.9 Message-Id: <20131118212432.D219A238889B@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org 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 + + 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). + 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: + *

{@link SolutionCallback}

+ * + * @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: + *

{@link SolutionCallback}

+ */ + @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. + *

+ * Note: 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 constraints = new ArrayList(); + Collection 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 createMath930Constraints() { + List constraints = new ArrayList(); 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 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 linearConstraints = new ArrayList(); + + /** + * 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 constraints) { + linearConstraints.addAll(constraints); + } + + /** + * Gets the set of linear constraints. + * + * @return the constraints. + */ + public Collection getConstraints() { + return Collections.unmodifiableList(linearConstraints); + } + } + }