Simplex Algorithm
11-21-2023, 02:05 PM (This post was last modified: 11-21-2023 05:03 PM by Albert Chan.)
Post: #39
 Albert Chan Senior Member Posts: 2,636 Joined: Jul 2018
RE: Simplex Algorithm
(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?
 « Next Oldest | Next Newest »

 Messages In This Thread Simplex Algorithm - ftneek - 11-11-2023, 11:21 PM RE: Simplex Algorithm - Albert Chan - 11-11-2023, 11:51 PM RE: Simplex Algorithm - Albert Chan - 11-12-2023, 12:38 AM RE: Simplex Algorithm - Albert Chan - 11-12-2023, 05:11 PM RE: Simplex Algorithm - ftneek - 11-12-2023, 05:40 PM RE: Simplex Algorithm - Albert Chan - 11-13-2023, 02:48 PM RE: Simplex Algorithm - ftneek - 11-12-2023, 12:00 AM RE: Simplex Algorithm - ftneek - 11-12-2023, 01:44 AM RE: Simplex Algorithm - Albert Chan - 11-12-2023, 11:04 PM RE: Simplex Algorithm - ftneek - 11-13-2023, 01:51 AM RE: Simplex Algorithm - Albert Chan - 11-12-2023, 08:46 PM RE: Simplex Algorithm - ftneek - 11-12-2023, 10:09 PM RE: Simplex Algorithm - ftneek - 11-13-2023, 05:34 PM RE: Simplex Algorithm - Albert Chan - 11-13-2023, 10:46 PM RE: Simplex Algorithm - Albert Chan - 11-14-2023, 02:25 AM RE: Simplex Algorithm - ftneek - 11-14-2023, 06:24 AM RE: Simplex Algorithm - Albert Chan - 11-14-2023, 09:23 AM RE: Simplex Algorithm - ftneek - 11-14-2023, 10:39 AM RE: Simplex Algorithm - Albert Chan - 11-15-2023, 04:36 PM RE: Simplex Algorithm - ftneek - 11-15-2023, 05:58 PM RE: Simplex Algorithm - Albert Chan - 11-16-2023, 11:42 AM RE: Simplex Algorithm - Albert Chan - 11-16-2023, 07:15 PM RE: Simplex Algorithm - ftneek - 11-17-2023, 07:47 AM RE: Simplex Algorithm - Albert Chan - 11-17-2023, 11:04 AM RE: Simplex Algorithm - ftneek - 11-18-2023, 01:27 AM RE: Simplex Algorithm - ftneek - 11-18-2023, 10:31 PM RE: Simplex Algorithm - Albert Chan - 11-19-2023, 12:57 AM RE: Simplex Algorithm - ftneek - 11-19-2023, 07:05 AM RE: Simplex Algorithm - Albert Chan - 11-19-2023, 04:58 PM RE: Simplex Algorithm - Albert Chan - 11-20-2023, 06:12 PM RE: Simplex Algorithm - ftneek - 11-21-2023, 08:36 AM RE: Simplex Algorithm - Albert Chan - 11-21-2023 02:05 PM RE: Simplex Algorithm - ftneek - 11-19-2023, 08:02 PM RE: Simplex Algorithm - ftneek - 11-20-2023, 12:18 AM RE: Simplex Algorithm - Albert Chan - 11-20-2023, 02:14 AM RE: Simplex Algorithm - ftneek - 11-20-2023, 09:02 AM RE: Simplex Algorithm - Albert Chan - 11-20-2023, 11:42 AM RE: Simplex Algorithm - Albert Chan - 11-20-2023, 03:34 PM RE: Simplex Algorithm - ftneek - 11-20-2023, 07:52 PM RE: Simplex Algorithm - Albert Chan - 11-21-2023, 05:58 PM RE: Simplex Algorithm - Albert Chan - 11-21-2023, 11:20 PM RE: Simplex Algorithm - Albert Chan - 11-22-2023, 06:44 PM RE: Simplex Algorithm - Albert Chan - 11-22-2023, 10:10 PM RE: Simplex Algorithm - Albert Chan - 12-24-2023, 03:46 PM RE: Simplex Algorithm - ftneek - 12-24-2023, 07:32 PM RE: Simplex Algorithm - Albert Chan - 12-24-2023, 08:05 PM RE: Simplex Algorithm - ftneek - 11-23-2023, 01:23 AM RE: Simplex Algorithm - Albert Chan - 11-23-2023, 06:35 AM RE: Simplex Algorithm - ftneek - 12-22-2023, 07:38 AM RE: Simplex Algorithm - Albert Chan - 12-22-2023, 04:07 PM RE: Simplex Algorithm - ftneek - 12-22-2023, 07:28 PM RE: Simplex Algorithm - Albert Chan - 12-23-2023, 04:44 AM RE: Simplex Algorithm - ftneek - 12-23-2023, 07:46 AM RE: Simplex Algorithm - Albert Chan - 12-23-2023, 10:23 AM RE: Simplex Algorithm - ftneek - 12-23-2023, 09:30 PM RE: Simplex Algorithm - ftneek - 01-07-2024, 02:40 AM

User(s) browsing this thread: 1 Guest(s)