QGAL (QSimplex): Add constraints simplification

Now the simplex solver is able to remove fixed variables from its
constraints as to improve its running time.

The simplification consists of two actions that are done iteratively
until no possible changes exist:

 1st) Look for constraints of type Var == Constant
      Save constant as the trivial value of Var
 2nd) Substitute known results in existing constraints

Signed-off-by: Eduardo M. Fleury <eduardo.fleury@openbossa.org>
Reviewed-by: Caio Marcelo de Oliveira Filho <caio.oliveira@openbossa.org>

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();