Post Reply 
Simplex Algorithm
11-16-2023, 07:15 PM (This post was last modified: 11-17-2023 07:24 PM by Albert Chan.)
Post: #22
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.
Find all posts by this user
Quote this message in a reply
Post Reply 


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)