Simplex Algorithm

[Albert Chan]

(11-21-2023 08:36 AM)ftneek Wrote:  Reminder, simplex_core is able to continue iteration on a tableau from any stage.

I don't know this requirement. Easy fix. '+' = added, '-' = subtracted

simplex() Wrote:IF c > art-(n-=1) THEN continue END
+ IF art THEN
+ a[c+2]:=artrow(v+1,art)-sum(a[POS(bv,J)],J,v+1-art,v);
+ END
RETURN simplex_core(a,bv,v,art,0)

simplex_core() Wrote:- 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;

For efficiency sake, simplex_core assumed pivots are all 1's
This is why my version 4 get 20% speedup running test_simplex().

We can add another wrapper to turn pivots to 1, say, call this simplex2

Code:

simplex2(a,bv,v,art,ign):=
BEGIN
 LOCAL I;
 FOR I FROM 1 to len(bv) DO a:=pivot1(a,I,bv[I]) END
 RETURN simplex_core(a,bv,v,art,ign)
END;

ftneek Wrote: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}]

> simplex2([[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}]

These make simplex_core() restartable at any stage. And, run very fast.

BTW, is above tableau in standard form? Should all constraints be negated?