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>

1 files changed, 5 insertions, 2 deletions

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