We introduce a new variant of Chubanov’s method for solving linear homogeneous systems with positive variables. In the \BP\ we use a recently introduced cut in combination with Nemirovski’s Mirror-Prox method. We show that the cut requires at most $O(n^3)$ time, just as Chabonov’s cut. In an earlier paper it was shown that the new cuts are at least as sharp as those of Chubanov. Our \MMA\ is in essence the same as Chubanov’s \MA, except that it uses the new \BP\ as a subroutine. The new method has $O(n^{4.5}L)$ time complexity. Some computational results are presented in comparison with Gurobi.
Citation
Nat. Univ. Singapore/ TU Delft June 2020