When to use which simplex algorithm?

Question

in linear programming we use simplex method to find optimal solution. But I have also seen methods like Two Phase Method, Dual method, M-method. My question is, how do I know which method to use? For example when do I use two phase method?

Answer 1

This is a big question, but here is an overview.

Big-M and Two-Phase are not ways to find optimal solutions. They are both ways to obtain an initial feasible solution. Once you have a feasible solution, you use the regular simplex to find the optimal.

In addition, Big-M and Two-Phase are basically equivalent. They both do the same thing. The only significant difference is which is easier for you. Computers prefer Two-Phase, since Big-M requires the use of an ambiguously large $M$, and it is hard to tell a computer how to pick a 'large' number without defining what it is (is one million enough?). However, Big-M has the advantage that you don't have to use a separate phase to obtain the feasible solution.

In summary, people working by hand often prefer Big-M, and computers often prefer Two-Phase. In the end, everybody uses Simplex.

Answer 2

In practice, you use a software package that does it for you. Linear programming is done by hand only in undergraduate linear programming courses, and in that case you use whichever method the instructor tells you to use.

Answer 3

I agree with Elliot G's answer. As a complement, I would add that the dual simplex can be used to repair an existing solution.

For example, imagine you have an optimal solution, but one of the constraint changes, and your solution is no longer feasible. Instead of recomputing the solution from scratch, the dual method will repair the solution in a few iterations.

More generally, if you have a problem where you can easily find a good solution (in terms of cost) that is nearly feasible, the dual is the way to go.