commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r758920 [1/2] - in /commons/proper/math/trunk: ./ src/java/org/apache/commons/math/ src/java/org/apache/commons/math/optimization/ src/java/org/apache/commons/math/optimization/general/ src/java/org/apache/commons/math/optimization/linear/ ...
Date Thu, 26 Mar 2009 23:25:31 GMT
Author: luc
Date: Thu Mar 26 23:25:30 2009
New Revision: 758920

URL: http://svn.apache.org/viewvc?rev=758920&view=rev
Log:
added an implementation of Dantzig's simplex algorithm
to solve constrained linear optimization problems
JIRA: MATH-246

Added:
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/AbstractLinearOptimizer.java   (with props)
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearConstraint.java   (with props)
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearObjectiveFunction.java   (with props)
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearOptimizer.java   (with props)
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/NoFeasibleSolutionException.java   (with props)
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/Relationship.java   (with props)
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java   (with props)
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java   (with props)
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/UnboundedSolutionException.java   (with props)
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/package.html   (with props)
    commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java   (with props)
    commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java   (with props)
Modified:
    commons/proper/math/trunk/NOTICE.txt
    commons/proper/math/trunk/pom.xml
    commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/OptimizationException.java
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/general/GaussNewtonOptimizer.java
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/general/NonLinearConjugateGradientOptimizer.java
    commons/proper/math/trunk/src/site/xdoc/changes.xml

