General relation between primal and dual solutions of LP

Question

Similar "help me solve this"-question has been asked dosens of time here. The closest things I was able to google is this post that says that "the last part is complicated". There are plenty of examples on the web, that are like "because where we have that, we can use the following trick" but I could not find any algebraic formula, or a system of equations, or a general algorithm for finding a solution of a primal problem given a solution of a dual. To be more concrete:

$$ \min c^T x \quad \text{s.t. } Ax-b=0, x\geq 0$$ and its dual $$ \max b^T y \quad \text{s.t. } c-A^Ty - s = 0, s \geq 0$$

That is clear that given the optimal $(y*, s*)$:

1. $c^T x = b^T y^*$
2. $x_i s_i = 0 $

Thank you!

but we need more and I can not find the general

Answer 1

We'll use what's called the Complementary Slackness Theorem, from here.

Theorem. Suppose a primal linear programming problem $\mathcal{P}$ and its dual $\mathcal{D}$ have solutions $x^*$ and $y^*$ respectively.

• If $x^*_j > 0$, then the $j$-th constraint of $\mathcal{D}$ is binding.
• If the $i$-th constraint of $\mathcal{P}$ is not binding, i.e. the equality does not hold, then $y^*_i = 0$.

Equivalent statements follow from contraposition.

If you want to use the theorem, then you'll first need to use your dual solution to determine which dual constraints are not binding. Those tell you which primal variables are zero. Use that information, and the fact that binding dual constraints correspond to positive primal variables. It will amount to solving a system of equations.