A (sketchy) implementation of a cutting planes algorithm for integer linear programming

gomory_cuts.k

eps:1e-13

/ set [-eps;eps) to 0.0
nrm:{0.0+x*~~(-eps;eps)'x}

pivot: {[t;b;n;r;c]
 e:n@*&0.5<t[r;n]
 t[r]%:t[r;c];
 t[i]-:t[i:(!#t)^r;c]*\:t[r]
 t[i;c]:0.0
 (nrm t;b@<b:e,b^c;n@<n:c,n^e)}

/ requires: feasible tableau
primalpivot: {[t;b;n]
 :[^c:b@*&0>t[0;b]; :(t;b;n);]
 r:i@*>%/+t[i:1_!#t;c,0]
 :[0>t[r;c]; `err "unbounded"; pivot[t;b;n;r;c]]}

/ requires: superoptimal tableau
dualpivot: {[t;b;n]
 :[^r:i@*&0>t[i:1_!#t;0]; :(t;b;n); ]
 c:b@*<0w^%/t[r,0;b];
 :[0<t[r;c]; `err "infeasible"; pivot[t;b;n;r;c]]}

gomorycut: {[t;b;n]
 r:i@*>v-:_v:eps+t[i:1_!#t;0]
 :[(2*eps)>v i?r; :(t;b;n); ]
 t,:,(_t[r;])-t[r;]
 t:t,'((-1+#t)#0.0),1.0
 (nrm t;b;n,-1+#*t)}

/ requires: feasible tableau
primalsimplex: (primalpivot.)/

/ requires: superoptimal tableau
dualsimplex: (dualpivot.)/

/ requires: feasible tableau
cuttingplanes: (dualsimplex@gomorycut.)/primalsimplex@

A: (0  -4  1 0 0 0
    14  7 -2 1 0 0
    3   0  1 0 1 0
    3   2 -2 0 0 1)

cuttingplanes (A;1 2;3 4 5)