Simplex Algorithm
12-23-2023, 04:44 AM (This post was last modified: 12-23-2023 02:21 PM by Albert Chan.)
Post: #49
 Albert Chan Senior Member Posts: 2,637 Joined: Jul 2018
RE: Simplex Algorithm
(12-22-2023 04:07 PM)Albert Chan Wrote:  Problem seems to arise from simplex.hppgrm, not the others.

Problem is simplex() first CASE ... END, to parse user input.
Removing first CASE ... END solved crashing issue.

I simplified a bit, with extended simplex_le(a, [dir=inf], [integers]) pattern.
Slight difference, simplex() wrapper default is minimize.

Code:
// simplex(a,[dir],[integers],[binary],[unrestricted]) simplex(a):= BEGIN LOCAL (binary:=0),(integers:=0),(unrestricted:=0),(art:=0),(dir:=-inf); LOCAL b,c,d,v,bv,n,I,J; IF dim(d:=dim(a))!=2 THEN  IF d>5 THEN error(a) END;  a,dir,integers,binary,unrestricted := a;  IF (art:=abs(dir))==inf THEN art:=0 END;  d:=dim(a); END; IF unrestricted!=0 THEN  FOR I FROM len(unrestricted) DOWNTO 1 DO   b:=col(a,unrestricted[I]);   a:=ADDCOL(a,-b,unrestricted[I]+1);   n:=contains(integers,unrestricted[I]);   IF n THEN    integers:=REDIM(integers,len(integers)+1);    FOR J FROM len(integers) DOWNTO n+1 DO integers[J]:=integers[J-1]+1 END;   END;  END; d[2]+=len(unrestricted); END; c:=row(a,d[1]); a:=delrow(a,d[1]); IF binary!=0 THEN  v:=[];  FOR I FROM 1 TO len(binary) DO   n:=makelist(d[2]);   n[binary[I]]:=1;   n[0]:=1;   v:=append(v,n);  END;  a:=append(a,op(v));  d[1]+=len(binary);  integers:=UNION(integers,binary); END; b:=col(a,d[2]); a:=delcol(a,d[2]); d:=d.-1; CASE  IF art==0 OR art==d[1] THEN a:=extend(a,IDENMAT(d[1])) END;  DEFAULT   v:=append(makemat(0,art,d[1]-art),op(IDENMAT(d[1]-art)));   v:=extend(v,append(IDENMAT(art),op(makemat(0,d[1]-art,art))));   a:=extend(a,v); END; a:=ADDCOL(a,b,d[2]+d[1]+1); c:=REDIM(c,len(c)+d[1]); c[0]:=c[d[2]+1]; c[d[2]+1]:=0; a:=append(a,c); n:=art; c,v:=dim(a).-1;  /* constraints, variables */ bv:=range(v-art+1,v+1); bv:=CONCAT(bv,range(d[2]+1,v-art+1)); IF dir>0 THEN a[0]:=-a[0] END; IF integers != 0 THEN  c:=simplex_int(addartrow(a,art),bv,v,art,0,integers) ELSE  c:=simplex_core(addartrow(a,art),bv,v,art,0); END; IF dir>0 THEN c[1]:=-c[1] END; RETURN c END;

(11-22-2023 06:44 PM)Albert Chan Wrote:  > 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

> m:=[-[2,4,22],-[3,2,20],-[4,5,40],[6,5,0]]
> simplex(m); /* simplex default = minimize */

$$[\frac{320}{7},\left(\begin{array}{cccccc} 0 & 0 & 1 & \frac{6}{7} & \frac{-8}{7} & \frac{46}{7} \\ 1 & 0 & 0 & \frac{-5}{7} & \frac{2}{7} & \frac{20}{7} \\ 0 & 1 & 0 & \frac{4}{7} & \frac{-3}{7} & \frac{40}{7} \\ 0 & 0 & 0 & \frac{10}{7} & \frac{3}{7} & \frac{-320}{7} \end{array}\right) ,[3,1,2],2,\left(\begin{array}{c} \frac{20}{7} \\ \frac{40}{7} \\ \frac{46}{7} \\ 0 \\ 0 \end{array}\right) ]$$

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

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

Note that variables list now returned as a matrix.

Also, simplex() solved equality constraints using art variables, simplex_le() by variable eliminations.

test01() example:

> simplex([[1,2,0,1,20],[2,1,1,0,10],[-1,4,-2,3,40],[1,4,3,2,0]],-3)

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

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

$$[35,\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) ,[4,1],3,\left(\begin{array}{c} 5 \\ 0 \\ 0 \\ 15 \end{array}\right) ]$$
 « 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)