Simplex Algorithm

[ftneek]

(11-20-2023 06:12 PM)Albert Chan Wrote:  

(11-19-2023 04:58 PM)Albert Chan Wrote:  I am not convinced that -1 slack variable will cause problem.

I am now convniced that it will not cause problem, even if scaled.
.
.
.
I am reverting back to the fast method, without (again) canonicalize all pivots.
And, no need to fill artrow, even in simplex_core(), it handles this internally

simplex(m, [art=0]) ≡ simplex_core(m, pivots, variables, art, 0)

I uploaded a new file with the infinite solution correction you mentioned. But I wasn't able to include this portion of code in simplex_core yet.

Code:

IF art THEN /* add artrow */
 a:=append(a,artrow((c:=len(a[1])),art));
 a[0]-=sum(a[POS(bv,J)],J,c-art,c-1);
END;

I added a new test 4. It is an example of input that is currently allowed by simplex_core, but the command didn't work when I tried your version, because the -1's are not being pivoted on. This what I mean by limiting the number of ways you can input a system and arrive at the same solution.

Current simplex_core
> simplex_core([[2,4,-1,0,0,22],[3,2,0,-1,0,20],[4,5,0,0,-1,40],[6,5,0,0,0,0]],{3,4,5},5,0,0)
[320/7,[20/7,40/7,46/7,0,0],[[0,0,1,6/7,-8/7,46/7],[1,0,0,-5/7,2/7,20/7],[0,1,0,4/7,-3/7,40/7],[0,0,0,10/7,3/7,-320/7]],{3,1,2}]

Your version
> simplex_core([[2,4,-1,0,0,22],[3,2,0,-1,0,20],[4,5,0,0,-1,40],[6,5,0,0,0,0]],{3,4,5},5,0,0)
[0,[0,0,0,0,0],[[2,4,-1,0,0,22],[3,2,0,-1,0,20],[4,5,0,0,-1,40],[6,5,0,0,0,0]],{3,4,5}]

Also, appending an artificial row should not happen inside simplex_core, at least the current way you propose. Reminder, simplex_core is able to continue iteration on a tableau from any stage. For sensitivity analysis, we may consider what happens to the solution if we add a constraint. But just adding a row/bv to the original matrix and applying simplex algorithm again can be expensive for large systems. Instead, we insert the row into the final tableau and continue computation from there. This an example of where your current implementation is wrong, if you are going to set up the artificial row, it should be offset by ign.