Simplex Algorithm
11-13-2023, 02:48 PM (This post was last modified: 11-13-2023 10:52 PM by Albert Chan.)
Post: #12
 Albert Chan Senior Member Posts: 2,637 Joined: Jul 2018
RE: Simplex Algorithm
Another optimization, remove_eq_c(a,n) now also return pivots information.
simplex_le(a, ±n) use pivots to make less slack variables (smaller identity matrix)

Code:
pivot_index(a) := BEGIN     LOCAL b := contains((a:=abs(a)), 1);     IF b THEN RETURN b END     IF (b:=max(a)) THEN b := contains(a,b) END     RETURN b; END; remove_eq_c(a, n) := BEGIN   LOCAL j,k, c := len(a[1]);   LOCAL p := makelist(n);   /* max pivots */   FOR j FROM n DOWNTO 1 DO     p[j] := k := pivot_index(suppress(a[j],c));     IF k==0 and a[j][c] THEN error(a) END     a := k ? pivot((a[j]:=a[j]/a[j][k]),j,k) : delrows(a,j);   END   return a, remove(0,p); END; simplex_le(a, dir) := BEGIN  LOCAL b, p := [];  LOCAL n := abs(dir);  IF n<len(a) THEN a,p := remove_eq_c(a,n) END  b := dim(a);  a := transpose(extend(a, identity(b(1))));  a[0] := a[b[2]];  a := transpose(delrows(a, b[2] .. b[2]+len(p)));  n := sum(b)-2 - len(p);         /* variables */  p := extend(p,range(b[2],n+1)); /* pivots */  IF dir>0 THEN a[0] := -a[0] END /* maximize */  a := simplex2(a,p,n,0,0);  IF dir>0 THEN a[1] := -a[1] END /* undo flip */  return a; END;

Benchmark example, time reduced to 0.0050 s. For this example, no slack variables!

> m := [[3,2,1,10], [2,5,3,15], [-2,-3,-4,0]]
> simplex_le(m, -2)

$$\displaystyle [ \frac{-130}{7},[\frac{15}{7},0,\frac{25}{7}],\left(\begin{array}{cccc} 1 & \frac{1}{7} & 0 & \frac{15}{7} \\ 0 & \frac{11}{7} & 1 & \frac{25}{7} \\ 0 & \frac{25}{7} & 0 & \frac{130}{7} \end{array}\right) ]$$

An Introduction to Linear Programming and Game Theory 3rd Edition, Paul R. Thie and Gerard E. Keough
Chapter 3.7 Redundant system, example 2. Again, no slack variables!

> m := [[1,2,0,1,20], [2,1,1,0,10], [-1,4,-2,3,40], [1,4,3,2,0]]
> simplex_le(m, -3)

$$[35,[5,0,0,15],\left(\begin{array}{ccccc} 0 & \frac{3}{2} & \frac{-1}{2} & 1 & 15 \\ 1 & \frac{1}{2} & \frac{1}{2} & 0 & 5 \\ 0 & \frac{1}{2} & \frac{7}{2} & 0 & -35 \end{array}\right) ]$$

We have redundant "=" constraint, net of only 2 "=" constraints.

> remove_eq_c(m, 3)

$$[\left(\begin{array}{ccccc} 0 & 1 & \frac{-1}{3} & \frac{2}{3} & 10 \\ 1 & 0 & \frac{2}{3} & \frac{-1}{3} & 0 \\ 0 & 0 & \frac{11}{3} & \frac{-1}{3} & -40 \end{array}\right) ,[2,1] ]$$

This simulate my previous version, not using pivot information.

> simplex_le(Ans[1], -inf)

$$[35,[5,0,0,15,0,0],\left(\begin{array}{ccccccc} 0 & \frac{3}{2} & \frac{-1}{2} & 1 & \frac{3}{2} & 0 & 15 \\ 1 & \frac{1}{2} & \frac{1}{2} & 0 & \frac{1}{2} & 1 & 5 \\ 0 & \frac{1}{2} & \frac{7}{2} & 0 & \frac{1}{2} & 0 & -35 \end{array}\right) ]$$

Update: HP Prime had a weird behavior list /= k interpeted as list := list * (1/k)

> m := [3.0]
> m /= 3.0
> m[1] - 1      → −3.5527136788e−15

Thus, in remove_eq_c, to turn pivot as 1. (exactly), we do a[j] := a[j]/a[j][k]
I have made changes to ftneek code as well. Now pivot of 1. is exactly 1
sol(a,v) (and others) are reverted back to original, comparing pivot 1 instead of fuzzy 1.0
 « 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)