Simplex Algorithm
11-16-2023, 07:15 PM (This post was last modified: 11-17-2023 07:24 PM by Albert Chan.)
Post: #22
 Albert Chan Senior Member Posts: 2,636 Joined: Jul 2018
RE: Simplex Algorithm
ftneek Wrote:[minRatio] algorithm uses this pivoting rule.
Quote:Step 4: Determine the variables xin to ENTER and xout to EXIT BVs.
-> Select Most negative cj <0, corresponding column variable -> xin to ENTER.
->Compute Ratios of (RHS entries bj>=0)/(Entries of that aij>0) -> Lowest Ratio -> Corresponding Row BV: xout to EXIT.
-> Go to step 5 to continue.

Selection is too restrictive. Especially since aij, bj can be anything.

It is possible code never get a chance of making ratios --> POS return 0
In HP Prime, A[0] = A last element, outside valid pivot selection area.

This is the reason canonicalForm() may get into trouble of divide by 0.
Yes, it patched with check aijā 0, but still just a patch.
With a correct minRatio, this should never happen!

Why? Because of added slack/art variables, equation rows are independent.
It is impossible to get variables row of all zeros, even after row operations.
And, slack/art variables are initially setup with 1's, a positive number.
If some other variables are negative, any pivoting will turn them positive.
In other words, positive coefficient(s) are always available, for the picking.

So, what should be the right algorithm for minRatio?
I think maxRatio algorithm is perfect for this! (as in min(x) = -max(-x))
It really is doing maximum ratio, does not care for sign of ratios!
Note: maxRatio is a piece of code inside complex2, not itself a function.

Bonus: for valid setup, canonicalForm() will never get a divide-by-0.
Conversely, divide-by-0 implied matrix was setup wrong, and should be stopped.

