When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual."
I know that both the primal LP and its dual must have the same optimal objective value (assuming both are feasible and bounded). I also understand complementary slackness (the product of all primal variables and dual slack variables is 0, as is the product of all dual variables and primal slack variables).
To me, solving the dual gives you some useful information about the solution of the primal:
- The final objective value, which restricts you to an $n-1$ hyperplane
- All nonzero dual slack variables require primal variables of 0.
But aside from this information, to me it doesn't seem that solving the dual truly solves the primal LP. Knowing the optimal objective value can help (given this, simply find the primal feasible point with that objective value), as can knowing which primal variables are 0. But the latter is LP-specific: if the dual problem has many zeroes in the solution, then there isn't information about the primal variables.
My question is this: when people say "We'll solve the dual," does that mean it actually solves the primal or that it simply gives useful information that can help to faster solve the primal?
Thanks for your help, none of my colleagues could answer.