General relation between primal and dual solutions of LP

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

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$.

• Thank you! Right, but isn't it same as "2." in the question body? What is gives us is: 1) $c^t x = C$, where $C$ is some constant + 2) information on which components of $x$ are greater then zero from dual slack variables. That does not seem to be enough to uniquely identify $x$, right? – Ben Usman Jul 13 '17 at 6:21
• Ah! I guess I got it! We can additionally use $Ax=b$ - should it be enough now? And if it wasn't equality, but inequality, we would take rows from this inequality that correspond to $y_j \neq 0$, right? – Ben Usman Jul 13 '17 at 6:25
• Would it be enough now? I mean, if we have just $k$ equality constraints on $x$ of dim $n$ ($A$ is $k \times n$), +1 equality from dual=primal, and assume that only $m$ of $n$ slack variables $s_j$ turn out to be zero, so we have to estimate $n-m$ values, then what if $k+1 < n-m$? – Ben Usman Jul 13 '17 at 6:34