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