Simplex Algorithm

[Albert Chan]

(11-22-2023 10:10 PM)Albert Chan Wrote:  > simplex_le([[2,3,4,6],[4,2,5,5],[22,20,40,0]],∞,[1,2,3])

\([40 \;\cdots \left(\begin{array}{cc}
0 & 0 \\
2 & 0 \\
0 & 1 \\
0 & 2 \\
1 & 0
\end{array}\right) ]\)

simplex_le() simply return infinite solutions (integers or not).
It is just luck that above variables happened to be integers.

This fixed it.
simplex_le(), before patch

Code:

 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]][1])!=DOM_INT THEN break END
  END;
  IF I>len(z) THEN break END        // one solution

simplex_le(), after patch

Code:

 WHILE len(x:=a[0]) DO  // Gomory's plane cutting algorithm
  FOR b FROM 1 to len(x[1]) DO
   FOR I FROM 1 to len(z) DO
    IF type(x[z[I]][b])!=DOM_INT THEN break END
   END;
   IF I>len(z) THEN break END // solution
  END;
  IF I>len(z) THEN break END  // solution

break 2 unable to get out of WHILE loop (why?), thus the ugly multiple breaks.
If there is a better way, don't hesitate to post!