I'm surprised this list doesn't include interior point methods, which (unlike the simplex method) demonstrate that a large class of nonlinear optimization problems (namely, convex SDPs) can be solved in polynomial time.