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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Related post from OR.SEs: When should I use dual Simplex over primal Simplex? and Guidelines for Linear Optimization approaches? $\endgroup$– SecretAgentManMar 6 at 21:16
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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.
-
$\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$– khernikDec 14, 2013 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$– khernikDec 14, 2013 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$– khernikDec 14, 2013 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$– JoeDec 14, 2013 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$– JoeDec 14, 2013 at 22:57
$\begingroup$
$\endgroup$
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.
