1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.commons.math.optimization.linear;
19
20 import java.io.IOException;
21 import java.io.ObjectInputStream;
22 import java.io.ObjectOutputStream;
23 import java.io.Serializable;
24 import java.util.ArrayList;
25 import java.util.Collection;
26 import java.util.HashSet;
27 import java.util.List;
28 import java.util.Set;
29
30 import org.apache.commons.math.linear.MatrixUtils;
31 import org.apache.commons.math.linear.RealMatrix;
32 import org.apache.commons.math.linear.Array2DRowRealMatrix;
33 import org.apache.commons.math.linear.RealVector;
34 import org.apache.commons.math.optimization.GoalType;
35 import org.apache.commons.math.optimization.RealPointValuePair;
36 import org.apache.commons.math.util.MathUtils;
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 class SimplexTableau implements Serializable {
64
65
66 private static final long serialVersionUID = -1369660067587938365L;
67
68
69 private final LinearObjectiveFunction f;
70
71
72 private final Collection<LinearConstraint> constraints;
73
74
75 private final boolean restrictToNonNegative;
76
77
78 protected transient RealMatrix tableau;
79
80
81 protected final int numDecisionVariables;
82
83
84 protected final int numSlackVariables;
85
86
87 protected int numArtificialVariables;
88
89
90 protected final double epsilon;
91
92
93
94
95
96
97
98
99
100
101 SimplexTableau(final LinearObjectiveFunction f,
102 final Collection<LinearConstraint> constraints,
103 final GoalType goalType, final boolean restrictToNonNegative,
104 final double epsilon) {
105 this.f = f;
106 this.constraints = constraints;
107 this.restrictToNonNegative = restrictToNonNegative;
108 this.epsilon = epsilon;
109 this.numDecisionVariables = getNumVariables() + (restrictToNonNegative ? 0 : 1);
110 this.numSlackVariables = getConstraintTypeCounts(Relationship.LEQ) +
111 getConstraintTypeCounts(Relationship.GEQ);
112 this.numArtificialVariables = getConstraintTypeCounts(Relationship.EQ) +
113 getConstraintTypeCounts(Relationship.GEQ);
114 this.tableau = new Array2DRowRealMatrix(createTableau(goalType == GoalType.MAXIMIZE));
115 initialize();
116 }
117
118
119
120
121
122
123 protected double[][] createTableau(final boolean maximize) {
124
125
126 List<LinearConstraint> constraints = getNormalizedConstraints();
127 int width = numDecisionVariables + numSlackVariables +
128 numArtificialVariables + getNumObjectiveFunctions() + 1;
129 int height = constraints.size() + getNumObjectiveFunctions();
130 double[][] matrix = new double[height][width];
131
132
133 if (getNumObjectiveFunctions() == 2) {
134 matrix[0][0] = -1;
135 }
136 int zIndex = (getNumObjectiveFunctions() == 1) ? 0 : 1;
137 matrix[zIndex][zIndex] = maximize ? 1 : -1;
138 RealVector objectiveCoefficients =
139 maximize ? f.getCoefficients().mapMultiply(-1) : f.getCoefficients();
140 copyArray(objectiveCoefficients.getData(), matrix[zIndex], getNumObjectiveFunctions());
141 matrix[zIndex][width - 1] =
142 maximize ? f.getConstantTerm() : -1 * f.getConstantTerm();
143
144 if (!restrictToNonNegative) {
145 matrix[zIndex][getSlackVariableOffset() - 1] =
146 getInvertedCoeffiecientSum(objectiveCoefficients);
147 }
148
149
150 int slackVar = 0;
151 int artificialVar = 0;
152 for (int i = 0; i < constraints.size(); i++) {
153 LinearConstraint constraint = constraints.get(i);
154 int row = getNumObjectiveFunctions() + i;
155
156
157 copyArray(constraint.getCoefficients().getData(), matrix[row], 1);
158
159
160 if (!restrictToNonNegative) {
161 matrix[row][getSlackVariableOffset() - 1] =
162 getInvertedCoeffiecientSum(constraint.getCoefficients());
163 }
164
165
166 matrix[row][width - 1] = constraint.getValue();
167
168
169 if (constraint.getRelationship() == Relationship.LEQ) {
170 matrix[row][getSlackVariableOffset() + slackVar++] = 1;
171 } else if (constraint.getRelationship() == Relationship.GEQ) {
172 matrix[row][getSlackVariableOffset() + slackVar++] = -1;
173 }
174
175
176 if ((constraint.getRelationship() == Relationship.EQ) ||
177 (constraint.getRelationship() == Relationship.GEQ)) {
178 matrix[0][getArtificialVariableOffset() + artificialVar] = 1;
179 matrix[row][getArtificialVariableOffset() + artificialVar++] = 1;
180 }
181 }
182
183 return matrix;
184 }
185
186
187
188
189 public int getNumVariables() {
190 return f.getCoefficients().getDimension();
191 }
192
193
194
195
196
197 public List<LinearConstraint> getNormalizedConstraints() {
198 List<LinearConstraint> normalized = new ArrayList<LinearConstraint>();
199 for (LinearConstraint constraint : constraints) {
200 normalized.add(normalize(constraint));
201 }
202 return normalized;
203 }
204
205
206
207
208
209
210 private LinearConstraint normalize(final LinearConstraint constraint) {
211 if (constraint.getValue() < 0) {
212 return new LinearConstraint(constraint.getCoefficients().mapMultiply(-1),
213 constraint.getRelationship().oppositeRelationship(),
214 -1 * constraint.getValue());
215 }
216 return new LinearConstraint(constraint.getCoefficients(),
217 constraint.getRelationship(), constraint.getValue());
218 }
219
220
221
222
223
224 protected final int getNumObjectiveFunctions() {
225 return this.numArtificialVariables > 0 ? 2 : 1;
226 }
227
228
229
230
231
232
233 private int getConstraintTypeCounts(final Relationship relationship) {
234 int count = 0;
235 for (final LinearConstraint constraint : constraints) {
236 if (constraint.getRelationship() == relationship) {
237 ++count;
238 }
239 }
240 return count;
241 }
242
243
244
245
246
247 private void initialize() {
248 for (int artificialVar = 0; artificialVar < numArtificialVariables; artificialVar++) {
249 int row = getBasicRow(getArtificialVariableOffset() + artificialVar);
250 subtractRow(0, row, 1.0);
251 }
252 }
253
254
255
256
257
258
259 protected static double getInvertedCoeffiecientSum(final RealVector coefficients) {
260 double sum = 0;
261 for (double coefficient : coefficients.getData()) {
262 sum -= coefficient;
263 }
264 return sum;
265 }
266
267
268
269
270
271
272 private Integer getBasicRow(final int col) {
273 Integer row = null;
274 for (int i = getNumObjectiveFunctions(); i < getHeight(); i++) {
275 if (MathUtils.equals(getEntry(i, col), 1.0, epsilon) && (row == null)) {
276 row = i;
277 } else if (!MathUtils.equals(getEntry(i, col), 0.0, epsilon)) {
278 return null;
279 }
280 }
281 return row;
282 }
283
284
285
286
287 protected void discardArtificialVariables() {
288 if (numArtificialVariables == 0) {
289 return;
290 }
291 int width = getWidth() - numArtificialVariables - 1;
292 int height = getHeight() - 1;
293 double[][] matrix = new double[height][width];
294 for (int i = 0; i < height; i++) {
295 for (int j = 0; j < width - 1; j++) {
296 matrix[i][j] = getEntry(i + 1, j + 1);
297 }
298 matrix[i][width - 1] = getEntry(i + 1, getRhsOffset());
299 }
300 this.tableau = new Array2DRowRealMatrix(matrix);
301 this.numArtificialVariables = 0;
302 }
303
304
305
306
307
308
309
310 private void copyArray(final double[] src, final double[] dest,
311 final int destPos) {
312 System.arraycopy(src, 0, dest, getNumObjectiveFunctions(), src.length);
313 }
314
315
316
317
318
319
320 protected RealPointValuePair getSolution() {
321 double[] coefficients = new double[getOriginalNumDecisionVariables()];
322 Integer basicRow =
323 getBasicRow(getNumObjectiveFunctions() + getOriginalNumDecisionVariables());
324 double mostNegative = basicRow == null ? 0 : getEntry(basicRow, getRhsOffset());
325 Set<Integer> basicRows = new HashSet<Integer>();
326 for (int i = 0; i < coefficients.length; i++) {
327 basicRow = getBasicRow(getNumObjectiveFunctions() + i);
328 if (basicRows.contains(basicRow)) {
329
330
331 coefficients[i] = 0;
332 } else {
333 basicRows.add(basicRow);
334 coefficients[i] =
335 (basicRow == null ? 0 : getEntry(basicRow, getRhsOffset())) -
336 (restrictToNonNegative ? 0 : mostNegative);
337 }
338 }
339 return new RealPointValuePair(coefficients, f.getValue(coefficients));
340 }
341
342
343
344
345
346
347
348
349
350
351 protected void divideRow(final int dividendRow, final double divisor) {
352 for (int j = 0; j < getWidth(); j++) {
353 tableau.setEntry(dividendRow, j, tableau.getEntry(dividendRow, j) / divisor);
354 }
355 }
356
357
358
359
360
361
362
363
364
365
366
367 protected void subtractRow(final int minuendRow, final int subtrahendRow,
368 final double multiple) {
369 for (int j = 0; j < getWidth(); j++) {
370 tableau.setEntry(minuendRow, j, tableau.getEntry(minuendRow, j) -
371 multiple * tableau.getEntry(subtrahendRow, j));
372 }
373 }
374
375
376
377
378
379 protected final int getWidth() {
380 return tableau.getColumnDimension();
381 }
382
383
384
385
386
387 protected final int getHeight() {
388 return tableau.getRowDimension();
389 }
390
391
392
393
394
395
396 protected final double getEntry(final int row, final int column) {
397 return tableau.getEntry(row, column);
398 }
399
400
401
402
403
404
405 protected final void setEntry(final int row, final int column,
406 final double value) {
407 tableau.setEntry(row, column, value);
408 }
409
410
411
412
413
414 protected final int getSlackVariableOffset() {
415 return getNumObjectiveFunctions() + numDecisionVariables;
416 }
417
418
419
420
421
422 protected final int getArtificialVariableOffset() {
423 return getNumObjectiveFunctions() + numDecisionVariables + numSlackVariables;
424 }
425
426
427
428
429
430 protected final int getRhsOffset() {
431 return getWidth() - 1;
432 }
433
434
435
436
437
438
439
440
441
442
443
444 protected final int getNumDecisionVariables() {
445 return numDecisionVariables;
446 }
447
448
449
450
451
452
453 protected final int getOriginalNumDecisionVariables() {
454 return restrictToNonNegative ? numDecisionVariables : numDecisionVariables - 1;
455 }
456
457
458
459
460
461 protected final int getNumSlackVariables() {
462 return numSlackVariables;
463 }
464
465
466
467
468
469 protected final int getNumArtificialVariables() {
470 return numArtificialVariables;
471 }
472
473
474
475
476
477 protected final double[][] getData() {
478 return tableau.getData();
479 }
480
481
482 @Override
483 public boolean equals(Object other) {
484
485 if (this == other) {
486 return true;
487 }
488
489 if (other == null) {
490 return false;
491 }
492
493 try {
494
495 SimplexTableau rhs = (SimplexTableau) other;
496 return (restrictToNonNegative == rhs.restrictToNonNegative) &&
497 (numDecisionVariables == rhs.numDecisionVariables) &&
498 (numSlackVariables == rhs.numSlackVariables) &&
499 (numArtificialVariables == rhs.numArtificialVariables) &&
500 (epsilon == rhs.epsilon) &&
501 f.equals(rhs.f) &&
502 constraints.equals(rhs.constraints) &&
503 tableau.equals(rhs.tableau);
504
505 } catch (ClassCastException ex) {
506
507 return false;
508 }
509
510 }
511
512
513 @Override
514 public int hashCode() {
515 return Boolean.valueOf(restrictToNonNegative).hashCode() ^
516 numDecisionVariables ^
517 numSlackVariables ^
518 numArtificialVariables ^
519 Double.valueOf(epsilon).hashCode() ^
520 f.hashCode() ^
521 constraints.hashCode() ^
522 tableau.hashCode();
523 }
524
525
526
527
528
529 private void writeObject(ObjectOutputStream oos)
530 throws IOException {
531 oos.defaultWriteObject();
532 MatrixUtils.serializeRealMatrix(tableau, oos);
533 }
534
535
536
537
538
539
540 private void readObject(ObjectInputStream ois)
541 throws ClassNotFoundException, IOException {
542 ois.defaultReadObject();
543 MatrixUtils.deserializeRealMatrix(this, "tableau", ois);
544 }
545 }