Why can't we solve a LP problem just by finding all vertices of feasible region and testing the objective function at each vertex?

Question

Why can't we solve a problem just by finding all vertices of the convex polytope of feasible solutions and testing the objective function at each vertex?

My guess is basic solution of LP may not be feasible, or maybe the Time complexity of finding vertexes is as same as using the Simplex method to find the optimal solution? I am not sure. In other words, if the LP is feasible and has feasible basic solutions, are we guaranteed to find the optimal solution?

And my second question: why do we need the simplex method or some other algorithm to solve linear optimization problems?

Answer 1

If you were given the set containing every point and that set is finite, you can probably choose not to use a complex method like the Simplex method :) In such a case, one needs to ensure that each feasible point obey the constraints and record the objective function value for it, then at the end get the extreme value using the intermediate result that you have reordered in the previous step. This is quite possible when you have 2 variables because you can create a plot and identify the points that represent possible solutions visually or by performing limited computations. However, given a large number of variables, the points to examine can't be found by plotting and are not known in advance (tedious calculations aside). The Simplex method identifies the points and visits each one using an iterative mechanical process that is guaranteed to converge when the problem is formulated correctly. This makes the Simplex not only possible by hand but also well suited to be programmed and solved by a machine. It is an algorithm.

As per your second question, an correct algorithm makes solving a problem possible for any one or machine that carries the algorithm instructions. You can provide someone who has no idea about Simplex with the steps and they can calculate the optimal solution for you.

In this way, an algorithm makes solving a problem independent of the solver's skills, in addition, you are always guaranteed to get a result.

Some history for you:

Dantzig's original example was to find the best assignment of 70 people to 70 jobs. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the observable universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the simplex algorithm. The theory behind linear programming drastically reduces the number of possible solutions that must be checked.

Source: Wikipedia - Linear Programming.

What is a "Simplex" any way...?"

A simplex is the geometrical figure consisting, in N dimensions, of N+1 points (or vertices) and all their interconnecting line segments, polygonal faces, etc. In two dimensions, a simplex is a Triangle. In three dimensions, it is a Tetrahedron, not necessary the regular Tetrahedron.

Source: Numerical Recipes 3rd Edition: The Art of Scientific Computing.

Answer 2

Yes, we will find the optimal solution by checking every corner of the feasible region. The problem is exactly the computational complexity.

Suppose that the feasible region is given by a system of equations $Ax = b$ with $x\ge 0$, where $x \in \mathbb R^{100}$, $b \in \mathbb R^{50}$, and $A$ is a $50 \times 100$ matrix. Then to check every corner of the feasible region, we should try all $\binom{100}{50}= 100\,891\,344\,545\,564\,193\,334\,812\,497\,256$ choices of $50$ basic variables: first to see if they produce a feasible corner point (that is, all $50$ of those variables are nonnegative when we solve for them, setting the rest to $0$) and second to find the objective value so that we can compare.

This brute-force search will take far too long: if we check a billion points a second, we'll be done after approximately $200$ times the age of the universe so far. On the other hand, the typical linear program of this size can be solved nearly-instantly with better algorithms.

For any particular pivoting rule, there are examples like the Klee–Minty cube where the simplex method is also exponentially slow (in other words, just as bad as checking every corner). But this is very rare, and there are many results showing in various ways that on average, the simplex method will be much faster. And there are other methods with a guaranteed polynomial running time.