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>

0 files changed, 0 insertions, 0 deletions