qsimplex_p.cpp

Absolute File Name:/home/qt/qt5_coco/qt5/qtbase/src/widgets/graphicsview/qsimplex_p.cpp
Source codeSwitch to Preprocessed file
LineSourceCount
1/****************************************************************************-
2**-
3** Copyright (C) 2015 The Qt Company Ltd.-
4** Contact: http://www.qt.io/licensing/-
5**-
6** This file is part of the QtWidgets module of the Qt Toolkit.-
7**-
8** $QT_BEGIN_LICENSE:LGPL21$-
9** Commercial License Usage-
10** Licensees holding valid commercial Qt licenses may use this file in-
11** accordance with the commercial license agreement provided with the-
12** Software or, alternatively, in accordance with the terms contained in-
13** a written agreement between you and The Qt Company. For licensing terms-
14** and conditions see http://www.qt.io/terms-conditions. For further-
15** information use the contact form at http://www.qt.io/contact-us.-
16**-
17** GNU Lesser General Public License Usage-
18** Alternatively, this file may be used under the terms of the GNU Lesser-
19** General Public License version 2.1 or version 3 as published by the Free-
20** Software Foundation and appearing in the file LICENSE.LGPLv21 and-
21** LICENSE.LGPLv3 included in the packaging of this file. Please review the-
22** following information to ensure the GNU Lesser General Public License-
23** requirements will be met: https://www.gnu.org/licenses/lgpl.html and-
24** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.-
25**-
26** As a special exception, The Qt Company gives you certain additional-
27** rights. These rights are described in The Qt Company LGPL Exception-
28** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.-
29**-
30** $QT_END_LICENSE$-
31**-
32****************************************************************************/-
33-
34#include "qsimplex_p.h"-
35-
36#include <QtCore/qset.h>-
37#include <QtCore/qdebug.h>-
38-
39#include <stdlib.h>-
40-
41QT_BEGIN_NAMESPACE-
42-
43/*!-
44 \internal-
45 \class QSimplex-
46-
47 The QSimplex class is a Linear Programming problem solver based on the two-phase-
48 simplex method.-
49-
50 It takes a set of QSimplexConstraints as its restrictive constraints and an-
51 additional QSimplexConstraint as its objective function. Then methods to maximize-
52 and minimize the problem solution are provided.-
53-
54 The two-phase simplex method is based on the following steps:-
55 First phase:-
56 1.a) Modify the original, complex, and possibly not feasible problem, into a new,-
57 easy to solve problem.-
58 1.b) Set as the objective of the new problem, a feasible solution for the original-
59 complex problem.-
60 1.c) Run simplex to optimize the modified problem and check whether a solution for-
61 the original problem exists.-
62-
63 Second phase:-
64 2.a) Go back to the original problem with the feasibl (but not optimal) solution-
65 found in the first phase.-
66 2.b) Set the original objective.-
67 3.c) Run simplex to optimize the original problem towards its optimal solution.-
68*/-
69-
70/*!-
71 \internal-
72*/-
73QSimplex::QSimplex() : objective(0), rows(0), columns(0), firstArtificial(0), matrix(0)-
74{-
75}
never executed: end of block
0
76-
77/*!-
78 \internal-
79*/-
80QSimplex::~QSimplex()-
81{-
82 clearDataStructures();-
83}
never executed: end of block
0
84-
85/*!-
86 \internal-
87*/-
88void QSimplex::clearDataStructures()-
89{-
90 if (matrix == 0)
matrix == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
91 return;
never executed: return;
0
92-
93 // Matrix-
94 rows = 0;-
95 columns = 0;-
96 firstArtificial = 0;-
97 free(matrix);-
98 matrix = 0;-
99-
100 // Constraints-
101 for (int i = 0; i < constraints.size(); ++i) {
i < constraints.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
102 delete constraints[i]->helper.first;-
103 delete constraints[i]->artificial;-
104 delete constraints[i];-
105 }
never executed: end of block
0
106 constraints.clear();-
107-
108 // Other-
109 variables.clear();-
110 objective = 0;-
111}
never executed: end of block
0
112-
113/*!-
114 \internal-
115 Sets the new constraints in the simplex solver and returns whether the problem-
116 is feasible.-
117-
118 This method sets the new constraints, normalizes them, creates the simplex matrix-
119 and runs the first simplex phase.-
120*/-
121bool QSimplex::setConstraints(const QList<QSimplexConstraint *> &newConstraints)-
122{-
123 ////////////////////////////-
124 // Reset to initial state //-
125 ////////////////////////////-
126 clearDataStructures();-
127-
128 if (newConstraints.isEmpty())
newConstraints.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
129 return true; // we are ok with no constraints
never executed: return true;
0
130-
131 // Make deep copy of constraints. We need this copy because we may change-
132 // them in the simplification method.-
133 for (int i = 0; i < newConstraints.size(); ++i) {
i < newConstraints.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
134 QSimplexConstraint *c = new QSimplexConstraint;-
135 c->constant = newConstraints[i]->constant;-
136 c->ratio = newConstraints[i]->ratio;-
137 c->variables = newConstraints[i]->variables;-
138 constraints << c;-
139 }
never executed: end of block
0
140-
141 // Remove constraints of type Var == K and replace them for their value.-
142 if (!simplifyConstraints(&constraints)) {
!simplifyConst...(&constraints)Description
TRUEnever evaluated
FALSEnever evaluated
0
143 qWarning("QSimplex: No feasible solution!");-
144 clearDataStructures();-
145 return false;
never executed: return false;
0
146 }-
147-
148 ///////////////////////////////////////-
149 // Prepare variables and constraints //-
150 ///////////////////////////////////////-
151-
152 // Set Variables direct mapping.-
153 // "variables" is a list that provides a stable, indexed list of all variables-
154 // used in this problem.-
155 QSet<QSimplexVariable *> variablesSet;-
156 for (int i = 0; i < constraints.size(); ++i)
i < constraints.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
157 variablesSet += \
never executed: variablesSet += QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
0
158 QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
never executed: variablesSet += QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
0
159 variables = variablesSet.toList();-
160-
161 // Set Variables reverse mapping-
162 // We also need to be able to find the index for a given variable, to do that-
163 // we store in each variable its index.-
164 for (int i = 0; i < variables.size(); ++i) {
i < variables.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
165 // The variable "0" goes at the column "1", etc...-
166 variables[i]->index = i + 1;-
167 }
never executed: end of block
0
168-
169 // Normalize Constraints-
170 // In this step, we prepare the constraints in two ways:-
171 // Firstly, we modify all constraints of type "LessOrEqual" or "MoreOrEqual"-
172 // by the adding slack or surplus variables and making them "Equal" constraints.-
173 // Secondly, we need every single constraint to have a direct, easy feasible-
174 // solution. Constraints that have slack variables are already easy to solve,-
175 // to all the others we add artificial variables.-
176 //-
177 // At the end we modify the constraints as follows:-
178 // - LessOrEqual: SLACK variable is added.-
179 // - Equal: ARTIFICIAL variable is added.-
180 // - More or Equal: ARTIFICIAL and SURPLUS variables are added.-
181 int variableIndex = variables.size();-
182 QList <QSimplexVariable *> artificialList;-
183-
184 for (int i = 0; i < constraints.size(); ++i) {
i < constraints.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
185 QSimplexVariable *slack;-
186 QSimplexVariable *surplus;-
187 QSimplexVariable *artificial;-
188-
189 Q_ASSERT(constraints[i]->helper.first == 0);-
190 Q_ASSERT(constraints[i]->artificial == 0);-
191-
192 switch(constraints[i]->ratio) {-
193 case QSimplexConstraint::LessOrEqual:
never executed: case QSimplexConstraint::LessOrEqual:
0
194 slack = new QSimplexVariable;-
195 slack->index = ++variableIndex;-
196 constraints[i]->helper.first = slack;-
197 constraints[i]->helper.second = 1.0;-
198 break;
never executed: break;
0
199 case QSimplexConstraint::MoreOrEqual:
never executed: case QSimplexConstraint::MoreOrEqual:
0
200 surplus = new QSimplexVariable;-
201 surplus->index = ++variableIndex;-
202 constraints[i]->helper.first = surplus;-
203 constraints[i]->helper.second = -1.0;-
204 // fall through-
205 case QSimplexConstraint::Equal:
code before this statement never executed: case QSimplexConstraint::Equal:
never executed: case QSimplexConstraint::Equal:
0
206 artificial = new QSimplexVariable;-
207 constraints[i]->artificial = artificial;-
208 artificialList += constraints[i]->artificial;-
209 break;
never executed: break;
0
210 }-
211 }
never executed: end of block
0
212-
213 // All original, slack and surplus have already had its index set-
214 // at this point. We now set the index of the artificial variables-
215 // as to ensure they are at the end of the variable list and therefore-
216 // can be easily removed at the end of this method.-
217 firstArtificial = variableIndex + 1;-
218 for (int i = 0; i < artificialList.size(); ++i)
i < artificialList.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
219 artificialList[i]->index = ++variableIndex;
never executed: artificialList[i]->index = ++variableIndex;
0
220 artificialList.clear();-
221-
222 /////////////////////////////-
223 // Fill the Simplex matrix //-
224 /////////////////////////////-
225-
226 // One for each variable plus the Basic and BFS columns (first and last)-
227 columns = variableIndex + 2;-
228 // One for each constraint plus the objective function-
229 rows = constraints.size() + 1;-
230-
231 matrix = (qreal *)malloc(sizeof(qreal) * columns * rows);-
232 if (!matrix) {
!matrixDescription
TRUEnever evaluated
FALSEnever evaluated
0
233 qWarning("QSimplex: Unable to allocate memory!");-
234 return false;
never executed: return false;
0
235 }-
236 for (int i = columns * rows - 1; i >= 0; --i)
i >= 0Description
TRUEnever evaluated
FALSEnever evaluated
0
237 matrix[i] = 0.0;
never executed: matrix[i] = 0.0;
0
238-
239 // Fill Matrix-
240 for (int i = 1; i <= constraints.size(); ++i) {
i <= constraints.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
241 QSimplexConstraint *c = constraints[i - 1];-
242-
243 if (c->artificial) {
c->artificialDescription
TRUEnever evaluated
FALSEnever evaluated
0
244 // Will use artificial basic variable-
245 setValueAt(i, 0, c->artificial->index);-
246 setValueAt(i, c->artificial->index, 1.0);-
247-
248 if (c->helper.second != 0.0) {
c->helper.second != 0.0Description
TRUEnever evaluated
FALSEnever evaluated
0
249 // Surplus variable-
250 setValueAt(i, c->helper.first->index, c->helper.second);-
251 }
never executed: end of block
0
252 } else {
never executed: end of block
0
253 // Slack is used as the basic variable-
254 Q_ASSERT(c->helper.second == 1.0);-
255 setValueAt(i, 0, c->helper.first->index);-
256 setValueAt(i, c->helper.first->index, 1.0);-
257 }
never executed: end of block
0
258-
259 QHash<QSimplexVariable *, qreal>::const_iterator iter;-
260 for (iter = c->variables.constBegin();-
261 iter != c->variables.constEnd();
iter != c->var...les.constEnd()Description
TRUEnever evaluated
FALSEnever evaluated
0
262 ++iter) {-
263 setValueAt(i, iter.key()->index, iter.value());-
264 }
never executed: end of block
0
265-
266 setValueAt(i, columns - 1, c->constant);-
267 }
never executed: end of block
0
268-
269 // Set objective for the first-phase Simplex.-
270 // Z = -1 * sum_of_artificial_vars-
271 for (int j = firstArtificial; j < columns - 1; ++j)
j < columns - 1Description
TRUEnever evaluated
FALSEnever evaluated
0
272 setValueAt(0, j, 1.0);
never executed: setValueAt(0, j, 1.0);
0
273-
274 // Maximize our objective (artificial vars go to zero)-
275 solveMaxHelper();-
276-
277 // If there is a solution where the sum of all artificial-
278 // variables is zero, then all of them can be removed and yet-
279 // we will have a feasible (but not optimal) solution for the-
280 // original problem.-
281 // Otherwise, we clean up our structures and report there is-
282 // no feasible solution.-
283 if ((valueAt(0, columns - 1) != 0.0) && (qAbs(valueAt(0, columns - 1)) > 0.00001)) {
(valueAt(0, co...s - 1) != 0.0)Description
TRUEnever evaluated
FALSEnever evaluated
(qAbs(valueAt(...1)) > 0.00001)Description
TRUEnever evaluated
FALSEnever evaluated
0
284 qWarning("QSimplex: No feasible solution!");-
285 clearDataStructures();-
286 return false;
never executed: return false;
0
287 }-
288-
289 // Remove artificial variables. We already have a feasible-
290 // solution for the first problem, thus we don't need them-
291 // anymore.-
292 clearColumns(firstArtificial, columns - 2);-
293-
294 return true;
never executed: return true;
0
295}-
296-
297/*!-
298 \internal-
299-
300 Run simplex on the current matrix with the current objective.-
301-
302 This is the iterative method. The matrix lines are combined-
303 as to modify the variable values towards the best solution possible.-
304 The method returns when the matrix is in the optimal state.-
305*/-
306void QSimplex::solveMaxHelper()-
307{-
308 reducedRowEchelon();-
309 while (iterate()) ;
never executed: ;
iterate()Description
TRUEnever evaluated
FALSEnever evaluated
0
310}
never executed: end of block
0
311-
312/*!-
313 \internal-
314*/-
315void QSimplex::setObjective(QSimplexConstraint *newObjective)-
316{-
317 objective = newObjective;-
318}
never executed: end of block
0
319-
320/*!-
321 \internal-
322*/-
323void QSimplex::clearRow(int rowIndex)-
324{-
325 qreal *item = matrix + rowIndex * columns;-
326 for (int i = 0; i < columns; ++i)
i < columnsDescription
TRUEnever evaluated
FALSEnever evaluated
0
327 item[i] = 0.0;
never executed: item[i] = 0.0;
0
328}
never executed: end of block
0
329-
330/*!-
331 \internal-
332*/-
333void QSimplex::clearColumns(int first, int last)-
334{-
335 for (int i = 0; i < rows; ++i) {
i < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
0
336 qreal *row = matrix + i * columns;-
337 for (int j = first; j <= last; ++j)
j <= lastDescription
TRUEnever evaluated
FALSEnever evaluated
0
338 row[j] = 0.0;
never executed: row[j] = 0.0;
0
339 }
never executed: end of block
0
340}
never executed: end of block
0
341-
342/*!-
343 \internal-
344*/-
345void QSimplex::dumpMatrix()-
346{-
347 qDebug("---- Simplex Matrix ----\n");-
348-
349 QString str(QLatin1String(" "));-
350 for (int j = 0; j < columns; ++j)
j < columnsDescription
TRUEnever evaluated
FALSEnever evaluated
0
351 str += QString::fromLatin1(" <%1 >").arg(j, 2);
never executed: str += QString::fromLatin1(" <%1 >").arg(j, 2);
0
352 qDebug("%s", qPrintable(str));-
353 for (int i = 0; i < rows; ++i) {
i < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
0
354 str = QString::fromLatin1("Row %1:").arg(i, 2);-
355-
356 qreal *row = matrix + i * columns;-
357 for (int j = 0; j < columns; ++j)
j < columnsDescription
TRUEnever evaluated
FALSEnever evaluated
0
358 str += QString::fromLatin1("%1").arg(row[j], 7, 'f', 2);
never executed: str += QString::fromLatin1("%1").arg(row[j], 7, 'f', 2);
0
359 qDebug("%s", qPrintable(str));-
360 }
never executed: end of block
0
361 qDebug("------------------------\n");-
362}
never executed: end of block
0
363-
364/*!-
365 \internal-
366*/-
367void QSimplex::combineRows(int toIndex, int fromIndex, qreal factor)-
368{-
369 if (!factor)
!factorDescription
TRUEnever evaluated
FALSEnever evaluated
0
370 return;
never executed: return;
0
371-
372 qreal *from = matrix + fromIndex * columns;-
373 qreal *to = matrix + toIndex * columns;-
374-
375 for (int j = 1; j < columns; ++j) {
j < columnsDescription
TRUEnever evaluated
FALSEnever evaluated
0
376 qreal value = from[j];-
377-
378 // skip to[j] = to[j] + factor*0.0-
379 if (value == 0.0)
value == 0.0Description
TRUEnever evaluated
FALSEnever evaluated
0
380 continue;
never executed: continue;
0
381-
382 to[j] += factor * value;-
383-
384 // ### Avoid Numerical errors-
385 if (qAbs(to[j]) < 0.0000000001)
qAbs(to[j]) < 0.0000000001Description
TRUEnever evaluated
FALSEnever evaluated
0
386 to[j] = 0.0;
never executed: to[j] = 0.0;
0
387 }
never executed: end of block
0
388}
never executed: end of block
0
389-
390/*!-
391 \internal-
392*/-
393int QSimplex::findPivotColumn()-
394{-
395 qreal min = 0;-
396 int minIndex = -1;-
397-
398 for (int j = 0; j < columns-1; ++j) {
j < columns-1Description
TRUEnever evaluated
FALSEnever evaluated
0
399 if (valueAt(0, j) < min) {
valueAt(0, j) < minDescription
TRUEnever evaluated
FALSEnever evaluated
0
400 min = valueAt(0, j);-
401 minIndex = j;-
402 }
never executed: end of block
0
403 }
never executed: end of block
0
404-
405 return minIndex;
never executed: return minIndex;
0
406}-
407-
408/*!-
409 \internal-
410-
411 For a given pivot column, find the pivot row. That is, the row with the-
412 minimum associated "quotient" where:-
413-
414 - quotient is the division of the value in the last column by the value-
415 in the pivot column.-
416 - rows with value less or equal to zero are ignored-
417 - if two rows have the same quotient, lines are chosen based on the-
418 highest variable index (value in the first column)-
419-
420 The last condition avoids a bug where artificial variables would be-
421 left behind for the second-phase simplex, and with 'good'-
422 constraints would be removed before it, what would lead to incorrect-
423 results.-
424*/-
425int QSimplex::pivotRowForColumn(int column)-
426{-
427 qreal min = qreal(999999999999.0); // ###-
428 int minIndex = -1;-
429-
430 for (int i = 1; i < rows; ++i) {
i < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
0
431 qreal divisor = valueAt(i, column);-
432 if (divisor <= 0)
divisor <= 0Description
TRUEnever evaluated
FALSEnever evaluated
0
433 continue;
never executed: continue;
0
434-
435 qreal quotient = valueAt(i, columns - 1) / divisor;-
436 if (quotient < min) {
quotient < minDescription
TRUEnever evaluated
FALSEnever evaluated
0
437 min = quotient;-
438 minIndex = i;-
439 } else if ((quotient == min) && (valueAt(i, 0) > valueAt(minIndex, 0))) {
never executed: end of block
(quotient == min)Description
TRUEnever evaluated
FALSEnever evaluated
(valueAt(i, 0)...(minIndex, 0))Description
TRUEnever evaluated
FALSEnever evaluated
0
440 minIndex = i;-
441 }
never executed: end of block
0
442 }
never executed: end of block
0
443-
444 return minIndex;
never executed: return minIndex;
0
445}-
446-
447/*!-
448 \internal-
449*/-
450void QSimplex::reducedRowEchelon()-
451{-
452 for (int i = 1; i < rows; ++i) {
i < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
0
453 int factorInObjectiveRow = valueAt(i, 0);-
454 combineRows(0, i, -1 * valueAt(0, factorInObjectiveRow));-
455 }
never executed: end of block
0
456}
never executed: end of block
0
457-
458/*!-
459 \internal-
460-
461 Does one iteration towards a better solution for the problem.-
462 See 'solveMaxHelper'.-
463*/-
464bool QSimplex::iterate()-
465{-
466 // Find Pivot column-
467 int pivotColumn = findPivotColumn();-
468 if (pivotColumn == -1)
pivotColumn == -1Description
TRUEnever evaluated
FALSEnever evaluated
0
469 return false;
never executed: return false;
0
470-
471 // Find Pivot row for column-
472 int pivotRow = pivotRowForColumn(pivotColumn);-
473 if (pivotRow == -1) {
pivotRow == -1Description
TRUEnever evaluated
FALSEnever evaluated
0
474 qWarning("QSimplex: Unbounded problem!");-
475 return false;
never executed: return false;
0
476 }-
477-
478 // Normalize Pivot Row-
479 qreal pivot = valueAt(pivotRow, pivotColumn);-
480 if (pivot != 1.0)
pivot != 1.0Description
TRUEnever evaluated
FALSEnever evaluated
0
481 combineRows(pivotRow, pivotRow, (1.0 - pivot) / pivot);
never executed: combineRows(pivotRow, pivotRow, (1.0 - pivot) / pivot);
0
482-
483 // Update other rows-
484 for (int row=0; row < rows; ++row) {
row < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
0
485 if (row == pivotRow)
row == pivotRowDescription
TRUEnever evaluated
FALSEnever evaluated
0
486 continue;
never executed: continue;
0
487-
488 combineRows(row, pivotRow, -1 * valueAt(row, pivotColumn));-
489 }
never executed: end of block
0
490-
491 // Update first column-
492 setValueAt(pivotRow, 0, pivotColumn);-
493-
494 // dumpMatrix();-
495 // qDebug("------------ end of iteration --------------\n");-
496 return true;
never executed: return true;
0
497}-
498-
499/*!-
500 \internal-
501-
502 Both solveMin and solveMax are interfaces to this method.-
503-
504 The enum SolverFactor admits 2 values: Minimum (-1) and Maximum (+1).-
505-
506 This method sets the original objective and runs the second phase-
507 Simplex to obtain the optimal solution for the problem. As the internal-
508 simplex solver is only able to _maximize_ objectives, we handle the-
509 minimization case by inverting the original objective and then-
510 maximizing it.-
511*/-
512qreal QSimplex::solver(SolverFactor factor)-
513{-
514 // Remove old objective-
515 clearRow(0);-
516-
517 // Set new objective in the first row of the simplex matrix-
518 qreal resultOffset = 0;-
519 QHash<QSimplexVariable *, qreal>::const_iterator iter;-
520 for (iter = objective->variables.constBegin();-
521 iter != objective->variables.constEnd();
iter != object...les.constEnd()Description
TRUEnever evaluated
FALSEnever evaluated
0
522 ++iter) {-
523-
524 // Check if the variable was removed in the simplification process.-
525 // If so, we save its offset to the objective function and skip adding-
526 // it to the matrix.-
527 if (iter.key()->index == -1) {
iter.key()->index == -1Description
TRUEnever evaluated
FALSEnever evaluated
0
528 resultOffset += iter.value() * iter.key()->result;-
529 continue;
never executed: continue;
0
530 }-
531-
532 setValueAt(0, iter.key()->index, -1 * factor * iter.value());-
533 }
never executed: end of block
0
534-
535 solveMaxHelper();-
536 collectResults();-
537-
538#ifdef QT_DEBUG-
539 for (int i = 0; i < constraints.size(); ++i) {
i < constraints.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
540 Q_ASSERT(constraints[i]->isSatisfied());-
541 }
never executed: end of block
0
542#endif-
543-
544 // Return the value calculated by the simplex plus the value of the-
545 // fixed variables.-
546 return (factor * valueAt(0, columns - 1)) + resultOffset;
never executed: return (factor * valueAt(0, columns - 1)) + resultOffset;
0
547}-
548-
549/*!-
550 \internal-
551 Minimize the original objective.-
552*/-
553qreal QSimplex::solveMin()-
554{-
555 return solver(Minimum);
never executed: return solver(Minimum);
0
556}-
557-
558/*!-
559 \internal-
560 Maximize the original objective.-
561*/-
562qreal QSimplex::solveMax()-
563{-
564 return solver(Maximum);
never executed: return solver(Maximum);
0
565}-
566-
567/*!-
568 \internal-
569-
570 Reads results from the simplified matrix and saves them in the-
571 "result" member of each QSimplexVariable.-
572*/-
573void QSimplex::collectResults()-
574{-
575 // All variables are zero unless overridden below.-
576-
577 // ### Is this really needed? Is there any chance that an-
578 // important variable remains as non-basic at the end of simplex?-
579 for (int i = 0; i < variables.size(); ++i)
i < variables.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
580 variables[i]->result = 0;
never executed: variables[i]->result = 0;
0
581-
582 // Basic variables-
583 // Update the variable indicated in the first column with the value-
584 // in the last column.-
585 for (int i = 1; i < rows; ++i) {
i < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
0
586 int index = valueAt(i, 0) - 1;-
587 if (index < variables.size())
index < variables.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
588 variables[index]->result = valueAt(i, columns - 1);
never executed: variables[index]->result = valueAt(i, columns - 1);
0
589 }
never executed: end of block
0
590}
never executed: end of block
0
591-
592/*!-
593 \internal-
594-
595 Looks for single-valued variables and remove them from the constraints list.-
596*/-
597bool QSimplex::simplifyConstraints(QList<QSimplexConstraint *> *constraints)-
598{-
599 QHash<QSimplexVariable *, qreal> results; // List of single-valued variables-
600 bool modified = true; // Any chance more optimization exists?-
601-
602 while (modified) {
modifiedDescription
TRUEnever evaluated
FALSEnever evaluated
0
603 modified = false;-
604-
605 // For all constraints-
606 QList<QSimplexConstraint *>::iterator iter = constraints->begin();-
607 while (iter != constraints->end()) {
iter != constraints->end()Description
TRUEnever evaluated
FALSEnever evaluated
0
608 QSimplexConstraint *c = *iter;-
609 if ((c->ratio == QSimplexConstraint::Equal) && (c->variables.count() == 1)) {
(c->ratio == Q...traint::Equal)Description
TRUEnever evaluated
FALSEnever evaluated
(c->variables.count() == 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
610 // Check whether this is a constraint of type Var == K-
611 // If so, save its value to "results".-
612 QSimplexVariable *variable = c->variables.constBegin().key();-
613 qreal result = c->constant / c->variables.value(variable);-
614-
615 results.insert(variable, result);-
616 variable->result = result;-
617 variable->index = -1;-
618 modified = true;-
619-
620 }
never executed: end of block
0
621-
622 // Replace known values among their variables-
623 QHash<QSimplexVariable *, qreal>::const_iterator r;-
624 for (r = results.constBegin(); r != results.constEnd(); ++r) {
r != results.constEnd()Description
TRUEnever evaluated
FALSEnever evaluated
0
625 if (c->variables.contains(r.key())) {
c->variables.contains(r.key())Description
TRUEnever evaluated
FALSEnever evaluated
0
626 c->constant -= r.value() * c->variables.take(r.key());-
627 modified = true;-
628 }
never executed: end of block
0
629 }
never executed: end of block
0
630-
631 // Keep it normalized-
632 if (c->constant < 0)
c->constant < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
633 c->invert();
never executed: c->invert();
0
634-
635 if (c->variables.isEmpty()) {
c->variables.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
636 // If constraint became empty due to substitution, delete it.-
637 if (c->isSatisfied() == false)
c->isSatisfied() == falseDescription
TRUEnever evaluated
FALSEnever evaluated
0
638 // We must ensure that the constraint soon to be deleted would not-
639 // make the problem unfeasible if left behind. If that's the case,-
640 // we return false so the simplex solver can properly report that.-
641 return false;
never executed: return false;
0
642-
643 delete c;-
644 iter = constraints->erase(iter);-
645 } else {
never executed: end of block
0
646 ++iter;-
647 }
never executed: end of block
0
648 }-
649 }
never executed: end of block
0
650-
651 return true;
never executed: return true;
0
652}-
653-
654void QSimplexConstraint::invert()-
655{-
656 constant = -constant;-
657 ratio = Ratio(2 - ratio);-
658-
659 QHash<QSimplexVariable *, qreal>::iterator iter;-
660 for (iter = variables.begin(); iter != variables.end(); ++iter) {
iter != variables.end()Description
TRUEnever evaluated
FALSEnever evaluated
0
661 iter.value() = -iter.value();-
662 }
never executed: end of block
0
663}
never executed: end of block
0
664-
665QT_END_NAMESPACE-
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9