Note: I just posted latest complex_le code, thus not added here.
Code:
#cas simplex(a):= BEGIN LOCAL b0,d,v,ign,l,column,art,n,l1,l2,I,J; b0:={}; d:=dim(a); v:=d(2)-1; art:=0; ign:=0; n:=1; FOR I FROM 1 TO d(1)-1 DO  l:=row(a,I);  FOR J FROM v downto 1 DO   IF len(b0)-d(1)+n==0 THEN    BREAK 2;   END;   column:=col(a,J);   l1:=abs(trn(column));   IF NOT contains(b0,J) AND l(J)-1==0 THEN // This should detect artificial variables |last row|= sqrt(numColumns-1 for b,-2 for x1 x2)    IF column(d(1))-1==0 AND l1-sqrt(2)==0 AND abs(trn(col(a,d(1))))-sqrt(v-2)<=0 THEN     b0:=CONCAT(b0,{J});     art:=art+1;     n:=2;     BREAK;    ELSE // If theres only 1 or 2 1's in a column, we can use it as initial bv.     IF l1-1==0 OR l1-sqrt(2)==0 THEN      b0:=CONCAT(b0,{J});      BREAK;     END;    END;   END;  END; END; RETURN simplex2(a,b0,v,art,ign); END; simplex2(a,b0,v,art,ign):= BEGIN LOCAL aij,b,bv,c,cj,cmin,bmin,d,n,m,m1,xin,xout,z,l1,l2,I; bv:=b0; d:=dim(a); m:=canonicalForm(a,bv); b:=mat2list(col(m,d(2))); c:=SUPPRESS(row(m,d(1)),d(2)-ign,d(2)); cmin:=MIN(c); n:=1+(art>0); b:=SUPPRESS(b,d(1)-n+1,d(1)); bmin:=MIN(b); // Step 2: If all ci are =0, go to Step 6 WHILE cmin<0 OR bmin<0 DO // Step 3: For any ci < 0, check for unbounded solution  FOR I FROM 1 TO (d(2)-1-ign) DO   IF c(I) < 0 AND MAX(col(m,I))<=0 THEN // UNBOUNDED SOLUTION    RETURN [-inf,[],m];   END;  END; // Step 4: Determine the bv to enter and exit  xin:=POS(c,cmin);  b:=mat2list(col(m,d(2)));  xout:=minRatio(col(m,xin),b,n); // Step 5: Canonical reduction with new bv  IF bv[xout]!=xin THEN   bv[xout]:=xin;   m:=canonicalForm(m,bv);   c:=SUPPRESS(row(m,d(1)),d(2)-ign,d(2));   IF (cmin:=MIN(c))<0 THEN continue END;  END;  IF art>0 THEN   IF m(d(1),d(2))!=0 THEN // w?0? NO SOLUTION / EMPTY FEASIBLE REGION    RETURN ["No Solution: empty feasible region (w?0)",[],m];   END;   m:=delrows(m,d(1));   n:=1;   ign:=art;   art:=0;   d=dim(m);   c:=SUPPRESS(row(m,d(1)),d(2)-ign,d(2));   cmin:=MIN(c);  ELSE   b:=mat2list(col(m,d(2)));   b:=SUPPRESS(b,d(1));   bmin:=MIN(b); // IF ?bi<0, use Dual Simplex   IF bmin<0 THEN    FOR I FROM 1 TO len(b) DO     IF b(I)<0 AND MIN(SUPPRESS(row(m,I),d(2)-ign,d(2)))>=0 THEN      RETURN ["No Solution",[],m];     END;    END;    xout:=POS(b,bmin);        bv[xout]:=minRatio(-m[xout],c,0);   /* max ratio */    m:=canonicalForm(m,bv);    c:=SUPPRESS(row(m,d(1)),d(2)-ign,d(2));    cmin:=MIN(c);   END;  END; END; // Step 6: ci,bi=0 optimum achieved l1:=sol(m,v); m1:=m; z:=-m(d(1),d(2)); c:=SUPPRESS(row(m1,d(1)),d(2)-ign,d(2)); FOR I FROM 1 TO len(c) DO  IF c(I)==0 AND NOT contains(bv,I) AND abs(trn(col(m1,I)))!=1 AND abs(trn(col(m1,I)))!=0 THEN   xin:=I;   b:=mat2list(col(m1,d(2)));   xout:=minRatio(col(m1,xin),b,1);   bv[xout]:=xin;   m1:=canonicalForm(m1,bv);   l2:=sol(m1,v); // IFINITE SOLUTIONS   IF l1==l2 THEN BREAK END   RETURN [z,l2-(l2-l1)*t,m];  END; END; // UNIQUE SOLUTION RETURN [z,l1,m]; END; sol(a,v):= BEGIN  LOCAL x,b,c, j,k;  x:=makelist(v); /* all zeroes */  b:=col(a,0);    /* last column */  FOR j FROM 1 TO v DO   IF abs(trn(c:=col(a,j)))!=1 THEN continue END   IF (k:=contains(c,1))==0 THEN continue END   IF b[k] THEN x[j]:=b[k]; b[k]:=0 END  END;  RETURN x; END; canonicalForm(M, BV):= BEGIN  LOCAL I, J, P;  FOR I FROM 1 TO len(BV) STEP 1 DO   IF (P:=M[I][J:=BV[I]])==0 THEN error(M) END   M:=pivot((M[I]:=M[I]/P),I,J)  END;  RETURN M; END; minRatio(a,b,n):=  BEGIN  LOCAL i, ratio, (j:=0), (minratio:=inf);  FOR i FROM 1 TO len(b)-n DO   IF a[i]<=0 THEN continue END   ratio:=b[i]/a[i];   IF minratio>ratio THEN minratio:=ratio; j:=i END  END;  RETURN j END;

Update:
1. skip some canonicalForm() calculations, if we know it will just return itself.
2. unbound solution, return [-inf, [], m], to signal no minimum.
 « 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: 2 Guest(s)