2 files changed, 99 insertions, 4 deletions

diff --git a/src/gui/graphicsview/qsimplex_p.cpp b/src/gui/graphicsview/qsimplex_p.cpp
index b3997fa..86b10b4 100644
--- a/src/gui/graphicsview/qsimplex_p.cpp
+++ b/src/gui/graphicsview/qsimplex_p.cpp
@@ -146,6 +146,13 @@ bool QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
         constraints << c;
     }
 
+    // Remove constraints of type Var == K and replace them for their value.
+    if (!simplifyConstraints(&constraints)) {
+        qWarning() << "QSimplex: No feasible solution!";
+        clearDataStructures();
+        return false;
+    }
+
     ///////////////////////////////////////
     // Prepare variables and constraints //
     ///////////////////////////////////////
@@ -515,11 +522,21 @@ qreal QSimplex::solver(solverFactor factor)
     // Remove old objective
     clearRow(0);
 
-    // Set new objective
+    // Set new objective in the first row of the simplex matrix
+    qreal resultOffset = 0;
     QHash<QSimplexVariable *, qreal>::const_iterator iter;
     for (iter = objective->variables.constBegin();
          iter != objective->variables.constEnd();
          ++iter) {
+
+        // Check if the variable was removed in the simplification process.
+        // If so, we save its offset to the objective function and skip adding
+        // it to the matrix.
+        if (iter.key()->index == -1) {
+            resultOffset += iter.value() * iter.key()->result;
+            continue;
+        }
+
         setValueAt(0, iter.key()->index, -1 * factor * iter.value());
     }
 
@@ -532,7 +549,9 @@ qreal QSimplex::solver(solverFactor factor)
     }
 #endif
 
-    return factor * valueAt(0, columns - 1);
+    // Return the value calculated by the simplex plus the value of the
+    // fixed variables.
+    return (factor * valueAt(0, columns - 1)) + resultOffset;
 }
 
 /*!
@@ -578,4 +597,77 @@ void QSimplex::collectResults()
     }
 }
 
+/*!
+  \internal
+
+  Looks for single-valued variables and remove them from the constraints list.
+*/
+bool QSimplex::simplifyConstraints(QList<QSimplexConstraint *> *constraints)
+{
+    QHash<QSimplexVariable *, qreal> results;   // List of single-valued variables
+    bool modified = true;                       // Any chance more optimization exists?
+
+    while (modified) {
+        modified = false;
+
+        // For all constraints
+        QList<QSimplexConstraint *>::iterator iter = constraints->begin();
+        while (iter != constraints->end()) {
+            QSimplexConstraint *c = *iter;
+            if ((c->ratio == QSimplexConstraint::Equal) && (c->variables.count() == 1)) {
+                // Check whether this is a constraint of type Var == K
+                // If so, save its value to "results".
+                QSimplexVariable *variable = c->variables.constBegin().key();
+                qreal result = c->constant / c->variables.value(variable);
+
+                results.insert(variable, result);
+                variable->result = result;
+                variable->index = -1;
+                modified = true;
+
+            }
+
+            // Replace known values among their variables
+            QHash<QSimplexVariable *, qreal>::const_iterator r;
+            for (r = results.constBegin(); r != results.constEnd(); ++r) {
+                if (c->variables.contains(r.key())) {
+                    c->constant -= r.value() * c->variables.take(r.key());
+                    modified = true;
+                }
+            }
+
+            // Keep it normalized
+            if (c->constant < 0)
+                c->invert();
+
+            if (c->variables.isEmpty()) {
+                // If constraint became empty due to substitution, delete it.
+                if (c->isSatisfied() == false)
+                    // We must ensure that the constraint soon to be deleted would not
+                    // make the problem unfeasible if left behind. If that's the case,
+                    // we return false so the simplex solver can properly report that.
+                    return false;
+
+                delete c;
+                iter = constraints->erase(iter);
+            } else {
+                ++iter;
+            }
+        }
+    }
+
+    return true;
+}
+
+void QSimplexConstraint::invert()
+{
+    constant = -constant;
+    ratio = Ratio(2 - ratio);
+
+    QHash<QSimplexVariable *, qreal>::iterator iter;
+    for (iter = variables.begin(); iter != variables.end(); ++iter) {
+        iter.value() = -iter.value();
+    }
+}
+
 QT_END_NAMESPACE
diff --git a/src/gui/graphicsview/qsimplex_p.h b/src/gui/graphicsview/qsimplex_p.h
index 5ec13c3..66ea739 100644
--- a/src/gui/graphicsview/qsimplex_p.h
+++ b/src/gui/graphicsview/qsimplex_p.h
@@ -63,7 +63,7 @@ struct QSimplexVariable
     QSimplexVariable() : result(0), index(0) {}
 
     qreal result;
-    uint index;
+    int index;
 };
 
 
@@ -95,7 +95,8 @@ struct QSimplexConstraint
     QPair<QSimplexVariable *, qreal> helper;
     QSimplexVariable * artificial;
 
-#ifdef QT_DEBUG
+    void invert();
+
     bool isSatisfied() {
         qreal leftHandSide(0);
 
@@ -119,6 +120,7 @@ struct QSimplexConstraint
         }
     }
 
+#ifdef QT_DEBUG
     QString toString() {
         QString result;
         result += QString::fromAscii("-- QSimplexConstraint %1 --").arg(int(this), 0, 16);
@@ -167,6 +169,7 @@ private:
     void combineRows(int toIndex, int fromIndex, qreal factor);
 
     // Simplex
+    bool simplifyConstraints(QList<QSimplexConstraint *> *constraints);
     int findPivotColumn();
     int pivotRowForColumn(int column);
     void reducedRowEchelon();