Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am studying linear programming and I came across primal-dual algorithm in Linear Programming. I understood it but I am unable to understand why there is a need to calculate a dual, if problem can be solved in primal space. Are there some inherent advantages?

I am fine with the proofs of weak duality and strong duality but I just wonder that what is the reason.

Any help appreciated.

share|improve this question
    
A related question from the theoretical computer science perspective. –  Artem Kaznatcheev Oct 15 '13 at 21:39
add comment

2 Answers 2

up vote 5 down vote accepted

Here are some uses of the dual problem.

  1. Understanding the dual problem leads to specialized algorithms for some important classes of linear programming problems. Examples include the transportation simplex method, the Hungarian algorithm for the assignment problem, and the network simplex method. Even column generation relies partly on duality.
  2. The dual can be helpful for sensitivity analysis. Changing the primal's right-hand side constraint vector or adding a new constraint to it can make the original primal optimal solution infeasible. However, this only changes the objective function or adds a new variable to the dual, respectively, so the original dual optimal solution is still feasible (and is usually not far from the new dual optimal solution).
  3. Sometimes finding an initial feasible solution to the dual is much easier than finding one for the primal. For example, if the primal is a minimization problem, the constraints are often of the form $A {\bf x} \geq {\bf b}$, ${\bf x} \geq {\bf 0}$, for ${\bf b} \geq {\bf 0}$. The dual constraints would then likely be of the form $A^T {\bf y} \leq {\bf c}$, ${\bf y} \geq {\bf 0}$, for ${\bf c} \geq {\bf 0}$. The origin is feasible for the latter problem but not for the former.
  4. The dual variables give the shadow prices for the primal constraints. Suppose you have a profit maximization problem with a resource constraint $i$. Then the value $y_i$ of the corresponding dual variable in the optimal solution tells you that you get an increase of $y_i$ in the maximum profit for each unit increase in the amount of resource $i$ (absent degeneracy and for small increases in resource $i$).
  5. Sometimes the dual is just easier to solve. Aseem Dua mentions this: A problem with many constraints and few variables can be converted into one with few constraints and many variables.
share|improve this answer
add comment

Duality provides a lot of computational advantage in a problem with lesser number of variables and a multitude of constraints.

Take the example of simplex, you will notice it is much easier to deal with lesser basic variables.

Economists have an interpretation (wiki article has a section) that defines the dual variables nicely. On another front, duality gives a better understanding of the situation and may offer certain more perspectives.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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