QGraphicsAnchorLayout: Fix bug where simplex would return wrong results

Jan-Arve found a bug where QSimplex would return bad results in
some tight situations. The problem was triggered randomly but the
chances of appearance were higher in problems with only one
feasible solution, ie. problems what were in the boundary of
feasibility.

The QSimplex solver implements a two-phase simplex solver, the
first phase is responsible for finding a _feasible_ solution for
the problem (not the best one). The second phase starts with
the basic feasible solution (just found) and changes until
one that is _optimal_ is found.

To implement that solution we need to add artificial variables
to the original problem, before phase 1, and remove them, before
starting phase 2. Unfortunately though, there was some randomness
in the criteria used by the solver that would sometimes cause
the removal of a good variable instead of an artificial one,
between the phases.

With one good variable missing, the solver would also miss an
important restriction, without such, it would push the objective
function too far, thus returning a "wrong" result.

This commit adds a tie-breaker condition to the pivot row logic
to ensure the artificial variables are removed before the "good"
ones.

Signed-off-by: Eduardo M. Fleury <eduardo.fleury@openbossa.org>
Reviewed-by: Artur Duque de Souza <artur.souza@openbossa.org>

1 files changed, 38 insertions, 0 deletions

diff --git a/src/gui/graphicsview/qsimplex_p.cpp b/src/gui/graphicsview/qsimplex_p.cpp
index 7de7da0..94eb5c0 100644
--- a/src/gui/graphicsview/qsimplex_p.cpp
+++ b/src/gui/graphicsview/qsimplex_p.cpp
@@ -273,6 +273,25 @@ bool QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints)
     // solution for the first problem, thus we don't need them
     // anymore.
     clearColumns(firstArtificial, columns - 2);
+
+    #ifdef QT_DEBUG
+    // Ensure that at the end of the simplex each row should either:
+    //  - Have a positive value on the column associated to its variable, or
+    //  - Have zero values in all columns.
+    //
+    // This avoids a regression where restrictions would be lost
+    // due to randomness in the pivotRowForColumn method.
+    for (int i = 1; i < rows; ++i) {
+        int variableIndex = valueAt(i, 0);
+        if (valueAt(i, variableIndex) > 0)
+            continue;
+
+        for (int j = 1; j < columns; ++j) {
+            Q_ASSERT(valueAt(i, j) == 0);
+        }
+    }
+    #endif
+
     return true;
 }
 
@@ -371,6 +390,23 @@ int QSimplex::findPivotColumn()
     return minIndex;
 }
 
+/*!
+  \internal
+
+  For a given pivot column, find the pivot row. That is, the row with the
+  minimum associated "quotient" where:
+
+  - quotient is the division of the value in the last column by the value
+    in the pivot column.
+  - rows with value less or equal to zero are ignored
+  - if two rows have the same quotient, lines are chosen based on the
+    highest variable index (value in the first column)
+
+  The last condition avoids a bug where artificial variables would be
+  left behind for the second-phase simplex, and with 'good'
+  constraints would be removed before it, what would lead to incorrect
+  results.
+*/
 int QSimplex::pivotRowForColumn(int column)
 {
     qreal min = qreal(999999999999.0); // ###
@@ -385,6 +421,8 @@ int QSimplex::pivotRowForColumn(int column)
         if (quotient < min) {
             min = quotient;
             minIndex = i;
+        } else if ((quotient == min) && (valueAt(i, 0) > valueAt(minIndex, 0))) {
+            minIndex = i;
         }
     }