0
$\begingroup$

Our strong duality theorem is:

If both the primal LP and the dual LP have feasible solutions, then they both have optimal solutions, and for any primal optimal solution $x$ and dual optimal solution $y$, we have $c^Tx=b^Ty$.

Can this be written as:

Both the primal LP and the dual LP have feasible solutions $\iff$ then they both have optimal solutions $\iff$ for any primal optimal solution $x$ and dual optimal solution $y$, we have $c^Tx=b^Ty$.

$\endgroup$
0
$\begingroup$

No. While the first equivalence could be proven, the last equivalence does not hold. Given an appropriate formulation of the primal and dual linear program, the last statement: "for any primal optimal solution $x$ and dual optimal solution $y$, we have $c^Tx=b^Ty$" is always true, even if the primal linear program is infeasible. Indeed, it is a consequence of the strong duality theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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