Author: luc
Date: Tue Jun 2 19:37:30 2009
New Revision: 781135
URL: http://svn.apache.org/viewvc?rev=781135&view=rev
Log:
Fixed a problem when setting some variables (several variables were set instead
of only one)
JIRA: MATH-272
Modified:
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
commons/proper/math/trunk/src/site/xdoc/changes.xml
commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
Modified:
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=781135&r1=781134&r2=781135&view=diff
==============================================================================
---
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
(original)
+++
commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
Tue Jun 2 19:37:30 2009
@@ -23,7 +23,9 @@
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
+import java.util.HashSet;
import java.util.List;
+import java.util.Set;
import org.apache.commons.math.linear.MatrixUtils;
import org.apache.commons.math.linear.RealMatrix;
@@ -321,39 +323,27 @@
*/
protected RealPointValuePair getSolution() {
double[] coefficients = new double[getOriginalNumDecisionVariables()];
- double mostNegative =
getDecisionVariableValue(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++) {
- coefficients[i] =
- getDecisionVariableValue(i) - (restrictToNonNegative ? 0 :
mostNegative);
+ 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);
+ }
}
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) {
- int col = getNumObjectiveFunctions() + decisionVariable;
- Integer basicRow = getBasicRow(col);
- if (basicRow == null) {
- return 0;
- }
- // if there are multiple variables that can take the value on the RHS
- // then we'll give the first variable that value
- for (int i = getNumObjectiveFunctions(); i < col; i++) {
- if (tableau.getEntry(basicRow, i) == 1) {
- return 0;
- }
- }
- return getEntry(basicRow, getRhsOffset());
- }
-
- /**
* Subtracts a multiple of one row from another.
* <p>
* After application of this operation, the following will hold:
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=781135&r1=781134&r2=781135&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Tue Jun 2 19:37:30 2009
@@ -39,6 +39,10 @@
</properties>
<body>
<release version="2.0" date="TBD" description="TBD">
+ <action dev="luc" type="fix" issue="MATH-272" due-to="Benjamin McCann">
+ Fixed a problem when setting some variables (several variables were set
+ instead of only one)
+ </action>
<action dev="luc" type="add" due-to="Gilles Sadowski">
Added a way to limit the number of functions evaluations in optimizers
(the number of iterations could already be limited)
Modified:
commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
URL:
http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java?rev=781135&r1=781134&r2=781135&view=diff
==============================================================================
---
commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
(original)
+++
commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
Tue Jun 2 19:37:30 2009
@@ -17,19 +17,38 @@
package org.apache.commons.math.optimization.linear;
+import static org.junit.Assert.assertEquals;
+
import java.util.ArrayList;
import java.util.Collection;
-import junit.framework.TestCase;
-
import org.apache.commons.math.linear.RealVector;
import org.apache.commons.math.linear.RealVectorImpl;
import org.apache.commons.math.optimization.GoalType;
import org.apache.commons.math.optimization.OptimizationException;
import org.apache.commons.math.optimization.RealPointValuePair;
+import org.junit.Test;
-public class SimplexSolverTest extends TestCase {
+public class SimplexSolverTest {
+ @Test
+ public void testMath272() throws OptimizationException {
+ LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {
2, 2, 1 }, 0);
+ Collection<LinearConstraint> constraints = new
ArrayList<LinearConstraint>();
+ constraints.add(new LinearConstraint(new double[] { 1, 1, 0 },
Relationship.GEQ, 1));
+ constraints.add(new LinearConstraint(new double[] { 1, 0, 1 },
Relationship.GEQ, 1));
+ constraints.add(new LinearConstraint(new double[] { 0, 1, 0 },
Relationship.GEQ, 1));
+
+ SimplexSolver solver = new SimplexSolver();
+ RealPointValuePair solution = solver.optimize(f, constraints,
GoalType.MINIMIZE, true);
+
+ assertEquals(0.0, solution.getPoint()[0], .0000001);
+ assertEquals(1.0, solution.getPoint()[1], .0000001);
+ assertEquals(1.0, solution.getPoint()[2], .0000001);
+ assertEquals(3.0, solution.getValue(), .0000001);
+ }
+
+ @Test
public void testSimplexSolver() throws OptimizationException {
LinearObjectiveFunction f =
new LinearObjectiveFunction(new double[] { 15, 10 }, 7);
@@ -40,15 +59,16 @@
SimplexSolver solver = new SimplexSolver();
RealPointValuePair solution = solver.optimize(f, constraints,
GoalType.MAXIMIZE, false);
- assertEquals(2.0, solution.getPoint()[0]);
- assertEquals(2.0, solution.getPoint()[1]);
- assertEquals(57.0, solution.getValue());
+ assertEquals(2.0, solution.getPoint()[0], 0.0);
+ assertEquals(2.0, solution.getPoint()[1], 0.0);
+ assertEquals(57.0, solution.getValue(), 0.0);
}
/**
* With no artificial variables needed (no equals and no greater than
* constraints) we can go straight to Phase 2.
*/
+ @Test
public void testModelWithNoArtificialVars() throws OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {
15, 10 }, 0);
Collection<LinearConstraint> constraints = new
ArrayList<LinearConstraint>();
@@ -58,11 +78,12 @@
SimplexSolver solver = new SimplexSolver();
RealPointValuePair solution = solver.optimize(f, constraints,
GoalType.MAXIMIZE, false);
- assertEquals(2.0, solution.getPoint()[0]);
- assertEquals(2.0, solution.getPoint()[1]);
- assertEquals(50.0, solution.getValue());
+ assertEquals(2.0, solution.getPoint()[0], 0.0);
+ assertEquals(2.0, solution.getPoint()[1], 0.0);
+ assertEquals(50.0, solution.getValue(), 0.0);
}
+ @Test
public void testMinimization() throws OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {
-2, 1 }, -5);
Collection<LinearConstraint> constraints = new
ArrayList<LinearConstraint>();
@@ -72,11 +93,12 @@
SimplexSolver solver = new SimplexSolver();
RealPointValuePair solution = solver.optimize(f, constraints,
GoalType.MINIMIZE, false);
- assertEquals(4.0, solution.getPoint()[0]);
- assertEquals(0.0, solution.getPoint()[1]);
- assertEquals(-13.0, solution.getValue());
+ assertEquals(4.0, solution.getPoint()[0], 0.0);
+ assertEquals(0.0, solution.getPoint()[1], 0.0);
+ assertEquals(-13.0, solution.getValue(), 0.0);
}
+ @Test
public void testSolutionWithNegativeDecisionVariable() throws
OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {
-2, 1 }, 0);
Collection<LinearConstraint> constraints = new
ArrayList<LinearConstraint>();
@@ -85,44 +107,33 @@
SimplexSolver solver = new SimplexSolver();
RealPointValuePair solution = solver.optimize(f, constraints,
GoalType.MAXIMIZE, false);
- assertEquals(-2.0, solution.getPoint()[0]);
- assertEquals(8.0, solution.getPoint()[1]);
- assertEquals(12.0, solution.getValue());
+ assertEquals(-2.0, solution.getPoint()[0], 0.0);
+ assertEquals(8.0, solution.getPoint()[1], 0.0);
+ assertEquals(12.0, solution.getValue(), 0.0);
}
- public void testInfeasibleSolution() {
+ @Test(expected = NoFeasibleSolutionException.class)
+ public void testInfeasibleSolution() throws OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {
15 }, 0);
Collection<LinearConstraint> constraints = new
ArrayList<LinearConstraint>();
constraints.add(new LinearConstraint(new double[] { 1 },
Relationship.LEQ, 1));
constraints.add(new LinearConstraint(new double[] { 1 },
Relationship.GEQ, 3));
SimplexSolver solver = new SimplexSolver();
- try {
- solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
- fail("An exception should have been thrown.");
- } catch (NoFeasibleSolutionException e) {
- // expected;
- } catch (OptimizationException e) {
- fail("wrong exception caught");
- }
+ solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
}
- public void testUnboundedSolution() {
+ @Test(expected = UnboundedSolutionException.class)
+ public void testUnboundedSolution() throws OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {
15, 10 }, 0);
Collection<LinearConstraint> constraints = new
ArrayList<LinearConstraint>();
constraints.add(new LinearConstraint(new double[] { 1, 0 },
Relationship.EQ, 2));
SimplexSolver solver = new SimplexSolver();
- try {
- solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
- fail("An exception should have been thrown.");
- } catch (UnboundedSolutionException e) {
- // expected;
- } catch (OptimizationException e) {
- fail("wrong exception caught");
- }
+ solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
}
+ @Test
public void testRestrictVariablesToNonNegative() throws
OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {
409, 523, 70, 204, 339 }, 0);
Collection<LinearConstraint> constraints = new
ArrayList<LinearConstraint>();
@@ -142,6 +153,7 @@
assertEquals(1438556.7491409, solution.getValue(), .0000001);
}
+ @Test
public void testEpsilon() throws OptimizationException {
LinearObjectiveFunction f =
new LinearObjectiveFunction(new double[] { 10, 5, 1 }, 0);
@@ -152,12 +164,13 @@
SimplexSolver solver = new SimplexSolver();
RealPointValuePair solution = solver.optimize(f, constraints,
GoalType.MAXIMIZE, false);
- assertEquals(1.0, solution.getPoint()[0]);
- assertEquals(1.0, solution.getPoint()[1]);
- assertEquals(0.0, solution.getPoint()[2]);
- assertEquals(15.0, solution.getValue());
+ assertEquals(1.0, solution.getPoint()[0], 0.0);
+ assertEquals(1.0, solution.getPoint()[1], 0.0);
+ assertEquals(0.0, solution.getPoint()[2], 0.0);
+ assertEquals(15.0, solution.getValue(), 0.0);
}
+ @Test
public void testTrivialModel() throws OptimizationException {
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {
1, 1 }, 0);
Collection<LinearConstraint> constraints = new
ArrayList<LinearConstraint>();
@@ -168,6 +181,7 @@
assertEquals(0, solution.getValue(), .0000001);
}
+ @Test
public void testLargeModel() throws OptimizationException {
double[] objective = new double[] {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
