Invalid solution if artificial variables are still in basis after phase one

[chatziko]

A problem in the current implementation: after phase 1 an artificial variable can still be in the basis (with value 0). Such variables need to be driven out of the basis before starting phase 2, otherwise they might become non-zero in phase 2, which will make the solution invalid.

This is explained here:

Drive artificial variables out of the basis: If l-th basic variable is artifi­cial examine l-th row of B^−1 A. If all elements = 0 ⇒ row redundant. Otherwise pivot with non-0 element.

The following program demonstrates this issue. The returned solution violates the constraints:

A = [
    1//1     1        0        0        0;
    0        0        1        1        0;
    1        0        1        0        0;
    0        1        0        1        1;
    0        0        0        0        1;
];
c = vec([0//1        1        1        0        0]);
b = vec([1//2 1//2 1 1 1 ]);

(status,sol) = simplex(c, A, b); # already in standard form
println(A * sol == b);   # prints false, should be true

[IainNZ]

Interesting, I'd accept a fix + a test for this use case! It should be necessary to explicitly drive all the artificial variables at, iirc, but I'm clearly missing a step to make it work. You can see the handling of cB partially addresses this in the phase-switching code.

[chatziko]

I'm actually not using your julia code directly, but a C++ port of it included in my libqif library (here) (using a patched version of armadillo that works with rationals).

I've fixed the issue by driving out the artificial variables, the corresponding lines are here. It should be easily transferable back to julia, I'll do it if I find some time.