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