Post Reply 
Simplex Algorithm
11-20-2023, 02:14 AM
Post: #32
RE: Simplex Algorithm
(11-20-2023 12:18 AM)ftneek Wrote:  I just posted a new file with a fix for the simplex_int command.

> simplex_int([[2,9,1,0,40],[11,-8,0,1,82],[-3,-13,0,0,0]],[3,4],4,0,0,[1,2])
[-58,[2,4,0,92,90],...]
max=58

You beat me to it!
I also have simplex_int() bug fixed (culprit is INSERT command), and made code more compact.

Code:
// first attempt of Gomory's plane cutting algorithm
simplex_int(a,b0,v,art,ign,integers):=
BEGIN
 LOCAL b,d,x,m,I;
// Step 1: ignore integer restriction, apply simplex
 a:=simplex_core(a,b0,v,art,ign);
 ign:=art;
 art:=0;
 
 while len(x:=a[2]) DO
 
// Find non integer solution first index
  FOR I FROM 1 to len(integers) DO
   IF type(x[integers[I]])!=DOM_INT THEN break END
  END;

// STOP IF desired variables are integer
  IF I > len(integers) THEN return a END;
  
  a,b0 := a[3..4];
  d:=dim(a);
  b:=col(a,d[2]);
  
// Step 2: Detetmine constraint with largest fractional part
  m := b[1 .. d[1]-1];
  m -= floor(m);
  m := a[POS(m, max(m))];
 
// Create new constraint
  m:=floor(m)-m;
  I:=len(m)-ign;
  m:=extend(m[1..I-1], [1], m[I..0]);
  
  REDIM(a,{d(1),d(2)-1});
  ADDCOL(a,b-b,d(2)-ign);
  ADDCOL(a,b,d(2)+1-ign);
  ADDROW(a,m,d(1));
  b0:=append(b0,d(2)-ign);
  
// Step 3: solve with new constraint
  a:=simplex_core(a,b0,v+1,art,ign);
 END;
 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: 1 Guest(s)