graphicsview/qsimplex_p.cpp

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