Post Reply 
Simplex Algorithm
12-23-2023, 04:44 AM (This post was last modified: 12-23-2023 02:21 PM by Albert Chan.)
Post: #49
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) ]\)
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: 1 Guest(s)