Simplex Algorithm

[Albert Chan]

(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;