Complementary slackness states that if $x$ and $y$ are solutions to primal and dual respectively, then they satisfy: $x$ and $y$ are optimal solutions to primal and dual respectively if and only if they are feasible to primal and dual respectively and they satisfy the complementary slackness condition.
My professor claimed that it follows that: for any solution $x$ to primal, $x$ is an optimal solution to primal if and only if there exists $y$ that is feasible for dual and satisfies the complementary slackness condition. I don't understand why it is true.
One direction "$x$ is an optimal solution to primal only if there exists $y$ that is feasible for dual and satisfies the complementary slackness condition" is true because of strong duality.
But I don't understand the other direction. If there exists $y$ that is feasible for dual and satisfies the complementary slackness condition, how do we justify that $x$ is optimal?
When solving either the primal or dual models for an optimal solution, we are effectively trying to close the duality gap between the models (see the Duality Theorems section). Recall the formal definitions of primal and dual linear programs:
\begin{matrix} & \text{Primal} & \text{Dual} \newline & \max z = c^Tx & \min w=b^Ty \newline \text{Subject to:} & Ax\le b & A^Ty \ge c \newline & x\ge0 & y \ge 0 & \end{matrix}
The duality theorem suggests that the constraints in one problem are tied to the variables of another problem via this primal-dual relationship (see Page $7$). If the primal variable, $x>0$, the constraint in the corresponding dual problem is binding; otherwise, if $x=0$, it is not binding. Likewise, if $y>0$, the corresponding constraint in the primal is binding; otherwise, if $y=0$, it is not binding.
The duality gap states that if an optimal solution for either problem is found, then $c^Tx = b^Ty$. Therefore, complementary slackness is a direct result of this behavior coming from the binding constraints of the optimal solution. The attached paper goes into this more theoretically and provides examples of how this can be used to solve either model given a solution from only one of them.