Simplex Algorithm

[Albert Chan]

(11-12-2023 01:44 AM)ftneek Wrote:  Thank you for the benchmarks. Now that I thought about it a little, since the simplex_le() method assumes the n constraints are <=, we know we need to add n slack variables. Thus if we make a list of the last n column indices (not counting/using b column) to use as initial basic variables, we can call simplex2() directly as we know all the arguments. This should speed up simplex_le() a bit.

Nice idea. Updated to simplex_le latest version.

< a := simplex(a);
> a := simplex2(a,range(b(2),sum(b)-1),sum(b)-2,0,0);

range(...) are column location of 1's of identity matrix.
variables = rows + cols - 2 = sum(b) - 2
No artificial variables, thus the doubled 0's

(11-11-2023 04:54 AM)ftneek Wrote:  Note I think there is a bug with my wrapper simplex() method, sometimes the artificial variable counter is not updated. So far the bad effect is for some systems with artificial variables. But also note that simplex2() works as intended with the correct arguments. I need to determine a correct (and hopefully efficient) way to identify artificial variables without false positives, as that would have a bad effect for systems without artificial variables.

Call simplex2 directly, simplex_le is more robust. Run faster too (was 0.0077 s)

> m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,0]]
> time(simplex_le(m, -2))                        → 0.0058

Just curious, if simplex2 can assume no artificial variables, can it speed up more?