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/09 10:48:04 UTC
svn commit: r812831 - in /commons/proper/math/trunk/src:
main/java/org/apache/commons/math/optimization/linear/
test/java/org/apache/commons/math/optimization/linear/
Author: luc
Date: Wed Sep 9 08:48:03 2009
New Revision: 812831
URL: http://svn.apache.org/viewvc?rev=812831&view=rev
Log:
applied Benjamin's patch from 2009-09-08
warning: I had to update the expected matrix in SimplexTableauTest.testdiscardArtificialVariables
JIRA: MATH-286
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexTableauTest.java
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexSolver.java?rev=812831&r1=812830&r2=812831&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexSolver.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexSolver.java Wed Sep 9 08:48:03 2009
@@ -174,7 +174,7 @@
new SimplexTableau(function, linearConstraints, goal, nonNegative, epsilon);
solvePhase1(tableau);
- tableau.discardArtificialVariables();
+ tableau.dropPhase1Objective();
while (!tableau.isOptimal()) {
doIteration(tableau);
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=812831&r1=812830&r2=812831&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 Wed Sep 9 08:48:03 2009
@@ -112,8 +112,7 @@
getConstraintTypeCounts(Relationship.GEQ);
this.numArtificialVariables = getConstraintTypeCounts(Relationship.EQ) +
getConstraintTypeCounts(Relationship.GEQ);
- this.tableau = new Array2DRowRealMatrix(createTableau(goalType == GoalType.MAXIMIZE));
- initialize();
+ this.tableau = createTableau(goalType == GoalType.MAXIMIZE);
}
/**
@@ -121,29 +120,29 @@
* @param maximize if true, goal is to maximize the objective function
* @return created tableau
*/
- protected double[][] createTableau(final boolean maximize) {
+ protected RealMatrix createTableau(final boolean maximize) {
// create a matrix of the correct size
int width = numDecisionVariables + numSlackVariables +
numArtificialVariables + getNumObjectiveFunctions() + 1; // + 1 is for RHS
int height = constraints.size() + getNumObjectiveFunctions();
- double[][] matrix = new double[height][width];
+ Array2DRowRealMatrix matrix = new Array2DRowRealMatrix(height, width);
// initialize the objective function rows
if (getNumObjectiveFunctions() == 2) {
- matrix[0][0] = -1;
+ matrix.setEntry(0, 0, -1);
}
int zIndex = (getNumObjectiveFunctions() == 1) ? 0 : 1;
- matrix[zIndex][zIndex] = maximize ? 1 : -1;
+ matrix.setEntry(zIndex, zIndex, maximize ? 1 : -1);
RealVector objectiveCoefficients =
maximize ? f.getCoefficients().mapMultiply(-1) : f.getCoefficients();
- copyArray(objectiveCoefficients.getData(), matrix[zIndex]);
- matrix[zIndex][width - 1] =
- maximize ? f.getConstantTerm() : -1 * f.getConstantTerm();
+ copyArray(objectiveCoefficients.getData(), matrix.getDataRef()[zIndex]);
+ matrix.setEntry(zIndex, width - 1,
+ maximize ? f.getConstantTerm() : -1 * f.getConstantTerm());
if (!restrictToNonNegative) {
- matrix[zIndex][getSlackVariableOffset() - 1] =
- getInvertedCoeffiecientSum(objectiveCoefficients);
+ matrix.setEntry(zIndex, getSlackVariableOffset() - 1,
+ getInvertedCoeffiecientSum(objectiveCoefficients));
}
// initialize the constraint rows
@@ -154,34 +153,34 @@
int row = getNumObjectiveFunctions() + i;
// decision variable coefficients
- copyArray(constraint.getCoefficients().getData(), matrix[row]);
+ copyArray(constraint.getCoefficients().getData(), matrix.getDataRef()[row]);
// x-
if (!restrictToNonNegative) {
- matrix[row][getSlackVariableOffset() - 1] =
- getInvertedCoeffiecientSum(constraint.getCoefficients());
+ matrix.setEntry(row, getSlackVariableOffset() - 1,
+ getInvertedCoeffiecientSum(constraint.getCoefficients()));
}
// RHS
- matrix[row][width - 1] = constraint.getValue();
+ matrix.setEntry(row, width - 1, constraint.getValue());
// slack variables
if (constraint.getRelationship() == Relationship.LEQ) {
- matrix[row][getSlackVariableOffset() + slackVar++] = 1; // slack
+ matrix.setEntry(row, getSlackVariableOffset() + slackVar++, 1); // slack
} else if (constraint.getRelationship() == Relationship.GEQ) {
- matrix[row][getSlackVariableOffset() + slackVar++] = -1; // excess
+ matrix.setEntry(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;
+ matrix.setEntry(0, getArtificialVariableOffset() + artificialVar, 1);
+ matrix.setEntry(row, getArtificialVariableOffset() + artificialVar++, 1);
+ matrix.setRowVector(0, matrix.getRowVector(0).subtract(matrix.getRowVector(row)));
}
}
return matrix;
-
}
/**
@@ -236,17 +235,6 @@
}
/**
- * 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.
@@ -264,30 +252,9 @@
* @param col index of the column to check
* @return the row that the variable is basic in. null if the column is not basic
*/
- 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
- * @param ignoreObjectiveRows if true ignore the first rows which correspond
- * to objective functions
- * @return the row that the variable is basic in. null if the column is not basic
- */
- private Integer getBasicRow(final int col, boolean ignoreObjectiveRows) {
+ protected Integer getBasicRow(final int col) {
Integer row = null;
- int start = ignoreObjectiveRows ? getNumObjectiveFunctions() : 0;
- for (int i = start; i < getHeight(); i++) {
+ for (int i = 0; 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)) {
@@ -298,21 +265,42 @@
}
/**
- * Removes the phase 1 objective function and artificial variables from this tableau.
+ * Removes the phase 1 objective function, positive cost non-artificial variables,
+ * and the non-basic artificial variables from this tableau.
*/
- protected void discardArtificialVariables() {
- if (numArtificialVariables == 0) {
+ protected void dropPhase1Objective() {
+ if (getNumObjectiveFunctions() == 1) {
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);
+
+ List<Integer> columnsToDrop = new ArrayList<Integer>();
+ columnsToDrop.add(0);
+
+ // positive cost non-artificial variables
+ for (int i = getNumObjectiveFunctions(); i < getArtificialVariableOffset(); i++) {
+ if (MathUtils.compareTo(tableau.getEntry(0, i), 0, epsilon) > 0) {
+ columnsToDrop.add(i);
+ }
+ }
+
+ // non-basic artificial variables
+ for (int i = 0; i < getNumArtificialVariables(); i++) {
+ int col = i + getArtificialVariableOffset();
+ if (getBasicRow(col) == null) {
+ columnsToDrop.add(col);
+ }
+ }
+
+ double[][] matrix = new double[getHeight() - 1][getWidth() - columnsToDrop.size()];
+ for (int i = 1; i < getHeight(); i++) {
+ int col = 0;
+ for (int j = 0; j < getWidth(); j++) {
+ if (!columnsToDrop.contains(j)) {
+ matrix[i - 1][col++] = tableau.getEntry(i, j);
}
- matrix[i][width - 1] = getEntry(i + 1, getRhsOffset());
+ }
}
+
this.tableau = new Array2DRowRealMatrix(matrix);
this.numArtificialVariables = 0;
}
@@ -345,11 +333,11 @@
*/
protected RealPointValuePair getSolution() {
double[] coefficients = new double[getOriginalNumDecisionVariables()];
- Integer negativeVarBasicRow = getBasicRowForSolution(getNegativeDecisionVariableOffset());
+ Integer negativeVarBasicRow = getBasicRow(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);
+ Integer 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
@@ -391,10 +379,8 @@
*/
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));
- }
+ tableau.setRowVector(minuendRow, tableau.getRowVector(minuendRow)
+ .subtract(tableau.getRowVector(subtrahendRow).mapMultiply(multiple)));
}
/**
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=812831&r1=812830&r2=812831&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 Wed Sep 9 08:48:03 2009
@@ -48,13 +48,17 @@
@Test
public void testMath286() throws OptimizationException {
- LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.2, 0.3 }, 0 );
+ LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.6, 0.4 }, 0 );
Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
- constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.EQ, 23.0));
+ constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 23.0));
+ constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 23.0));
+ constraints.add(new LinearConstraint(new double[] { 1, 0, 0, 0, 0, 0 }, Relationship.GEQ, 10.0));
+ constraints.add(new LinearConstraint(new double[] { 0, 0, 1, 0, 0, 0 }, Relationship.GEQ, 8.0));
+ constraints.add(new LinearConstraint(new double[] { 0, 0, 0, 0, 1, 0 }, Relationship.GEQ, 5.0));
SimplexSolver solver = new SimplexSolver();
RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
- Assert.assertEquals(6.9, solution.getValue(), .0000001);
+ Assert.assertEquals(25.8, solution.getValue(), .0000001);
}
@Test
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexTableauTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexTableauTest.java?rev=812831&r1=812830&r2=812831&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexTableauTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexTableauTest.java Wed Sep 9 08:48:03 2009
@@ -50,12 +50,12 @@
SimplexTableau tableau =
new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false, 1.0e-6);
double[][] expectedTableau = {
- { 1, -15, -10, 25, 0, 0, 0},
- { 0, 1, 0, -1, 1, 0, 2},
- { 0, 0, 1, -1, 0, 1, 3},
- { 0, 1, 1, -2, 0, 0, 4}
+ { 1, -15, -10, 0, 0, 0, 0},
+ { 0, 1, 0, 1, 0, 0, 2},
+ { 0, 0, 1, 0, 1, 0, 3},
+ { 0, 1, 1, 0, 0, 1, 4}
};
- tableau.discardArtificialVariables();
+ tableau.dropPhase1Objective();
assertMatrixEquals(expectedTableau, tableau.getData());
}