106 matrix = 0; |
106 matrix = 0; |
107 |
107 |
108 // Constraints |
108 // Constraints |
109 for (int i = 0; i < constraints.size(); ++i) { |
109 for (int i = 0; i < constraints.size(); ++i) { |
110 delete constraints[i]->helper.first; |
110 delete constraints[i]->helper.first; |
111 constraints[i]->helper.first = 0; |
|
112 constraints[i]->helper.second = 0.0; |
|
113 delete constraints[i]->artificial; |
111 delete constraints[i]->artificial; |
114 constraints[i]->artificial = 0; |
112 delete constraints[i]; |
115 } |
113 } |
116 constraints.clear(); |
114 constraints.clear(); |
117 |
115 |
118 // Other |
116 // Other |
119 variables.clear(); |
117 variables.clear(); |
135 //////////////////////////// |
133 //////////////////////////// |
136 clearDataStructures(); |
134 clearDataStructures(); |
137 |
135 |
138 if (newConstraints.isEmpty()) |
136 if (newConstraints.isEmpty()) |
139 return true; // we are ok with no constraints |
137 return true; // we are ok with no constraints |
140 constraints = newConstraints; |
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) { |
|
142 QSimplexConstraint *c = new QSimplexConstraint; |
|
143 c->constant = newConstraints[i]->constant; |
|
144 c->ratio = newConstraints[i]->ratio; |
|
145 c->variables = newConstraints[i]->variables; |
|
146 constraints << c; |
|
147 } |
|
148 |
|
149 // Remove constraints of type Var == K and replace them for their value. |
|
150 if (!simplifyConstraints(&constraints)) { |
|
151 qWarning() << "QSimplex: No feasible solution!"; |
|
152 clearDataStructures(); |
|
153 return false; |
|
154 } |
141 |
155 |
142 /////////////////////////////////////// |
156 /////////////////////////////////////// |
143 // Prepare variables and constraints // |
157 // Prepare variables and constraints // |
144 /////////////////////////////////////// |
158 /////////////////////////////////////// |
145 |
159 |
272 // variables is zero, then all of them can be removed and yet |
286 // variables is zero, then all of them can be removed and yet |
273 // we will have a feasible (but not optimal) solution for the |
287 // we will have a feasible (but not optimal) solution for the |
274 // original problem. |
288 // original problem. |
275 // Otherwise, we clean up our structures and report there is |
289 // Otherwise, we clean up our structures and report there is |
276 // no feasible solution. |
290 // no feasible solution. |
277 if (valueAt(0, columns - 1) != 0.0) { |
291 if ((valueAt(0, columns - 1) != 0.0) && (qAbs(valueAt(0, columns - 1)) > 0.00001)) { |
278 qWarning() << "QSimplex: No feasible solution!"; |
292 qWarning() << "QSimplex: No feasible solution!"; |
279 clearDataStructures(); |
293 clearDataStructures(); |
280 return false; |
294 return false; |
281 } |
295 } |
282 |
296 |
506 qreal QSimplex::solver(solverFactor factor) |
520 qreal QSimplex::solver(solverFactor factor) |
507 { |
521 { |
508 // Remove old objective |
522 // Remove old objective |
509 clearRow(0); |
523 clearRow(0); |
510 |
524 |
511 // Set new objective |
525 // Set new objective in the first row of the simplex matrix |
|
526 qreal resultOffset = 0; |
512 QHash<QSimplexVariable *, qreal>::const_iterator iter; |
527 QHash<QSimplexVariable *, qreal>::const_iterator iter; |
513 for (iter = objective->variables.constBegin(); |
528 for (iter = objective->variables.constBegin(); |
514 iter != objective->variables.constEnd(); |
529 iter != objective->variables.constEnd(); |
515 ++iter) { |
530 ++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) { |
|
536 resultOffset += iter.value() * iter.key()->result; |
|
537 continue; |
|
538 } |
|
539 |
516 setValueAt(0, iter.key()->index, -1 * factor * iter.value()); |
540 setValueAt(0, iter.key()->index, -1 * factor * iter.value()); |
517 } |
541 } |
518 |
542 |
519 solveMaxHelper(); |
543 solveMaxHelper(); |
520 collectResults(); |
544 collectResults(); |
523 for (int i = 0; i < constraints.size(); ++i) { |
547 for (int i = 0; i < constraints.size(); ++i) { |
524 Q_ASSERT(constraints[i]->isSatisfied()); |
548 Q_ASSERT(constraints[i]->isSatisfied()); |
525 } |
549 } |
526 #endif |
550 #endif |
527 |
551 |
528 return factor * valueAt(0, columns - 1); |
552 // Return the value calculated by the simplex plus the value of the |
|
553 // fixed variables. |
|
554 return (factor * valueAt(0, columns - 1)) + resultOffset; |
529 } |
555 } |
530 |
556 |
531 /*! |
557 /*! |
532 \internal |
558 \internal |
533 Minimize the original objective. |
559 Minimize the original objective. |
569 if (index < variables.size()) |
595 if (index < variables.size()) |
570 variables[index]->result = valueAt(i, columns - 1); |
596 variables[index]->result = valueAt(i, columns - 1); |
571 } |
597 } |
572 } |
598 } |
573 |
599 |
|
600 /*! |
|
601 \internal |
|
602 |
|
603 Looks for single-valued variables and remove them from the constraints list. |
|
604 */ |
|
605 bool QSimplex::simplifyConstraints(QList<QSimplexConstraint *> *constraints) |
|
606 { |
|
607 QHash<QSimplexVariable *, qreal> results; // List of single-valued variables |
|
608 bool modified = true; // Any chance more optimization exists? |
|
609 |
|
610 while (modified) { |
|
611 modified = false; |
|
612 |
|
613 // For all constraints |
|
614 QList<QSimplexConstraint *>::iterator iter = constraints->begin(); |
|
615 while (iter != constraints->end()) { |
|
616 QSimplexConstraint *c = *iter; |
|
617 if ((c->ratio == QSimplexConstraint::Equal) && (c->variables.count() == 1)) { |
|
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(); |
|
621 qreal result = c->constant / c->variables.value(variable); |
|
622 |
|
623 results.insert(variable, result); |
|
624 variable->result = result; |
|
625 variable->index = -1; |
|
626 modified = true; |
|
627 |
|
628 } |
|
629 |
|
630 // Replace known values among their variables |
|
631 QHash<QSimplexVariable *, qreal>::const_iterator r; |
|
632 for (r = results.constBegin(); r != results.constEnd(); ++r) { |
|
633 if (c->variables.contains(r.key())) { |
|
634 c->constant -= r.value() * c->variables.take(r.key()); |
|
635 modified = true; |
|
636 } |
|
637 } |
|
638 |
|
639 // Keep it normalized |
|
640 if (c->constant < 0) |
|
641 c->invert(); |
|
642 |
|
643 if (c->variables.isEmpty()) { |
|
644 // If constraint became empty due to substitution, delete it. |
|
645 if (c->isSatisfied() == false) |
|
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; |
|
650 |
|
651 delete c; |
|
652 iter = constraints->erase(iter); |
|
653 } else { |
|
654 ++iter; |
|
655 } |
|
656 } |
|
657 } |
|
658 |
|
659 return true; |
|
660 } |
|
661 |
|
662 void QSimplexConstraint::invert() |
|
663 { |
|
664 constant = -constant; |
|
665 ratio = Ratio(2 - ratio); |
|
666 |
|
667 QHash<QSimplexVariable *, qreal>::iterator iter; |
|
668 for (iter = variables.begin(); iter != variables.end(); ++iter) { |
|
669 iter.value() = -iter.value(); |
|
670 } |
|
671 } |
|
672 |
574 QT_END_NAMESPACE |
673 QT_END_NAMESPACE |