Modified: commons/proper/math/trunk/NOTICE.txt
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/NOTICE.txt?rev=758920&r1=758919&r2=758920&view=diff
==============================================================================
--- commons/proper/math/trunk/NOTICE.txt (original)
+++ commons/proper/math/trunk/NOTICE.txt Thu Mar 26 23:25:30 2009
@@ -4,6 +4,9 @@
 This product includes software developed by
 The Apache Software Foundation (http://www.apache.org/).
 
+This product includes software developed by
+Benjamin McCann (http://www.benmccann.com) and distributed with with
+the following copyright: Copyright 2009 Google Inc.
 
 This product includes software translated from the lmder, lmpar
 and qrsolv Fortran routines from the Minpack package and

Modified: commons/proper/math/trunk/pom.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/pom.xml?rev=758920&r1=758919&r2=758920&view=diff
==============================================================================
--- commons/proper/math/trunk/pom.xml (original)
+++ commons/proper/math/trunk/pom.xml Thu Mar 26 23:25:30 2009
@@ -143,6 +143,7 @@
     </contributor>
     <contributor>
       <name>Benjamin McCann</name>
+      <url>http://www.benmccann.com"</url>
     </contributor>
     <contributor>
       <name>Fredrik Norin</name>

Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java?rev=758920&r1=758919&r2=758920&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java Thu Mar 26 23:25:30 2009
@@ -146,6 +146,14 @@
     { "unable to bracket optimum in line search",
       "impossible d''encadrer l''optimum lors de la recherche lin\u00e9aire" },
 
+    // org.apache.commons.math.optimization.linear2.NoFeasibleSolutionException
+    { "no feasible solution",
+      "aucune solution r\u00e9alisable" },
+
+    // org.apache.commons.math.optimization.linear2.UnboundedSolutionException
+    { "unbounded solution",
+      "solution non born\u00e9e" },
+
     // org.apache.commons.math.geometry.CardanEulerSingularityException
     { "Cardan angles singularity",
       "singularit\u00e9 d''angles de Cardan" },

Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/OptimizationException.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/OptimizationException.java?rev=758920&r1=758919&r2=758920&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/OptimizationException.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/OptimizationException.java Thu Mar 26 23:25:30 2009
@@ -20,7 +20,7 @@
 import org.apache.commons.math.ConvergenceException;
 
 /** 
- * This class represents exceptions thrown by the estimation solvers.
+ * This class represents exceptions thrown by optimizers.
  *
  * @version $Revision$ $Date$
  * @since 1.2

Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/general/GaussNewtonOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/general/GaussNewtonOptimizer.java?rev=758920&r1=758919&r2=758920&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/general/GaussNewtonOptimizer.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/general/GaussNewtonOptimizer.java Thu Mar 26 23:25:30 2009
@@ -53,7 +53,7 @@
     /** Simple constructor with default settings.
      * <p>The convergence check is set to a {@link SimpleVectorialValueChecker}
      * and the maximal number of evaluation is set to
-     * {@link AbstractLeastSquaresOptimizer#DEFAULT_MAX_ITERATIONS}.
+     * {@link AbstractLinearOptimizer#DEFAULT_MAX_ITERATIONS}.
      * @param useLU if true, the normal equations will be solved using LU
      * decomposition, otherwise they will be solved using QR decomposition
      */

Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/general/NonLinearConjugateGradientOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/general/NonLinearConjugateGradientOptimizer.java?rev=758920&r1=758919&r2=758920&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/general/NonLinearConjugateGradientOptimizer.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/general/NonLinearConjugateGradientOptimizer.java Thu Mar 26 23:25:30 2009
@@ -63,7 +63,7 @@
     /** Simple constructor with default settings.
      * <p>The convergence check is set to a {@link SimpleVectorialValueChecker}
      * and the maximal number of evaluation is set to
-     * {@link AbstractLeastSquaresOptimizer#DEFAULT_MAX_EVALUATIONS}.
+     * {@link AbstractLinearOptimizer#DEFAULT_MAX_EVALUATIONS}.
      * @param updateFormula formula to use for updating the &beta; parameter,
      * must be one of {@link UpdateFormula#FLETCHER_REEVES} or {@link
      * UpdateFormula#POLAK_RIBIERE}

Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/AbstractLinearOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/AbstractLinearOptimizer.java?rev=758920&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/AbstractLinearOptimizer.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/AbstractLinearOptimizer.java Thu Mar 26 23:25:30 2009
@@ -0,0 +1,124 @@
+/*
+ * 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.math.optimization.linear;
+
+import java.util.Collection;
+
+import org.apache.commons.math.FunctionEvaluationException;
+import org.apache.commons.math.MaxIterationsExceededException;
+import org.apache.commons.math.optimization.GoalType;
+import org.apache.commons.math.optimization.OptimizationException;
+import org.apache.commons.math.optimization.RealPointValuePair;
+
+/**
+ * Base class for implementing linear optimizers.
+ * <p>This base class handles the boilerplate methods associated to thresholds
+ * settings and iterations counters.</p>
+ * @version $Revision$ $Date$
+ * @since 2.0
+ *
+ */
+public abstract class AbstractLinearOptimizer implements LinearOptimizer {
+
+    /** Serializable version identifier */
+    private static final long serialVersionUID = 8581325080951819398L;
+
+    /** Default maximal number of iterations allowed. */
+    public static final int DEFAULT_MAX_ITERATIONS = 100;
+
+    /** Maximal number of iterations allowed. */
+    private int maxIterations;
+
+    /** Number of iterations already performed. */
+    private int iterations;
+
+    /** Linear objective function. */
+    protected LinearObjectiveFunction f;
+
+    /** Linear constraints. */
+    protected Collection<LinearConstraint> constraints;
+
+    /** Type of optimization goal: either {@link GoalType#MAXIMIZE} or {@link GoalType#MINIMIZE}. */
+    protected GoalType goalType;
+
+    /** Whether to restrict the variables to non-negative values. */
+    protected boolean restrictToNonNegative;
+
+    /** Simple constructor with default settings.
+     * <p>The maximal number of evaluation is set to its default value.</p>
+     */
+    protected AbstractLinearOptimizer() {
+        setMaxIterations(DEFAULT_MAX_ITERATIONS);
+    }
+
+    /** {@inheritDoc} */
+    public void setMaxIterations(int maxIterations) {
+        this.maxIterations = maxIterations;
+    }
+
+    /** {@inheritDoc} */
+    public int getMaxIterations() {
+        return maxIterations;
+    }
+
+    /** {@inheritDoc} */
+    public int getIterations() {
+        return iterations;
+    }
+
+    /** Increment the iterations counter by 1.
+     * @exception OptimizationException if the maximal number
+     * of iterations is exceeded
+     */
+    protected void incrementIterationsCounter()
+        throws OptimizationException {
+        if (++iterations > maxIterations) {
+            if (++iterations > maxIterations) {
+                throw new OptimizationException(new MaxIterationsExceededException(maxIterations));
+            }
+        }
+    }
+
+    /** {@inheritDoc} */
+    public RealPointValuePair optimize(final LinearObjectiveFunction f,
+                                       final Collection<LinearConstraint> constraints,
+                                       final GoalType goalType, final boolean restrictToNonNegative)
+         throws OptimizationException {
+
+        // store linear problem characteristics
+        this.f                     = f;
+        this.constraints           = constraints;
+        this.goalType              = goalType;
+        this.restrictToNonNegative = restrictToNonNegative;
+
+        iterations = 0;
+
+        // solve the problem
+        return doOptimize();
+
+    }
+
+    /** Perform the bulk of optimization algorithm.
+     * @return the point/value pair giving the optimal value for objective function
+     * @exception OptimizationException if no solution fulfilling the constraints
+     * can be found in the allowed number of iterations
+     */
+    abstract protected RealPointValuePair doOptimize()
+        throws OptimizationException;
+
+}
\ No newline at end of file

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/AbstractLinearOptimizer.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/AbstractLinearOptimizer.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearConstraint.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearConstraint.java?rev=758920&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearConstraint.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearConstraint.java Thu Mar 26 23:25:30 2009
@@ -0,0 +1,183 @@
+/*
+ * 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.math.optimization.linear;
+
+import java.io.Serializable;
+
+import org.apache.commons.math.linear.RealVector;
+import org.apache.commons.math.linear.RealVectorImpl;
+
+
+/**
+ * A linear constraint for a linear optimization problem.
+ * <p>
+ * A linear constraint has one of the forms:
+ * <ul>
+ *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> = v</li>
+ *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> &lt;= v</li>
+ *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> >= v</li>
+ *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> =
+ *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+ *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> &lt;=
+ *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+ *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> >=
+ *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+ * </ul>
+ * The c<sub>i</sub>, l<sub>i</sub> or r<sub>i</sub> are the coefficients of the constraints, the x<sub>i</sub>
+ * are the coordinates of the current point and v is the value of the constraint.
+ * </p>
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public class LinearConstraint implements Serializable {
+
+    /** Serializable version identifier. */
+    private static final long serialVersionUID = -764632794033034092L;
+
+    /** Coefficients of the constraint (left hand side). */
+    private final RealVector coefficients;
+
+    /** Relationship between left and right hand sides (=, &lt;=, >=). */
+    private final Relationship relationship;
+
+    /** Value of the constraint (right hand side). */
+    private final double value;
+
+    /**
+     * Build a constraint involving a single linear equation.
+     * <p>
+     * A linear constraint with a single linear equation has one of the forms:
+     * <ul>
+     *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> = v</li>
+     *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> &lt;= v</li>
+     *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> >= v</li>
+     * </ul>
+     * </p>
+     * @param coefficients The coefficients of the constraint (left hand side)
+     * @param relationship The type of (in)equality used in the constraint
+     * @param value The value of the constraint (right hand side)
+     */
+    public LinearConstraint(final double[] coefficients, final Relationship relationship,
+                            final double value) {
+        this(new RealVectorImpl(coefficients), relationship, value);
+    }
+
+    /**
+     * Build a constraint involving a single linear equation.
+     * <p>
+     * A linear constraint with a single linear equation has one of the forms:
+     * <ul>
+     *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> = v</li>
+     *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> &lt;= v</li>
+     *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> >= v</li>
+     * </ul>
+     * </p>
+     * @param coefficients The coefficients of the constraint (left hand side)
+     * @param relationship The type of (in)equality used in the constraint
+     * @param value The value of the constraint (right hand side)
+     */
+    public LinearConstraint(final RealVector coefficients, final Relationship relationship,
+                            final double value) {
+        this.coefficients = coefficients;
+        this.relationship = relationship;
+        this.value        = value;
+    }
+
+    /**
+     * Build a constraint involving two linear equations.
+     * <p>
+     * A linear constraint with two linear equation has one of the forms:
+     * <ul>
+     *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> =
+     *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+     *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> &lt;=
+     *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+     *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> >=
+     *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+     * </ul>
+     * </p>
+     * @param lhsCoefficients The coefficients of the linear expression on the left hand side of the constraint
+     * @param lhsConstant The constant term of the linear expression on the left hand side of the constraint
+     * @param relationship The type of (in)equality used in the constraint
+     * @param rhsCoefficients The coefficients of the linear expression on the right hand side of the constraint
+     * @param rhsConstant The constant term of the linear expression on the right hand side of the constraint
+     */
+    public LinearConstraint(final double[] lhsCoefficients, final double lhsConstant,
+                            final Relationship relationship,
+                            final double[] rhsCoefficients, final double rhsConstant) {
+        double[] sub = new double[lhsCoefficients.length];
+        for (int i = 0; i < sub.length; ++i) {
+            sub[i] = lhsCoefficients[i] - rhsCoefficients[i];
+        }
+        this.coefficients = new RealVectorImpl(sub, false);
+        this.relationship = relationship;
+        this.value        = rhsConstant - lhsConstant;
+    }
+
+    /**
+     * Build a constraint involving two linear equations.
+     * <p>
+     * A linear constraint with two linear equation has one of the forms:
+     * <ul>
+     *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> =
+     *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+     *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> &lt;=
+     *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+     *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> >=
+     *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+     * </ul>
+     * </p>
+     * @param lhsCoefficients The coefficients of the linear expression on the left hand side of the constraint
+     * @param lhsConstant The constant term of the linear expression on the left hand side of the constraint
+     * @param relationship The type of (in)equality used in the constraint
+     * @param rhsCoefficients The coefficients of the linear expression on the right hand side of the constraint
+     * @param rhsConstant The constant term of the linear expression on the right hand side of the constraint
+     */
+    public LinearConstraint(final RealVector lhsCoefficients, final double lhsConstant,
+                            final Relationship relationship,
+                            final RealVector rhsCoefficients, final double rhsConstant) {
+        this.coefficients = lhsCoefficients.subtract(rhsCoefficients);
+        this.relationship = relationship;
+        this.value        = rhsConstant - lhsConstant;
+    }
+
+    /**
+     * Get the coefficients of the constraint (left hand side).
+     * @return coefficients of the constraint (left hand side)
+     */
+    public RealVector getCoefficients() {
+        return coefficients;
+    }
+
+    /**
+     * Get the relationship between left and right hand sides.
+     * @return relationship between left and right hand sides
+     */
+    public Relationship getRelationship() {
+        return relationship;
+    }
+
+    /**
+     * Get the value of the constraint (right hand side).
+     * @return value of the constraint (right hand side)
+     */
+    public double getValue() {
+        return value;
+    }
+
+}

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearConstraint.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearConstraint.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearObjectiveFunction.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearObjectiveFunction.java?rev=758920&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearObjectiveFunction.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearObjectiveFunction.java Thu Mar 26 23:25:30 2009
@@ -0,0 +1,100 @@
+/*
+ * 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.math.optimization.linear;
+
+import java.io.Serializable;
+
+import org.apache.commons.math.linear.RealVector;
+import org.apache.commons.math.linear.RealVectorImpl;
+
+/**
+ * An objective function for a linear optimization problem.
+ * <p>
+ * A linear objective function has one the form:
+ * <pre>
+ * c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> + d
+ * </pre>
+ * The c<sub>i</sub> and d are the coefficients of the equation,
+ * the x<sub>i</sub> are the coordinates of the current point.
+ * </p>
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public class LinearObjectiveFunction implements Serializable {
+
+    /** Serializable version identifier. */
+    private static final long serialVersionUID = -4531815507568396090L;
+
+    /** Coefficients of the constraint (c<sub>i</sub>). */
+    private final RealVector coefficients;
+
+    /** Constant term of the linear equation. */
+    private final double constantTerm;
+
+    /**
+     * @param coefficients The coefficients for the linear equation being optimized
+     * @param constantTerm The constant term of the linear equation
+     */
+    public LinearObjectiveFunction(double[] coefficients, double constantTerm) {
+        this(new RealVectorImpl(coefficients), constantTerm);
+    }
+
+    /**
+     * @param coefficients The coefficients for the linear equation being optimized
+     * @param constantTerm The constant term of the linear equation
+     */
+    public LinearObjectiveFunction(RealVector coefficients, double constantTerm) {
+        this.coefficients = coefficients;
+        this.constantTerm = constantTerm;
+    }
+
+    /**
+     * Get the coefficients of the linear equation being optimized.
+     * @return coefficients of the linear equation being optimized
+     */
+    public RealVector getCoefficients() {
+        return coefficients;
+    }
+
+    /**
+     * Get the constant of the linear equation being optimized.
+     * @return constant of the linear equation being optimized
+     */
+    public double getConstantTerm() {
+        return constantTerm;
+    }
+
+    /**
+     * Compute the value of the linear equation at the current point
+     * @param point point at which linear equation must be evaluated
+     * @return value of the linear equation at the current point
+     */
+    public double getValue(final double[] point) {
+        return coefficients.dotProduct(point) + constantTerm;
+    }
+
+    /**
+     * Compute the value of the linear equation at the current point
+     * @param point point at which linear equation must be evaluated
+     * @return value of the linear equation at the current point
+     */
+    public double getValue(final RealVector point) {
+        return coefficients.dotProduct(point) + constantTerm;
+    }
+
+}

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearObjectiveFunction.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearObjectiveFunction.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearOptimizer.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearOptimizer.java?rev=758920&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearOptimizer.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearOptimizer.java Thu Mar 26 23:25:30 2009
@@ -0,0 +1,91 @@
+/*
+ * 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.math.optimization.linear;
+
+import java.io.Serializable;
+import java.util.Collection;
+
+import org.apache.commons.math.analysis.DifferentiableMultivariateRealFunction;
+import org.apache.commons.math.optimization.GoalType;
+import org.apache.commons.math.optimization.OptimizationException;
+import org.apache.commons.math.optimization.RealPointValuePair;
+
+/** 
+ * This interface represents an optimization algorithm for linear problems.
+ * <p>Optimization algorithms find the input point set that either {@link GoalType
+ * maximize or minimize} an objective function. In the linear case the form of
+ * the function is restricted to
+ * <pre>
+ * c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> = v
+ * </pre>
+ * and there may be linear constraints too, of one of the forms:
+ * <ul>
+ *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> = v</li>
+ *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> &lt;= v</li>
+ *   <li>c<sub>1</sub>x<sub>1</sub> + ... c<sub>n</sub>x<sub>n</sub> >= v</li>
+ *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> =
+ *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+ *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> &lt;=
+ *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+ *   <li>l<sub>1</sub>x<sub>1</sub> + ... l<sub>n</sub>x<sub>n</sub> + l<sub>cst</sub> >=
+ *       r<sub>1</sub>x<sub>1</sub> + ... r<sub>n</sub>x<sub>n</sub> + r<sub>cst</sub></li>
+ * </ul>
+ * where the c<sub>i</sub>, l<sub>i</sub> or r<sub>i</sub> are the coefficients of
+ * the constraints, the x<sub>i</sub> are the coordinates of the current point and
+ * v is the value of the constraint.
+ * </p>
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public interface LinearOptimizer extends Serializable {
+
+    /** Set the maximal number of iterations of the algorithm.
+     * @param maxIterations maximal number of function calls
+     */
+    void setMaxIterations(int maxIterations);
+
+    /** Get the maximal number of iterations of the algorithm.
+     * @return maximal number of iterations
+     */
+    int getMaxIterations();
+
+    /** Get the number of iterations realized by the algorithm.
+     * <p>
+     * The number of evaluations corresponds to the last call to the
+     * {@link #optimize(DifferentiableMultivariateRealFunction, GoalType, double[]) optimize}
+     * method. It is 0 if the method has not been called yet.
+     * </p>
+     * @return number of iterations
+     */
+    int getIterations();
+
+    /** Optimizes an objective function.
+     * @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
+     * @return point/value pair giving the optimal value for objective function
+     * @exception OptimizationException if no solution fulfilling the constraints
+     * can be found in the allowed number of iterations
+     */
+   RealPointValuePair optimize(LinearObjectiveFunction f, Collection<LinearConstraint> constraints,
+                               GoalType goalType, boolean restrictToNonNegative)
+        throws OptimizationException;
+
+}

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/LinearOptimizer.java
------------------------------------------------------------------------------
    svn:mergeinfo = 

Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/NoFeasibleSolutionException.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/NoFeasibleSolutionException.java?rev=758920&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/NoFeasibleSolutionException.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/NoFeasibleSolutionException.java Thu Mar 26 23:25:30 2009
@@ -0,0 +1,40 @@
+/*
+ * 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.math.optimization.linear;
+
+import org.apache.commons.math.optimization.OptimizationException;
+
+/**
+ * This class represents exceptions thrown by optimizers when no solution
+ * fulfills the constraints.
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public class NoFeasibleSolutionException extends OptimizationException {
+
+    /** Serializable version identifier. */
+    private static final long serialVersionUID = -3044253632189082760L;
+
+    /** 
+     * Simple constructor using a default message.
+     */
+    public NoFeasibleSolutionException() {
+        super("no feasible solution");
+    }
+
+}

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/NoFeasibleSolutionException.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/NoFeasibleSolutionException.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/Relationship.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/Relationship.java?rev=758920&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/Relationship.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/Relationship.java Thu Mar 26 23:25:30 2009
@@ -0,0 +1,67 @@
+/*
+ * 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.math.optimization.linear;
+
+/**
+ * Types of relationships between two cells in a Solver {@link LinearConstraint}.
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public enum Relationship {
+
+    /** Equality relationship. */
+    EQ("="),
+
+    /** Lesser than or equal relationship. */
+    LEQ("<="),
+
+    /** Greater than or equal relationship. */
+    GEQ(">=");
+
+    /** Display string for the relationship. */
+    private String stringValue;
+
+    /** Simple constructor.
+     * @param stringValue display string for the relationship
+     */
+    private Relationship(String stringValue) {
+        this.stringValue = stringValue;
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public String toString() {
+        return stringValue;
+    }
+
+    /**
+     * Get the relationship obtained when multiplying all coefficients by -1.
+     * @return relationship obtained when multiplying all coefficients by -1
+     */
+    public Relationship oppositeRelationship() {
+        switch (this) {
+        case LEQ :
+            return GEQ;
+        case GEQ :
+            return LEQ;
+        default :
+            return EQ;
+        }
+    }
+
+}

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/Relationship.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/Relationship.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java?rev=758920&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java Thu Mar 26 23:25:30 2009
@@ -0,0 +1,197 @@
+/*
+ * 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.math.optimization.linear;
+
+import org.apache.commons.math.optimization.OptimizationException;
+import org.apache.commons.math.optimization.RealPointValuePair;
+import org.apache.commons.math.util.MathUtils;
+
+
+/**
+ * Solves a linear problem using the Two-Phase Simplex Method.
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public class SimplexSolver extends AbstractLinearOptimizer {
+
+    /** Serializable version identifier. */
+    private static final long serialVersionUID = -4886937648715323786L;
+
+    /** Default amount of error to accept in floating point comparisons. */ 
+    private static final double DEFAULT_EPSILON = 1.0e-10;
+
+    /** Amount of error to accept in floating point comparisons. */ 
+    protected final double epsilon;  
+
+    /**
+     * Build a simplex solver with default settings.
+     */
+    public SimplexSolver() {
+        this(DEFAULT_EPSILON);
+    }
+
+    /**
+     * Build a simplex solver with a specified accepted amount of error
+     * @param epsilon the amount of error to accept in floating point comparisons
+     */
+    public SimplexSolver(final double epsilon) {
+        this.epsilon = epsilon;
+    }
+
+    /**
+     * Returns the column with the most negative coefficient in the objective function row.
+     * @param tableau simple tableau for the problem
+     * @return column with the most negative coefficient
+     */
+    private Integer getPivotColumn(SimplexTableau tableau) {
+        double minValue = 0;
+        Integer minPos = null;
+        for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++) {
+            if (tableau.getEntry(0, i) < minValue) {
+                minValue = tableau.getEntry(0, i);
+                minPos = i;
+            }
+        }
+        return minPos;
+    }
+
+    /**
+     * Returns the row with the minimum ratio as given by the minimum ratio test (MRT).
+     * @param tableau simple tableau for the problem
+     * @param col the column to test the ratio of.  See {@link #getPivotColumn()}
+     * @return row with the minimum ratio
+     */
+    private Integer getPivotRow(final int col, final SimplexTableau tableau) {
+        double minRatio = Double.MAX_VALUE;
+        Integer minRatioPos = null;
+        for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getHeight(); i++) {
+            double rhs = tableau.getEntry(i, tableau.getWidth() - 1);
+            if (tableau.getEntry(i, col) >= 0) {
+                double ratio = rhs / tableau.getEntry(i, col);
+                if (ratio < minRatio) {
+                    minRatio = ratio;
+                    minRatioPos = i; 
+                }
+            }
+        }
+        return minRatioPos;
+    }
+
+
+    /**
+     * Runs one iteration of the Simplex method on the given model.
+     * @param tableau simple tableau for the problem
+     * @throws OptimizationException if the maximal iteration count has been
+     * exceeded or if the model is found not to have a bounded solution
+     */
+    protected void doIteration(final SimplexTableau tableau)
+        throws OptimizationException {
+
+        incrementIterationsCounter();
+
+        Integer pivotCol = getPivotColumn(tableau);
+        Integer pivotRow = getPivotRow(pivotCol, tableau);
+        if (pivotRow == null) {
+            throw new UnboundedSolutionException();
+        }
+
+        // set the pivot element to 1
+        double pivotVal = tableau.getEntry(pivotRow, pivotCol);
+        tableau.divideRow(pivotRow, pivotVal);
+
+        // set the rest of the pivot column to 0
+        for (int i = 0; i < tableau.getHeight(); i++) {
+            if (i != pivotRow) {
+                double multiplier = tableau.getEntry(i, pivotCol);
+                tableau.subtractRow(i, pivotRow, multiplier);
+            }
+        }
+    }
+
+    /**
+     * Checks whether Phase 1 is solved.
+     * @param tableau simple tableau for the problem
+     * @return whether Phase 1 is solved
+     */
+    private boolean isPhase1Solved(final SimplexTableau tableau) {
+        if (tableau.getNumArtificialVariables() == 0) {
+            return true;
+        }
+        for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++) {
+            if (tableau.getEntry(0, i) < 0) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * Returns whether the problem is at an optimal state.
+     * @param tableau simple tableau for the problem
+     * @return whether the model has been solved
+     */
+    public boolean isOptimal(final SimplexTableau tableau) {
+        if (tableau.getNumArtificialVariables() > 0) {
+            return false;
+        }
+        for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++) {
+            if (tableau.getEntry(0, i) < 0) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * Solves Phase 1 of the Simplex method.
+     * @param tableau simple tableau for the problem
+     * @exception OptimizationException if the maximal number of iterations is
+     * exceeded, or if the problem is found not to have a bounded solution, or
+     * if there is no feasible solution
+     */
+    protected void solvePhase1(final SimplexTableau tableau)
+        throws OptimizationException {
+        // make sure we're in Phase 1
+        if (tableau.getNumArtificialVariables() == 0) {
+            return;
+        }
+
+        while (!isPhase1Solved(tableau)) {
+            doIteration(tableau);
+        }
+
+        // if W is not zero then we have no feasible solution
+        if (!MathUtils.equals(tableau.getEntry(0, tableau.getRhsOffset()), 0, epsilon)) {
+            throw new NoFeasibleSolutionException();
+        }
+    }
+
+    /** {@inheritDoc} */
+    public RealPointValuePair doOptimize()
+        throws OptimizationException {
+        final SimplexTableau tableau =
+            new SimplexTableau(f, constraints, goalType, restrictToNonNegative);
+        solvePhase1(tableau);
+        tableau.discardArtificialVariables();
+        while (!isOptimal(tableau)) {
+            doIteration(tableau);
+        }
+        return tableau.getSolution();
+    }
+
+}

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java?rev=758920&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java Thu Mar 26 23:25:30 2009
@@ -0,0 +1,473 @@
+/*
+ * 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.math.optimization.linear;
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+import org.apache.commons.math.linear.RealMatrix;
+import org.apache.commons.math.linear.RealMatrixImpl;
+import org.apache.commons.math.linear.RealVector;
+import org.apache.commons.math.optimization.GoalType;
+import org.apache.commons.math.optimization.RealPointValuePair;
+
+/**
+ * A tableau for use in the Simplex method.
+ * 
+ * <p>
+ * Example:
+ * <pre>
+ *   W |  Z |  x1 |  x2 |  x- | s1 |  s2 |  a1 |  RHS
+ * ---------------------------------------------------
+ *  -1    0    0     0     0     0     0     1     0   &lt;= phase 1 objective
+ *   0    1   -15   -10    0     0     0     0     0   &lt;= phase 2 objective
+ *   0    0    1     0     0     1     0     0     2   &lt;= constraint 1
+ *   0    0    0     1     0     0     1     0     3   &lt;= constraint 2
+ *   0    0    1     1     0     0     0     1     4   &lt;= constraint 3
+ * </pre>
+ * W: Phase 1 objective function</br>
+ * Z: Phase 2 objective function</br>
+ * x1 &amp; x2: Decision variables</br>
+ * x-: Extra decision variable to allow for negative values</br>
+ * s1 &amp; s2: Slack/Surplus variables</br>
+ * a1: Artificial variable</br>
+ * RHS: Right hand side</br>
+ * </p>
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+class SimplexTableau implements Serializable {
+
+    /** Serializable version identifier. */
+    private static final long serialVersionUID = -1369660067587938365L;
+
+    /** Linear objective function. */
+    private final LinearObjectiveFunction f;
+
+    /** Linear constraints. */
+    private final Collection<LinearConstraint> constraints;
+
+    /** Whether to restrict the variables to non-negative values. */
+    private final boolean restrictToNonNegative;
+
+    /** Simple tableau. */
+    protected RealMatrix tableau;
+
+    /** Number of decision variables. */
+    protected final int numDecisionVariables;
+
+    /** Number of slack variables. */
+    protected final int numSlackVariables;
+
+    /** Number of artificial variables. */
+    protected int numArtificialVariables;
+
+    /**
+     * 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
+     */
+    SimplexTableau(final LinearObjectiveFunction f,
+                   final Collection<LinearConstraint> constraints,
+                   final GoalType goalType, final boolean restrictToNonNegative) {
+        this.f                      = f;
+        this.constraints            = constraints;
+        this.restrictToNonNegative  = restrictToNonNegative;
+        this.numDecisionVariables   = getNumVariables() + (restrictToNonNegative ? 0 : 1);
+        this.numSlackVariables      = getConstraintTypeCounts(Relationship.LEQ) +
+                                      getConstraintTypeCounts(Relationship.GEQ);
+        this.numArtificialVariables = getConstraintTypeCounts(Relationship.EQ) +
+                                      getConstraintTypeCounts(Relationship.GEQ);
+        this.tableau = new RealMatrixImpl(createTableau(goalType == GoalType.MAXIMIZE));
+        initialize();
+    }
+
+    /**
+     * Create the tableau by itself.
+     * @param maximize if true, goal is to maximize the objective function
+     * @return created tableau
+     */
+    protected double[][] createTableau(final boolean maximize) {
+
+        // create a matrix of the correct size
+        List<LinearConstraint> constraints = getNormalizedConstraints();
+        int width = numDecisionVariables + numSlackVariables +
+        numArtificialVariables + getNumObjectiveFunctions() + 1; // + 1 is for RHS
+        int height = constraints.size() + getNumObjectiveFunctions();
+        double[][] matrix = new double[height][width];
+
+        // initialize the objective function rows
+        if (getNumObjectiveFunctions() == 2) {
+            matrix[0][0] = -1;
+        }
+        int zIndex = (getNumObjectiveFunctions() == 1) ? 0 : 1;
+        matrix[zIndex][zIndex] = maximize ? 1 : -1;
+        RealVector objectiveCoefficients =
+            maximize ? f.getCoefficients().mapMultiply(-1) : f.getCoefficients();
+            copyArray(objectiveCoefficients.getData(), matrix[zIndex], getNumObjectiveFunctions());
+            matrix[zIndex][width - 1] =
+                maximize ? f.getConstantTerm() : -1 * f.getConstantTerm();
+
+                if (!restrictToNonNegative) {
+                    matrix[zIndex][getSlackVariableOffset() - 1] =
+                        getInvertedCoeffiecientSum(objectiveCoefficients);
+                }
+
+                // initialize the constraint rows
+                int slackVar = 0;
+                int artificialVar = 0;
+                for (int i = 0; i < constraints.size(); i++) {
+                    LinearConstraint constraint = constraints.get(i);
+                    int row = getNumObjectiveFunctions() + i;
+
+                    // decision variable coefficients
+                    copyArray(constraint.getCoefficients().getData(), matrix[row], 1);
+
+                    // x-
+                    if (!restrictToNonNegative) {
+                        matrix[row][getSlackVariableOffset() - 1] =
+                            getInvertedCoeffiecientSum(constraint.getCoefficients());
+                    }
+
+                    // RHS
+                    matrix[row][width - 1] = constraint.getValue();
+
+                    // slack variables
+                    if (constraint.getRelationship() == Relationship.LEQ) {
+                        matrix[row][getSlackVariableOffset() + slackVar++] = 1;  // slack
+                    } else if (constraint.getRelationship() == Relationship.GEQ) {
+                        matrix[row][getSlackVariableOffset() + slackVar++] = -1; // excess
+                    }
+
+                    // artificial variables
+                    if ((constraint.getRelationship() == Relationship.EQ) ||
+                        (constraint.getRelationship() == Relationship.GEQ)) {
+                        matrix[0][getArtificialVariableOffset() + artificialVar] = 1; 
+                        matrix[row][getArtificialVariableOffset() + artificialVar++] = 1; 
+                    }
+                }
+
+                return matrix;
+    }
+
+    /** Get the number of variables.
+     * @return number of variables
+     */
+    public int getNumVariables() {
+        return f.getCoefficients().getDimension();
+    }
+
+    /**
+     * Get new versions of the constraints which have positive right hand sides.
+     * @return new versions of the constraints
+     */
+    public List<LinearConstraint> getNormalizedConstraints() {
+        List<LinearConstraint> normalized = new ArrayList<LinearConstraint>();
+        for (LinearConstraint constraint : constraints) {
+            normalized.add(normalize(constraint));
+        }
+        return normalized;
+    }
+
+    /**
+     * Get a new equation equivalent to this one with a positive right hand side.
+     * @param constraint reference constraint
+     * @return new equation
+     */
+    private LinearConstraint normalize(final LinearConstraint constraint) {
+        if (constraint.getValue() < 0) {
+            return new LinearConstraint(constraint.getCoefficients().mapMultiply(-1),
+                                        constraint.getRelationship().oppositeRelationship(),
+                                        -1 * constraint.getValue());
+        }
+        return new LinearConstraint(constraint.getCoefficients(), 
+                                    constraint.getRelationship(), constraint.getValue());
+    }
+
+    /**
+     * Get the number of objective functions in this tableau.
+     * @return 2 for Phase 1.  1 for Phase 2.
+     */
+    protected final int getNumObjectiveFunctions() {
+        return this.numArtificialVariables > 0 ? 2 : 1;
+    }
+
+    /**
+     * Get a count of constraints corresponding to a specified relationship.
+     * @param relationship relationship to count
+     * @return number of constraint with the specified relationship
+     */
+    private int getConstraintTypeCounts(final Relationship relationship) {
+        int count = 0;
+        for (final LinearConstraint constraint : constraints) {
+            if (constraint.getRelationship() == relationship) {
+                ++count;
+            }
+        }
+        return count;
+    }
+
+    /**
+     * Puts the tableau in proper form by zeroing out the artificial variables
+     * in the objective function via elementary row operations.
+     */
+    private void initialize() {
+        for (int artificialVar = 0; artificialVar < numArtificialVariables; artificialVar++) {
+            int row = getBasicRow(getArtificialVariableOffset() + artificialVar);
+            subtractRow(0, row, 1.0);
+        }
+    }
+
+    /**
+     * Get the -1 times the sum of all coefficients in the given array.
+     * @param coefficients coefficients to sum
+     * @return the -1 times the sum of all coefficients in the given array.
+     */
+    protected static double getInvertedCoeffiecientSum(final RealVector coefficients) {
+        double sum = 0;
+        for (double coefficient : coefficients.getData()) {
+            sum -= coefficient;
+        }
+        return sum;
+    }
+
+    /**
+     * Checks whether the given column is basic.
+     * @param col index of the column to check
+     * @return the row that the variable is basic in.  null if the column is not basic
+     */
+    private Integer getBasicRow(final int col) {
+        Integer row = null;
+        for (int i = getNumObjectiveFunctions(); i < getHeight(); i++) {
+            if (getEntry(i, col) != 0.0) {
+                if (row == null) {
+                    row = i;
+                } else {
+                    return null;
+                }
+            }
+        }
+        return row;
+    }
+
+    /**
+     * Removes the phase 1 objective function and artificial variables from this tableau.
+     */
+    protected void discardArtificialVariables() {
+        if (numArtificialVariables == 0) {
+            return;
+        }
+        int width = getWidth() - numArtificialVariables - 1;
+        int height = getHeight() - 1;
+        double[][] matrix = new double[height][width];
+        for (int i = 0; i < height; i++) {
+            for (int j = 0; j < width - 1; j++) {
+                matrix[i][j] = getEntry(i + 1, j + 1);
+            }
+            matrix[i][width - 1] = getEntry(i + 1, getRhsOffset());
+        }
+        this.tableau = new RealMatrixImpl(matrix);
+        this.numArtificialVariables = 0;
+    }
+
+
+    /**
+     * @param src the source array
+     * @param dest the destination array
+     * @param destPos the destination position
+     */
+    private void copyArray(final double[] src, final double[] dest,
+                           final int destPos) {
+        System.arraycopy(src, 0, dest, getNumObjectiveFunctions(), src.length); 
+    }
+
+    /**
+     * Get the current solution.
+     * <p>
+     * {@link #solve} should be called first for this to be the optimal solution.
+     * </p>
+     * @return current solution
+     */
+    protected RealPointValuePair getSolution() {
+        double[] coefficients = new double[getOriginalNumDecisionVariables()];
+        double mostNegative = getDecisionVariableValue(getOriginalNumDecisionVariables());
+        for (int i = 0; i < coefficients.length; i++) {
+            coefficients[i] =
+                getDecisionVariableValue(i) - (restrictToNonNegative ? 0 : mostNegative); 
+        }
+        return new RealPointValuePair(coefficients, f.getValue(coefficients));
+    }
+
+    /**
+     * Get the value of the given decision variable.  This is not the actual
+     * value as it is guaranteed to be >= 0 and thus must be corrected before
+     * being returned to the user.
+     * 
+     * @param decisionVariable The index of the decision variable
+     * @return The value of the given decision variable.
+     */
+    protected double getDecisionVariableValue(final int decisionVariable) {
+        Integer basicRow = getBasicRow(getNumObjectiveFunctions() + decisionVariable);
+        return basicRow == null ? 0 : getEntry(basicRow, getRhsOffset()); 
+    }
+
+    /**
+     * Subtracts a multiple of one row from another.
+     * <p>
+     * After application of this operation, the following will hold:
+     *   minuendRow = minuendRow - multiple * subtrahendRow
+     * </p>
+     * @param dividendRow index of the row
+     * @param divisor value of the divisor
+     */
+    protected void divideRow(final int dividendRow, final double divisor) {
+        for (int j = 0; j < getWidth(); j++) {
+            tableau.setEntry(dividendRow, j, tableau.getEntry(dividendRow, j) / divisor);
+        }
+    }
+
+    /**
+     * Subtracts a multiple of one row from another.
+     * <p>
+     * After application of this operation, the following will hold:
+     *   minuendRow = minuendRow - multiple * subtrahendRow
+     * </p>
+     * @param minuendRow row index
+     * @param subtrahendRow row index
+     * @param multiple multiplication factor
+     */
+    protected void subtractRow(final int minuendRow, final int subtrahendRow,
+                               final double multiple) {
+        for (int j = 0; j < getWidth(); j++) {
+            tableau.setEntry(minuendRow, j, tableau.getEntry(minuendRow, j) -
+                             multiple * tableau.getEntry(subtrahendRow, j));
+        }
+    }
+
+    /**
+     * Get the width of the tableau.
+     * @return width of the tableau
+     */
+    protected final int getWidth() {
+        return tableau.getColumnDimension();
+    }
+
+    /**
+     * Get the height of the tableau.
+     * @return height of the tableau
+     */
+    protected final int getHeight() {
+        return tableau.getRowDimension();
+    }
+
+    /** Get an entry of the tableau.
+     * @param row row index
+     * @param column column index
+     * @return entry at (row, column)
+     */
+    protected final double getEntry(final int row, final int column) {
+        return tableau.getEntry(row, column);
+    }
+
+    /** Set an entry of the tableau.
+     * @param row row index
+     * @param column column index
+     * param value for the entry
+     */
+    protected final void setEntry(final int row, final int column,
+                                  final double value) {
+        tableau.setEntry(row, column, value);
+    }
+
+    /**
+     * Get the offset of the first slack variable.
+     * @return offset of the first slack variable
+     */
+    protected final int getSlackVariableOffset() {
+        return getNumObjectiveFunctions() + numDecisionVariables;
+    }
+
+    /**
+     * Get the offset of the first artificial variable.
+     * @return offset of the first artificial variable
+     */
+    protected final int getArtificialVariableOffset() {
+        return getNumObjectiveFunctions() + numDecisionVariables + numSlackVariables;
+    }
+
+    /**
+     * Get the offset of the right hand side.
+     * @return offset of the right hand side
+     */
+    protected final int getRhsOffset() {
+        return getWidth() - 1;
+    }
+
+    /**
+     * Get the number of decision variables.
+     * <p>
+     * If variables are not restricted to positive values, this will include 1
+     * extra decision variable to represent the absolute value of the most
+     * negative variable.
+     * </p>
+     * @return number of decision variables
+     * @see #getOriginalNumDecisionVariables()
+     */
+    protected final int getNumDecisionVariables() {
+        return numDecisionVariables;
+    }
+
+    /**
+     * Get the original number of decision variables.
+     * @return original number of decision variables
+     * @see #getNumDecisionVariables()
+     */
+    protected final int getOriginalNumDecisionVariables() {
+        return restrictToNonNegative ? numDecisionVariables : numDecisionVariables - 1;
+    }
+
+    /**
+     * Get the number of slack variables.
+     * @return number of slack variables
+     */
+    protected final int getNumSlackVariables() {
+        return numSlackVariables;
+    }
+
+    /**
+     * Get the number of artificial variables.
+     * @return number of artificial variables
+     */
+    protected final int getNumArtificialVariables() {
+        return numArtificialVariables;
+    }
+
+    /**
+     * Get the tableau data.
+     * @return tableau data
+     */
+    protected final double[][] getData() {
+        return tableau.getData();
+    }
+
+}

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/UnboundedSolutionException.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/UnboundedSolutionException.java?rev=758920&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/UnboundedSolutionException.java (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/UnboundedSolutionException.java Thu Mar 26 23:25:30 2009
@@ -0,0 +1,40 @@
+/*
+ * 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.math.optimization.linear;
+
+import org.apache.commons.math.optimization.OptimizationException;
+
+/**
+ * This class represents exceptions thrown by optimizers when a solution
+ * escapes to infinity.
+ * @version $Revision$ $Date$
+ * @since 2.0
+ */
+public class UnboundedSolutionException extends OptimizationException {
+
+    /** Serializable version identifier. */
+    private static final long serialVersionUID = 940539497277290619L;
+
+    /** 
+     * Simple constructor using a default message.
+     */
+    public UnboundedSolutionException() {
+        super("unbounded solution");
+    }
+
+}

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/UnboundedSolutionException.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/UnboundedSolutionException.java
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Added: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/package.html
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/package.html?rev=758920&view=auto
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/package.html (added)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/package.html Thu Mar 26 23:25:30 2009
@@ -0,0 +1,22 @@
+<html>
+<!--
+   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.
+  -->
+    <!-- $Revision$ -->
+<body>
+This package provides optimization algorithms for linear constrained problems.
+</body>
+</html>

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/package.html
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/package.html
------------------------------------------------------------------------------
    svn:keywords = Author Date Id Revision

Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=758920&r1=758919&r2=758920&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Thu Mar 26 23:25:30 2009
@@ -39,6 +39,9 @@
   </properties>
   <body>
     <release version="2.0" date="TBD" description="TBD">
+      <action dev="luc" type="add" issue="MATH-246" due-to="Benjamin McCann">
+        Added an optimizer for constrained linear problems based on 2-phases standard simplex.
+      </action>
       <action dev="luc" type="fix" issue="MATH-177" >
         Redesigned the optimization framework for a simpler yet more powerful API.
         Added non-linear conjugate gradient optimizer.



Mime
View raw message