Simplex algorithm — primal or dual?

Question

As far as I know there are two simplex algorithms – primal and dual. They have different halting criteria etc. Before using simplex I have to make a standardization of the LP. So, when do I use primal, and when dual simplex?

Answer 1

In general, if the primal problem is too difficult to solve (i.e. put into standard form and use the Simplex method), then likely it is easier to solve the dual problem. If you have to add a lot of artificial variables for solving the primal, then you are probably better off writing the dual of the LP and solving it using the Dual Simplex method. Keep in mind that when using Dual Simplex, you're sort of solving the primal within the dual due to complementary slackness and the Strong Duality Theorem, which is awesome. Note that this theorem has a necessary condition that the LP is bounded and has a feasible solution to it. See the related question here regarding solving the primal within the dual. Here is also a reference on the Strong Duality Theorem.

Consider the problem below (borrowed from here) for a good example of when to use dual simplex. $$\mathrm{Min} \ Z = 2x_1 + 3x_2 + 4x_3 + 5x_4 \tag{0}$$ s.t. $$x_1 - x_2 + x_3 - x_4 \ge 10 \tag{1}$$ $$x_1 -2x_2 + 3x_3 -4x_4 \ge 6 \tag{2}$$ $$3x_1 -4x_2 + 5x_3 -6x_4 \ge 15 \tag{3}$$ $$x \ge 0 \tag{4}$$

If we instead had all inequalities that were $\le$, the normal Simplex method would work great. The two-phase method would be a bit of work. However, since all of the coefficients in our OF (objective function--namely, Z here) are all non-negative, we can use the Dual Simplex without any problems.

Answer 2

Adding to what was said above, the dual simplex algorithm is also very useful in cases where you might need to $\textbf{insert new constraints}$ as you go.

Using the "regular" simplex method, you would have to solve the problem from the beginning every time you introduce a new constraint, and using the dual you will only have to make some (relatively) minor modifications. See example here.

BTW, using the dual simplex method is equivalent to taking the dual and then using the simplex method on the dual. See example here.