View Javadoc
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   &lt;= phase 1 objective
47   *   0    1   -15   -10    0     0     0     0     0   &lt;= phase 2 objective
48   *   0    0    1     0     0     1     0     0     2   &lt;= constraint 1
49   *   0    0    0     1     0     0     1     0     3   &lt;= constraint 2
50   *   0    0    1     1     0     0     0     1     4   &lt;= constraint 3
51   * </pre>
52   * W: Phase 1 objective function</br>
53   * Z: Phase 2 objective function</br>
54   * x1 &amp; x2: Decision variables</br>
55   * x-: Extra decision variable to allow for negative values</br>
56   * s1 &amp; 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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
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      */
650     protected final double[][] getData() {
651         return tableau.getData();
652     }
653 
654     @Override
655     public boolean equals(Object other) {
656 
657       if (this == other) {
658         return true;
659       }
660 
661       if (other instanceof SimplexTableau) {
662           SimplexTableau rhs = (SimplexTableau) other;
663           return (restrictToNonNegative  == rhs.restrictToNonNegative) &&
664                  (numDecisionVariables   == rhs.numDecisionVariables) &&
665                  (numSlackVariables      == rhs.numSlackVariables) &&
666                  (numArtificialVariables == rhs.numArtificialVariables) &&
667                  (epsilon                == rhs.epsilon) &&
668                  (maxUlps                == rhs.maxUlps) &&
669                  f.equals(rhs.f) &&
670                  constraints.equals(rhs.constraints) &&
671                  tableau.equals(rhs.tableau);
672       }
673       return false;
674     }
675 
676     @Override
677     public int hashCode() {
678         return Boolean.valueOf(restrictToNonNegative).hashCode() ^
679                numDecisionVariables ^
680                numSlackVariables ^
681                numArtificialVariables ^
682                Double.valueOf(epsilon).hashCode() ^
683                maxUlps ^
684                f.hashCode() ^
685                constraints.hashCode() ^
686                tableau.hashCode();
687     }
688 
689     /**
690      * Serialize the instance.
691      * @param oos stream where object should be written
692      * @throws IOException if object cannot be written to stream
693      */
694     private void writeObject(ObjectOutputStream oos)
695         throws IOException {
696         oos.defaultWriteObject();
697         MatrixUtils.serializeRealMatrix(tableau, oos);
698     }
699 
700     /**
701      * Deserialize the instance.
702      * @param ois stream from which the object should be read
703      * @throws ClassNotFoundException if a class in the stream cannot be found
704      * @throws IOException if object cannot be read from the stream
705      */
706     private void readObject(ObjectInputStream ois)
707       throws ClassNotFoundException, IOException {
708         ois.defaultReadObject();
709         MatrixUtils.deserializeRealMatrix(this, "tableau", ois);
710     }
711 }