Author: luc
Date: Fri Aug 21 23:07:42 2009
New Revision: 806753
URL: http://svn.apache.org/viewvc?rev=806753&view=rev
Log:
fixed an error leading the simplex solver to compute the right solution but
return another one
JIRA: MATH-286
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
commons/proper/math/trunk/src/site/xdoc/changes.xml
commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java?rev=806753&r1=806752&r2=806753&view=diff
==============================================================================
---
commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
(original)
+++
commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
Fri Aug 21 23:07:42 2009
@@ -270,8 +270,27 @@
* @return the row that the variable is basic in. null if the column is
not basic
*/
private Integer getBasicRow(final int col) {
+ return getBasicRow(col, true);
+ }
+
+ /**
+ * 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 getBasicRowForSolution(final int col) {
+ return getBasicRow(col, false);
+ }
+
+ /**
+ * 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, boolean ignoreObjectiveRows) {
Integer row = null;
- for (int i = getNumObjectiveFunctions(); i < getHeight(); i++) {
+ int start = ignoreObjectiveRows ? getNumObjectiveFunctions() : 0;
+ for (int i = start; i < getHeight(); i++) {
if (MathUtils.equals(getEntry(i, col), 1.0, epsilon) && (row ==
null)) {
row = i;
} else if (!MathUtils.equals(getEntry(i, col), 0.0, epsilon)) {
@@ -318,24 +337,23 @@
* @return current solution
*/
protected RealPointValuePair getSolution() {
- double[] coefficients = new double[getOriginalNumDecisionVariables()];
- Integer basicRow =
- getBasicRow(getNumObjectiveFunctions() +
getOriginalNumDecisionVariables());
- double mostNegative = basicRow == null ? 0 : getEntry(basicRow,
getRhsOffset());
- Set<Integer> basicRows = new HashSet<Integer>();
- for (int i = 0; i < coefficients.length; i++) {
- basicRow = getBasicRow(getNumObjectiveFunctions() + i);
- if (basicRows.contains(basicRow)) {
- // if multiple variables can take a given value
- // then we choose the first and set the rest equal to 0
- coefficients[i] = 0;
- } else {
- basicRows.add(basicRow);
- coefficients[i] =
- (basicRow == null ? 0 : getEntry(basicRow,
getRhsOffset())) -
- (restrictToNonNegative ? 0 : mostNegative);
- }
- }
+ double[] coefficients = new double[getOriginalNumDecisionVariables()];
+ Integer negativeVarBasicRow =
getBasicRowForSolution(getNegativeDecisionVariableOffset());
+ double mostNegative = negativeVarBasicRow == null ? 0 :
getEntry(negativeVarBasicRow, getRhsOffset());
+ Set<Integer> basicRows = new HashSet<Integer>();
+ for (int i = 0; i < coefficients.length; i++) {
+ Integer basicRow = getBasicRowForSolution(getNumObjectiveFunctions()
+ i);
+ if (basicRows.contains(basicRow)) {
+ // if multiple variables can take a given value
+ // then we choose the first and set the rest equal to 0
+ coefficients[i] = 0;
+ } else {
+ basicRows.add(basicRow);
+ coefficients[i] =
+ (basicRow == null ? 0 : getEntry(basicRow, getRhsOffset())) -
+ (restrictToNonNegative ? 0 : mostNegative);
+ }
+ }
return new RealPointValuePair(coefficients, f.getValue(coefficients));
}
@@ -430,6 +448,15 @@
protected final int getRhsOffset() {
return getWidth() - 1;
}
+
+ /**
+ * Returns the offset of the extra decision variable added when there is a
+ * negative decision variable in the original problem.
+ * @return the offset of x-
+ */
+ protected final int getNegativeDecisionVariableOffset() {
+ return getNumObjectiveFunctions() + getOriginalNumDecisionVariables();
+ }
/**
* Get the number of decision variables.
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=806753&r1=806752&r2=806753&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Fri Aug 21 23:07:42 2009
@@ -39,6 +39,10 @@
</properties>
<body>
<release version="2.1" date="TBD" description="TBD">
+ <action dev="luc" type="fix" issue="MATH-286" due-to="Benjamin McCann">
+ Fixed an error leading the simplex solver to compute the right solution
+ but return another one
+ </action>
<action dev="luc" type="fix" issue="MATH-283" due-to="Michael Nischt">
Prevent infinite loops in multi-directional direct optimization method
when
the start point is exactly at the optimal point
Modified:
commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java?rev=806753&r1=806752&r2=806753&view=diff
==============================================================================
---
commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
(original)
+++
commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
Fri Aug 21 23:07:42 2009
@@ -46,8 +46,18 @@
assertEquals(1.0, solution.getPoint()[1], .0000001);
assertEquals(1.0, solution.getPoint()[2], .0000001);
assertEquals(3.0, solution.getValue(), .0000001);
- }
+ }
+
+ @Test
+ public void testMath286() throws OptimizationException {
+ LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {
0.2, 0.3 }, 0 );
+ Collection<LinearConstraint> constraints = new
ArrayList<LinearConstraint>();
+ constraints.add(new LinearConstraint(new double[] { 1, 1 },
Relationship.EQ, 23.0));
+ RealPointValuePair solution = new SimplexSolver().optimize(f,
constraints, GoalType.MAXIMIZE, true);
+ assertEquals(6.9, solution.getValue(), .0000001);
+ }
+
@Test
public void testSimplexSolver() throws OptimizationException {
LinearObjectiveFunction f =
