Post Reply 
Simplex Algorithm
11-22-2023, 06:44 PM (This post was last modified: 11-24-2023 12:40 PM by Albert Chan.)
Post: #42
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;
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: 3 Guest(s)