1dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond/* 2dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Licensed to the Apache Software Foundation (ASF) under one or more 3dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * contributor license agreements. See the NOTICE file distributed with 4dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * this work for additional information regarding copyright ownership. 5dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * The ASF licenses this file to You under the Apache License, Version 2.0 6dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * (the "License"); you may not use this file except in compliance with 7dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * the License. You may obtain a copy of the License at 8dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * 9dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * http://www.apache.org/licenses/LICENSE-2.0 10dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * 11dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Unless required by applicable law or agreed to in writing, software 12dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * distributed under the License is distributed on an "AS IS" BASIS, 13dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * See the License for the specific language governing permissions and 15dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * limitations under the License. 16dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 17dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 18dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondpackage org.apache.commons.math.optimization.linear; 19dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 20dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.io.IOException; 21dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.io.ObjectInputStream; 22dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.io.ObjectOutputStream; 23dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.io.Serializable; 24dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.util.ArrayList; 25dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.util.Collection; 26dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.util.HashSet; 27dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.util.List; 28dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport java.util.Set; 29dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 30dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.linear.Array2DRowRealMatrix; 31dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.linear.MatrixUtils; 32dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.linear.RealMatrix; 33dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.linear.RealVector; 34dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.optimization.GoalType; 35dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.optimization.RealPointValuePair; 36dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondimport org.apache.commons.math.util.MathUtils; 37dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 38dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond/** 39dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * A tableau for use in the Simplex method. 40dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * 41dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <p> 42dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Example: 43dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <pre> 44dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * W | Z | x1 | x2 | x- | s1 | s2 | a1 | RHS 45dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * --------------------------------------------------- 46dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * -1 0 0 0 0 0 0 1 0 <= phase 1 objective 47dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * 0 1 -15 -10 0 0 0 0 0 <= phase 2 objective 48dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * 0 0 1 0 0 1 0 0 2 <= constraint 1 49dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * 0 0 0 1 0 0 1 0 3 <= constraint 2 50dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * 0 0 1 1 0 0 0 1 4 <= constraint 3 51dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * </pre> 52dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * W: Phase 1 objective function</br> 53dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Z: Phase 2 objective function</br> 54dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * x1 & x2: Decision variables</br> 55dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * x-: Extra decision variable to allow for negative values</br> 56dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * s1 & s2: Slack/Surplus variables</br> 57dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * a1: Artificial variable</br> 58dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * RHS: Right hand side</br> 59dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * </p> 60dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @version $Revision: 922713 $ $Date: 2010-03-14 02:26:13 +0100 (dim. 14 mars 2010) $ 61dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @since 2.0 62dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 63dee0849a9704d532af0b550146cbafbaa6ee1d19Raymondclass SimplexTableau implements Serializable { 64dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 65dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Column label for negative vars. */ 66dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static final String NEGATIVE_VAR_COLUMN_LABEL = "x-"; 67dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 68dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Serializable version identifier. */ 69dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private static final long serialVersionUID = -1369660067587938365L; 70dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 71dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Linear objective function. */ 72dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private final LinearObjectiveFunction f; 73dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 74dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Linear constraints. */ 75dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private final List<LinearConstraint> constraints; 76dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 77dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Whether to restrict the variables to non-negative values. */ 78dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private final boolean restrictToNonNegative; 79dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 80dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** The variables each column represents */ 81dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private final List<String> columnLabels = new ArrayList<String>(); 82dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 83dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Simple tableau. */ 84dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private transient RealMatrix tableau; 85dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 86dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Number of decision variables. */ 87dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private final int numDecisionVariables; 88dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 89dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Number of slack variables. */ 90dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private final int numSlackVariables; 91dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 92dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Number of artificial variables. */ 93dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private int numArtificialVariables; 94dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 95dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Amount of error to accept in floating point comparisons. */ 96dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private final double epsilon; 97dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 98dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 99dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Build a tableau for a linear problem. 100dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param f linear objective function 101dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param constraints linear constraints 102dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param goalType type of optimization goal: either {@link GoalType#MAXIMIZE} 103dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * or {@link GoalType#MINIMIZE} 104dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param restrictToNonNegative whether to restrict the variables to non-negative values 105dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param epsilon amount of error to accept in floating point comparisons 106dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 107dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond SimplexTableau(final LinearObjectiveFunction f, 108dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final Collection<LinearConstraint> constraints, 109dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final GoalType goalType, final boolean restrictToNonNegative, 110dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final double epsilon) { 111dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.f = f; 112dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.constraints = normalizeConstraints(constraints); 113dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.restrictToNonNegative = restrictToNonNegative; 114dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.epsilon = epsilon; 115dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.numDecisionVariables = f.getCoefficients().getDimension() + 116dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond (restrictToNonNegative ? 0 : 1); 117dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.numSlackVariables = getConstraintTypeCounts(Relationship.LEQ) + 118dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond getConstraintTypeCounts(Relationship.GEQ); 119dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.numArtificialVariables = getConstraintTypeCounts(Relationship.EQ) + 120dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond getConstraintTypeCounts(Relationship.GEQ); 121dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.tableau = createTableau(goalType == GoalType.MAXIMIZE); 122dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond initializeColumnLabels(); 123dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 124dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 125dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 126dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Initialize the labels for the columns. 127dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 128dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected void initializeColumnLabels() { 129dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (getNumObjectiveFunctions() == 2) { 130dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnLabels.add("W"); 131dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 132dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnLabels.add("Z"); 133dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = 0; i < getOriginalNumDecisionVariables(); i++) { 134dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnLabels.add("x" + i); 135dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 136dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (!restrictToNonNegative) { 137dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnLabels.add(NEGATIVE_VAR_COLUMN_LABEL); 138dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 139dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = 0; i < getNumSlackVariables(); i++) { 140dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnLabels.add("s" + i); 141dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 142dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = 0; i < getNumArtificialVariables(); i++) { 143dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnLabels.add("a" + i); 144dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 145dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnLabels.add("RHS"); 146dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 147dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 148dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 149dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Create the tableau by itself. 150dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param maximize if true, goal is to maximize the objective function 151dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return created tableau 152dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 153dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected RealMatrix createTableau(final boolean maximize) { 154dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 155dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // create a matrix of the correct size 156dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int width = numDecisionVariables + numSlackVariables + 157dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond numArtificialVariables + getNumObjectiveFunctions() + 1; // + 1 is for RHS 158dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int height = constraints.size() + getNumObjectiveFunctions(); 159dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond Array2DRowRealMatrix matrix = new Array2DRowRealMatrix(height, width); 160dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 161dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // initialize the objective function rows 162dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (getNumObjectiveFunctions() == 2) { 163dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setEntry(0, 0, -1); 164dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 165dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int zIndex = (getNumObjectiveFunctions() == 1) ? 0 : 1; 166dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setEntry(zIndex, zIndex, maximize ? 1 : -1); 167dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond RealVector objectiveCoefficients = 168dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond maximize ? f.getCoefficients().mapMultiply(-1) : f.getCoefficients(); 169dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond copyArray(objectiveCoefficients.getData(), matrix.getDataRef()[zIndex]); 170dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setEntry(zIndex, width - 1, 171dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond maximize ? f.getConstantTerm() : -1 * f.getConstantTerm()); 172dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 173dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (!restrictToNonNegative) { 174dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setEntry(zIndex, getSlackVariableOffset() - 1, 175dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond getInvertedCoeffiecientSum(objectiveCoefficients)); 176dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 177dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 178dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // initialize the constraint rows 179dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int slackVar = 0; 180dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int artificialVar = 0; 181dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = 0; i < constraints.size(); i++) { 182dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond LinearConstraint constraint = constraints.get(i); 183dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int row = getNumObjectiveFunctions() + i; 184dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 185dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // decision variable coefficients 186dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond copyArray(constraint.getCoefficients().getData(), matrix.getDataRef()[row]); 187dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 188dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // x- 189dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (!restrictToNonNegative) { 190dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setEntry(row, getSlackVariableOffset() - 1, 191dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond getInvertedCoeffiecientSum(constraint.getCoefficients())); 192dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 193dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 194dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // RHS 195dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setEntry(row, width - 1, constraint.getValue()); 196dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 197dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // slack variables 198dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (constraint.getRelationship() == Relationship.LEQ) { 199dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setEntry(row, getSlackVariableOffset() + slackVar++, 1); // slack 200dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } else if (constraint.getRelationship() == Relationship.GEQ) { 201dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setEntry(row, getSlackVariableOffset() + slackVar++, -1); // excess 202dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 203dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 204dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // artificial variables 205dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if ((constraint.getRelationship() == Relationship.EQ) || 206dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond (constraint.getRelationship() == Relationship.GEQ)) { 207dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setEntry(0, getArtificialVariableOffset() + artificialVar, 1); 208dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setEntry(row, getArtificialVariableOffset() + artificialVar++, 1); 209dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix.setRowVector(0, matrix.getRowVector(0).subtract(matrix.getRowVector(row))); 210dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 211dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 212dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 213dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return matrix; 214dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 215dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 216dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 217dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get new versions of the constraints which have positive right hand sides. 218dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param originalConstraints original (not normalized) constraints 219dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return new versions of the constraints 220dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 221dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public List<LinearConstraint> normalizeConstraints(Collection<LinearConstraint> originalConstraints) { 222dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond List<LinearConstraint> normalized = new ArrayList<LinearConstraint>(); 223dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (LinearConstraint constraint : originalConstraints) { 224dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond normalized.add(normalize(constraint)); 225dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 226dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return normalized; 227dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 228dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 229dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 230dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get a new equation equivalent to this one with a positive right hand side. 231dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param constraint reference constraint 232dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return new equation 233dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 234dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private LinearConstraint normalize(final LinearConstraint constraint) { 235dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (constraint.getValue() < 0) { 236dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return new LinearConstraint(constraint.getCoefficients().mapMultiply(-1), 237dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond constraint.getRelationship().oppositeRelationship(), 238dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond -1 * constraint.getValue()); 239dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 240dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return new LinearConstraint(constraint.getCoefficients(), 241dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond constraint.getRelationship(), constraint.getValue()); 242dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 243dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 244dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 245dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the number of objective functions in this tableau. 246dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return 2 for Phase 1. 1 for Phase 2. 247dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 248dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final int getNumObjectiveFunctions() { 249dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return this.numArtificialVariables > 0 ? 2 : 1; 250dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 251dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 252dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 253dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get a count of constraints corresponding to a specified relationship. 254dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param relationship relationship to count 255dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return number of constraint with the specified relationship 256dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 257dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private int getConstraintTypeCounts(final Relationship relationship) { 258dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int count = 0; 259dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (final LinearConstraint constraint : constraints) { 260dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (constraint.getRelationship() == relationship) { 261dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond ++count; 262dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 263dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 264dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return count; 265dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 266dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 267dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 268dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the -1 times the sum of all coefficients in the given array. 269dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param coefficients coefficients to sum 270dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return the -1 times the sum of all coefficients in the given array. 271dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 272dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected static double getInvertedCoeffiecientSum(final RealVector coefficients) { 273dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond double sum = 0; 274dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (double coefficient : coefficients.getData()) { 275dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond sum -= coefficient; 276dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 277dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return sum; 278dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 279dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 280dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 281dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Checks whether the given column is basic. 282dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param col index of the column to check 283dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return the row that the variable is basic in. null if the column is not basic 284dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 285dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected Integer getBasicRow(final int col) { 286dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond Integer row = null; 287dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = 0; i < getHeight(); i++) { 288dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (MathUtils.equals(getEntry(i, col), 1.0, epsilon) && (row == null)) { 289dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond row = i; 290dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } else if (!MathUtils.equals(getEntry(i, col), 0.0, epsilon)) { 291dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return null; 292dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 293dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 294dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return row; 295dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 296dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 297dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 298dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Removes the phase 1 objective function, positive cost non-artificial variables, 299dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * and the non-basic artificial variables from this tableau. 300dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 301dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected void dropPhase1Objective() { 302dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (getNumObjectiveFunctions() == 1) { 303dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return; 304dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 305dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 306dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond List<Integer> columnsToDrop = new ArrayList<Integer>(); 307dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnsToDrop.add(0); 308dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 309dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // positive cost non-artificial variables 310dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = getNumObjectiveFunctions(); i < getArtificialVariableOffset(); i++) { 311dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (MathUtils.compareTo(tableau.getEntry(0, i), 0, epsilon) > 0) { 312dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnsToDrop.add(i); 313dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 314dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 315dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 316dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // non-basic artificial variables 317dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = 0; i < getNumArtificialVariables(); i++) { 318dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int col = i + getArtificialVariableOffset(); 319dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (getBasicRow(col) == null) { 320dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnsToDrop.add(col); 321dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 322dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 323dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 324dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond double[][] matrix = new double[getHeight() - 1][getWidth() - columnsToDrop.size()]; 325dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = 1; i < getHeight(); i++) { 326dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int col = 0; 327dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int j = 0; j < getWidth(); j++) { 328dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (!columnsToDrop.contains(j)) { 329dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond matrix[i - 1][col++] = tableau.getEntry(i, j); 330dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 331dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 332dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 333dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 334dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = columnsToDrop.size() - 1; i >= 0; i--) { 335dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond columnLabels.remove((int) columnsToDrop.get(i)); 336dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 337dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 338dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.tableau = new Array2DRowRealMatrix(matrix); 339dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond this.numArtificialVariables = 0; 340dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 341dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 342dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 343dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param src the source array 344dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param dest the destination array 345dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 346dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private void copyArray(final double[] src, final double[] dest) { 347dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond System.arraycopy(src, 0, dest, getNumObjectiveFunctions(), src.length); 348dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 349dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 350dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 351dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Returns whether the problem is at an optimal state. 352dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return whether the model has been solved 353dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 354dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond boolean isOptimal() { 355dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = getNumObjectiveFunctions(); i < getWidth() - 1; i++) { 356dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (MathUtils.compareTo(tableau.getEntry(0, i), 0, epsilon) < 0) { 357dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return false; 358dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 359dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 360dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return true; 361dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 362dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 363dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 364dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the current solution. 365dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * 366dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return current solution 367dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 368dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected RealPointValuePair getSolution() { 369dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int negativeVarColumn = columnLabels.indexOf(NEGATIVE_VAR_COLUMN_LABEL); 370dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond Integer negativeVarBasicRow = negativeVarColumn > 0 ? getBasicRow(negativeVarColumn) : null; 371dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond double mostNegative = negativeVarBasicRow == null ? 0 : getEntry(negativeVarBasicRow, getRhsOffset()); 372dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 373dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond Set<Integer> basicRows = new HashSet<Integer>(); 374dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond double[] coefficients = new double[getOriginalNumDecisionVariables()]; 375dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int i = 0; i < coefficients.length; i++) { 376dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond int colIndex = columnLabels.indexOf("x" + i); 377dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (colIndex < 0) { 378dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond coefficients[i] = 0; 379dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond continue; 380dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 381dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond Integer basicRow = getBasicRow(colIndex); 382dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (basicRows.contains(basicRow)) { 383dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // if multiple variables can take a given value 384dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond // then we choose the first and set the rest equal to 0 385dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond coefficients[i] = 0; 386dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } else { 387dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond basicRows.add(basicRow); 388dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond coefficients[i] = 389dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond (basicRow == null ? 0 : getEntry(basicRow, getRhsOffset())) - 390dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond (restrictToNonNegative ? 0 : mostNegative); 391dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 392dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 393dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return new RealPointValuePair(coefficients, f.getValue(coefficients)); 394dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 395dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 396dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 397dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Subtracts a multiple of one row from another. 398dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <p> 399dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * After application of this operation, the following will hold: 400dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * minuendRow = minuendRow - multiple * subtrahendRow 401dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * </p> 402dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param dividendRow index of the row 403dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param divisor value of the divisor 404dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 405dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected void divideRow(final int dividendRow, final double divisor) { 406dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond for (int j = 0; j < getWidth(); j++) { 407dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond tableau.setEntry(dividendRow, j, tableau.getEntry(dividendRow, j) / divisor); 408dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 409dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 410dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 411dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 412dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Subtracts a multiple of one row from another. 413dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <p> 414dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * After application of this operation, the following will hold: 415dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * minuendRow = minuendRow - multiple * subtrahendRow 416dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * </p> 417dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param minuendRow row index 418dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param subtrahendRow row index 419dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param multiple multiplication factor 420dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 421dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected void subtractRow(final int minuendRow, final int subtrahendRow, 422dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final double multiple) { 423dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond tableau.setRowVector(minuendRow, tableau.getRowVector(minuendRow) 424dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond .subtract(tableau.getRowVector(subtrahendRow).mapMultiply(multiple))); 425dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 426dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 427dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 428dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the width of the tableau. 429dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return width of the tableau 430dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 431dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final int getWidth() { 432dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return tableau.getColumnDimension(); 433dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 434dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 435dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 436dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the height of the tableau. 437dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return height of the tableau 438dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 439dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final int getHeight() { 440dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return tableau.getRowDimension(); 441dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 442dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 443dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Get an entry of the tableau. 444dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param row row index 445dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param column column index 446dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return entry at (row, column) 447dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 448dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final double getEntry(final int row, final int column) { 449dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return tableau.getEntry(row, column); 450dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 451dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 452dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Set an entry of the tableau. 453dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param row row index 454dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param column column index 455dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param value for the entry 456dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 457dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final void setEntry(final int row, final int column, 458dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond final double value) { 459dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond tableau.setEntry(row, column, value); 460dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 461dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 462dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 463dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the offset of the first slack variable. 464dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return offset of the first slack variable 465dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 466dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final int getSlackVariableOffset() { 467dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return getNumObjectiveFunctions() + numDecisionVariables; 468dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 469dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 470dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 471dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the offset of the first artificial variable. 472dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return offset of the first artificial variable 473dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 474dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final int getArtificialVariableOffset() { 475dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return getNumObjectiveFunctions() + numDecisionVariables + numSlackVariables; 476dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 477dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 478dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 479dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the offset of the right hand side. 480dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return offset of the right hand side 481dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 482dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final int getRhsOffset() { 483dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return getWidth() - 1; 484dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 485dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 486dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 487dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the number of decision variables. 488dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * <p> 489dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * If variables are not restricted to positive values, this will include 1 490dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * extra decision variable to represent the absolute value of the most 491dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * negative variable. 492dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * </p> 493dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return number of decision variables 494dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @see #getOriginalNumDecisionVariables() 495dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 496dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final int getNumDecisionVariables() { 497dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return numDecisionVariables; 498dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 499dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 500dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 501dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the original number of decision variables. 502dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return original number of decision variables 503dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @see #getNumDecisionVariables() 504dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 505dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final int getOriginalNumDecisionVariables() { 506dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return f.getCoefficients().getDimension(); 507dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 508dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 509dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 510dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the number of slack variables. 511dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return number of slack variables 512dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 513dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final int getNumSlackVariables() { 514dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return numSlackVariables; 515dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 516dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 517dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 518dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the number of artificial variables. 519dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return number of artificial variables 520dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 521dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final int getNumArtificialVariables() { 522dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return numArtificialVariables; 523dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 524dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 525dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** 526dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * Get the tableau data. 527dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @return tableau data 528dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 529dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond protected final double[][] getData() { 530dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return tableau.getData(); 531dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 532dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 533dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** {@inheritDoc} */ 534dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond @Override 535dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public boolean equals(Object other) { 536dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 537dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (this == other) { 538dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return true; 539dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 540dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 541dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond if (other instanceof SimplexTableau) { 542dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond SimplexTableau rhs = (SimplexTableau) other; 543dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return (restrictToNonNegative == rhs.restrictToNonNegative) && 544dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond (numDecisionVariables == rhs.numDecisionVariables) && 545dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond (numSlackVariables == rhs.numSlackVariables) && 546dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond (numArtificialVariables == rhs.numArtificialVariables) && 547dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond (epsilon == rhs.epsilon) && 548dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond f.equals(rhs.f) && 549dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond constraints.equals(rhs.constraints) && 550dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond tableau.equals(rhs.tableau); 551dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 552dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return false; 553dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 554dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 555dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** {@inheritDoc} */ 556dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond @Override 557dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond public int hashCode() { 558dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond return Boolean.valueOf(restrictToNonNegative).hashCode() ^ 559dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond numDecisionVariables ^ 560dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond numSlackVariables ^ 561dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond numArtificialVariables ^ 562dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond Double.valueOf(epsilon).hashCode() ^ 563dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond f.hashCode() ^ 564dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond constraints.hashCode() ^ 565dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond tableau.hashCode(); 566dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 567dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 568dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Serialize the instance. 569dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param oos stream where object should be written 570dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @throws IOException if object cannot be written to stream 571dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 572dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private void writeObject(ObjectOutputStream oos) 573dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throws IOException { 574dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond oos.defaultWriteObject(); 575dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond MatrixUtils.serializeRealMatrix(tableau, oos); 576dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 577dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 578dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond /** Deserialize the instance. 579dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @param ois stream from which the object should be read 580dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @throws ClassNotFoundException if a class in the stream cannot be found 581dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond * @throws IOException if object cannot be read from the stream 582dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond */ 583dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond private void readObject(ObjectInputStream ois) 584dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond throws ClassNotFoundException, IOException { 585dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond ois.defaultReadObject(); 586dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond MatrixUtils.deserializeRealMatrix(this, "tableau", ois); 587dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond } 588dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond 589dee0849a9704d532af0b550146cbafbaa6ee1d19Raymond} 590