Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different:

Weak duality: If $\bar{x}$ is a feasible solution to $(P)$ and $\bar{y}$ is a feasible solution to $(D)$, then:

  1. $c^T \bar{x} \le b^T\bar{y}$
  2. if equality holds in the above inequality, then $\bar{x}$ is an optimal solution to $(P)$ and $\bar{b}$ is an optimal solution to $(D)$.

Strong duality: If there exists an optimal solution $x'$ for $(P)$, then there exists an optimal solution $y'$ for $(D)$ and the value of $x'$ in $(P)$ equals the value of $y'$ in $(D)$.

Are these two statements not saying the same thing? In other words, isn't the second statement (2.) in definition of Weak duality saying the same thing as strong duality?

Let's say we are given an LP $(P)$ and we find a dual $(D)$. Then can the same dual be used to deduce either strong duality or weak duality?

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

Weak duality is a property stating that any feasible solution to the dual problem corresponds to an upper bound on any solution to the primal problem. In contrast, strong duality states that the values of the optimal solutions to the primal problem and dual problem are always equal. Was this helpful enough?

share|improve this answer
    
Oh so its strong in the sense that it gives a stronger statement: one just gives an inequality while the other gives a equality? –  mtahmed Nov 18 '12 at 9:43
2  
Yes, exactly. The names are good hints for that. –  Ilan Kom Nov 18 '12 at 10:00
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.