7
$\begingroup$

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 standarization of the LP.

So when do I use primal, and when dual simplex?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand a couple of things here. Primal simplex for LP gives the same result as dual simplex for its dual LP? But if both methods need standard form (min objective function) then how do I know if it's primal or dual? $\endgroup$ – khernik Dec 14 '13 at 22:15
  • $\begingroup$ And why adding a lot of artificial variables for the primal doesn't imply adding them for the dual? In both cases I need an identity matrix, so artificial variables would be the same, isn't that right? $\endgroup$ – khernik Dec 14 '13 at 22:17
  • $\begingroup$ In your example I get an identity matrix ($x_{5},x_{6},x_{7}$) but with two $-1$, so can't I just use primal and multiply two rows by -1? $\endgroup$ – khernik Dec 14 '13 at 22:19
  • $\begingroup$ From what I've experienced, the canonical notation is using $x$ for the primal ($u$ for its corresponding slack variable) and $y$ for the dual problem ($v$ for its corresponding slack variable). See the link I added on Strong Duality Theorem which shows that if $y^*$ is an optimal solution to the dual, then there exists an $x^*$ such that both yield the same OF value. $\endgroup$ – Joe Dec 14 '13 at 22:21
  • 1
    $\begingroup$ The number of artificial variables between the (P) and the (D) problem need not be the same I believe because the whole point of using Dual Simplex method is so you choose an IBFS (initial basic feasible solution) so there are no artificial variables. The process in general of finding such an IBFS is what makes Dual Simplex to be used less because there is an easy way if you have all $\ge$ constraints, but can be difficult (and time consuming) otherwise. I'll look into the algorithms that computers use to determine whether it is better to do Simplex or Dual Simplex--I'll keep you updated. $\endgroup$ – Joe Dec 14 '13 at 22:57
2
$\begingroup$

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.

$\endgroup$

protected by Asaf Karagila Jul 3 '14 at 9:04

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.