Simplex Algorithm
11-22-2023, 06:44 PM (This post was last modified: 11-24-2023 12:40 PM by Albert Chan.)
Post: #42
 Albert Chan Senior Member Posts: 2,636 Joined: Jul 2018
RE: Simplex Algorithm
I added another option to simplex_le, to handle integer programming problems.
Default is maximize (no '=' constraint), and variables not needed to be integers.

simplex_le(a, [k=inf], [z=[]])

Code:
// s.t.  x,  y ≥ 0 //      2x +4y ≥ 22 //      3x +2y ≥ 20 //      4x +5y ≥ 40 // min  6x +5y = z

> m:=[-[2,4,22],-[3,2,20],-[4,5,40],[6,5,0]]
> simplex_le(m, -inf)

[320/7 ... [20/7,40/7,46/7,0,0]]

What if (x,y) required to be non-negative integer? (variables x = 1st, y = 2nd)

> simplex_le(m, -inf, [1,2])

[47 ... [2,7,10,0,3]]

min(z) is higher as expected, solution is x=2, y=7

I am posting only simplex_le wrapper, the rest is from previous post.
With this update, all test_cases can be done with simplex_le()
Code:
simplex_le(a) := BEGIN  LOCAL d,b,x,v,I,(p:=[]),(k:=inf),(z:=[]);  IF dim(dim(a))!=2 THEN a,k,z := a END  IF abs(k)<len(a) THEN a,p:=remove_eq_c(a,k) END  d := dim(a);  a := transpose(extend(a,identity(d[1])));  a[0] := a[d[2]];  a := transpose(delrows(a, d[2] .. d[2]+len(p)));  IF k==0 THEN return a END  v := sum(d)-2 - len(p);         // variables  p := extend(p,range(d[2],v+1)); // pivots  IF k>0 THEN a[0]:=-a[0] END     // maximize  a := simplex_core(a,p,v,0,0);  WHILE 1 DO     // Gomory's plane cutting algorithm   IF len(x:=a[0])==0 THEN break END // no solution   IF len(x[1])>1 THEN break END     // inf solution   FOR I FROM 1 to len(z) DO    IF type(x[z[I]])!=DOM_INT THEN break END   END;   IF I>len(z) THEN break END        // one solution // Detetmine constraint with largest frac_part   a,p,I := tail(a);   d:=dim(a);   b:=col(a,d[2]);   b-=floor(b);   b[d[1]]:=0;   x:=a[POS(b, max(b))]; // Create new constraint   x:=floor(x)-x;   x[d[2]+1]:=x[d[2]];   x[d[2]]:=1;   p[d[1]]:=d[2]; // pivot on 1 // solve with new constraint   ADDCOL(a,b-b,d[2]);   ADDROW(a,x,d[1]);   a:=simplex_core(a,p,v,0,0);   a[4]+=I;       // pivot1 calls  END;  IF k>0 THEN a[1]:=-a[1] END     // undo flip  RETURN a; END;
 « 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: 3 Guest(s)