You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2009/09/10 10:20:28 UTC
svn commit: r813301 - in /commons/proper/math/trunk/src:
main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
site/xdoc/changes.xml
test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
Author: luc
Date: Thu Sep 10 08:20:28 2009
New Revision: 813301
URL: http://svn.apache.org/viewvc?rev=813301&view=rev
Log:
Fixed a OutOfBoundException in simplex solver when some constraints are tight
JIRA: MATH-293
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=813301&r1=813300&r2=813301&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 Thu Sep 10 08:20:28 2009
@@ -74,6 +74,9 @@
/** Whether to restrict the variables to non-negative values. */
private final boolean restrictToNonNegative;
+ /** The variables each column represents */
+ private final List<String> columnLabels = new ArrayList<String>();
+
/** Simple tableau. */
private transient RealMatrix tableau;
@@ -113,6 +116,27 @@
this.numArtificialVariables = getConstraintTypeCounts(Relationship.EQ) +
getConstraintTypeCounts(Relationship.GEQ);
this.tableau = createTableau(goalType == GoalType.MAXIMIZE);
+ initializeColumnLabels();
+ }
+
+ protected void initializeColumnLabels() {
+ if (getNumObjectiveFunctions() == 2) {
+ columnLabels.add("W");
+ }
+ columnLabels.add("Z");
+ for (int i = 0; i < getOriginalNumDecisionVariables(); i++) {
+ columnLabels.add("x" + i);
+ }
+ if (!restrictToNonNegative) {
+ columnLabels.add("x-");
+ }
+ for (int i = 0; i < getNumSlackVariables(); i++) {
+ columnLabels.add("s" + i);
+ }
+ for (int i = 0; i < getNumArtificialVariables(); i++) {
+ columnLabels.add("a" + i);
+ }
+ columnLabels.add("RHS");
}
/**
@@ -301,6 +325,10 @@
}
}
+ for (int i = columnsToDrop.size() - 1; i >= 0; i--) {
+ columnLabels.remove((int) columnsToDrop.get(i));
+ }
+
this.tableau = new Array2DRowRealMatrix(matrix);
this.numArtificialVariables = 0;
}
@@ -332,12 +360,19 @@
* @return current solution
*/
protected RealPointValuePair getSolution() {
- double[] coefficients = new double[getOriginalNumDecisionVariables()];
- Integer negativeVarBasicRow = getBasicRow(getNegativeDecisionVariableOffset());
+ int negativeVarColumn = columnLabels.indexOf("x-");
+ Integer negativeVarBasicRow = negativeVarColumn > 0 ? getBasicRow(negativeVarColumn) : null;
double mostNegative = negativeVarBasicRow == null ? 0 : getEntry(negativeVarBasicRow, getRhsOffset());
+
Set<Integer> basicRows = new HashSet<Integer>();
+ double[] coefficients = new double[getOriginalNumDecisionVariables()];
for (int i = 0; i < coefficients.length; i++) {
- Integer basicRow = getBasicRow(getNumObjectiveFunctions() + i);
+ int colIndex = columnLabels.indexOf("x" + i);
+ if (colIndex < 0) {
+ coefficients[i] = 0;
+ continue;
+ }
+ Integer basicRow = getBasicRow(colIndex);
if (basicRows.contains(basicRow)) {
// if multiple variables can take a given value
// then we choose the first and set the rest equal to 0
@@ -349,7 +384,7 @@
(restrictToNonNegative ? 0 : mostNegative);
}
}
- return new RealPointValuePair(coefficients, f.getValue(coefficients));
+ return new RealPointValuePair(coefficients, f.getValue(coefficients));
}
/**
@@ -443,15 +478,6 @@
}
/**
- * 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.
* <p>
* If variables are not restricted to positive values, this will include 1
@@ -471,7 +497,7 @@
* @see #getNumDecisionVariables()
*/
protected final int getOriginalNumDecisionVariables() {
- return restrictToNonNegative ? numDecisionVariables : numDecisionVariables - 1;
+ return f.getCoefficients().getDimension();
}
/**
@@ -562,4 +588,5 @@
ois.defaultReadObject();
MatrixUtils.deserializeRealMatrix(this, "tableau", ois);
}
+
}
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=813301&r1=813300&r2=813301&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Thu Sep 10 08:20:28 2009
@@ -39,6 +39,9 @@
</properties>
<body>
<release version="2.1" date="TBD" description="TBD">
+ <action dev="luc" type="fix" issue="MATH-293" due-to="Benjamin McCann">
+ Fixed a OutOfBoundException in simplex solver when some constraints are tight.
+ </action>
<action dev="luc" type="fix" issue="MATH-291" due-to="Sebb">
Fixed misleading number formats in error messages for adaptive
stepsize integrators.
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=813301&r1=813300&r2=813301&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 Thu Sep 10 08:20:28 2009
@@ -117,6 +117,43 @@
}
@Test
+ public void testMath293() throws OptimizationException {
+ LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
+ Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
+ constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
+ constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
+ constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
+ constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
+ constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
+
+ SimplexSolver solver = new SimplexSolver();
+ RealPointValuePair solution1 = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
+
+ Assert.assertEquals(15.7143, solution1.getPoint()[0], .0001);
+ Assert.assertEquals(0.0, solution1.getPoint()[1], .0001);
+ Assert.assertEquals(14.2857, solution1.getPoint()[2], .0001);
+ Assert.assertEquals(0.0, solution1.getPoint()[3], .0001);
+ Assert.assertEquals(0.0, solution1.getPoint()[4], .0001);
+ Assert.assertEquals(30.0, solution1.getPoint()[5], .0001);
+ Assert.assertEquals(40.57143, solution1.getValue(), .0001);
+
+ double valA = 0.8 * solution1.getPoint()[0] + 0.2 * solution1.getPoint()[1];
+ double valB = 0.7 * solution1.getPoint()[2] + 0.3 * solution1.getPoint()[3];
+ double valC = 0.4 * solution1.getPoint()[4] + 0.6 * solution1.getPoint()[5];
+
+ f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
+ constraints = new ArrayList<LinearConstraint>();
+ constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
+ constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
+ constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
+ constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
+ constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
+
+ RealPointValuePair solution2 = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
+ Assert.assertEquals(40.57143, solution2.getValue(), .0001);
+ }
+
+ @Test
public void testSimplexSolver() throws OptimizationException {
LinearObjectiveFunction f =
new LinearObjectiveFunction(new double[] { 15, 10 }, 7);