19

It is not true that the Two-Phase methods requires Simplex iterations, it is just the common way to do it. Let's assume we have a linear program with $n$ variables and $m$ constraints. Step 1) Convert this LP into standard form by splitting all unbounded variables into two $\geq 0$ variables, making sure $b$ is non-negative (by multiplying the rows that ...


17

LP is solvable in polynomial time. The polynomial depends not only on problem size, but also the size of numbers of the input matrix. The standard proof is using the ellipsoid method. Of course, the proof uses exact arithmetic, as any complexity proof would. That method isn't practical though. It is unknown if LP is strongly polynomial. In practice you can ...


17

Let's start with the easy one: Ellipsoid Method Never use it. Even though it might appear efficient in the complexity-theory sense, it performs terrible and suffers heavily from numerical issues. Primal Simplex Mostly studied for historical interest, but there are some cases where it might outperform dual simplex (when the basis matrix in the primal revised ...


14

Point 2 of "What we know" is incorrect: the ellipsoid method does not require a feasible starting point. As I stated in a comment earlier, in Khachiyan (1980) it is proven that "determining the compatibility of a system of linear inequalities in $\mathbb{R}^n$ belongs to the class of $P$ of problems". In Section 6 of the paper, Khachiyan shows that if you ...


9

Bob Bixby (as just one representative of many computational guys) talks regularly about progress in LP and MIP solving; for the 50th anniversary issue of "Operations Research" he wrote an article on history and progress in LP solving that also contains perspectives on different algorithms (here), his general message is: these algorithms became vastly more ...


2

There are LP algorithms which do not require feasible start, and which do not use a Phase I / Phase II method. These algorithms are based on the "Homogeneous Self-Dual Embedding" (HSDE) approach of Ye, Todd, and Mizuno (Mathematics of Operations Research, Vol. 19, No. 1 (Feb., 1994), pp. 53-67). For suitable parameter choices, a path-following HSDE algorithm ...


Only top voted, non community-wiki answers of a minimum length are eligible