A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions

This paper proposes a polynomial algorithm for linear programming which is strongly polynomial for linear optimization problems $\min\{c^Tx : Ax = b, x\ge {\bf 0}\}$ having optimal solutions where each non-zero component $x_j$ belongs to an interval of the form $[\alpha_j, \alpha_j\cdot 2^{p(n)}],$ where $\alpha_j$ is some positive value and $p(n)$ is a polynomial of the number of variables. We do not impose any additional restrictions on $c$ and $A.$ This class of problems includes linear optimization problems having 0-1 optimal solutions and the Markov Decision Problem with a fixed discount factor as special cases. We also discuss a class of linear-programming relaxations of 0-1 integer problems that can be solved in strongly polynomial time by our algorithm.

Article

Download

View A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions