3

For linear programming, can we get the optimal solution of the primal problem based on the optimal solution of the dual problem? It seems that for dual problems, people are more concerned about the objective function value rather than the optimal solution.

J Allan
  • 31
  • When you refer to "the solution", you should be aware that the primal problem or the dual problem might have multiple optimal solutions. Is any one optimal solution to the primal problem enough? Also, what's the particular form of your LP- do you have <= constraints, equality constraints, non-negative variables, bounded variables? – Brian Borchers Sep 15 '16 at 22:08

1 Answers1

1

Yes, solving the dual problem will give you a solution to the primal problem as well. Remember that each slack variable associated with a constraint in the primal problem corresponds to a decision variable in the dual problem. In fact, the dual decision variable is nonzero if and only if the corresponding primal constraint is satisfied with equality (i.e. the primal slack variable is zero). This is the notion of complimentary slackness. Once you know which constraints must hold with equality in the primal, you can obtain the values of the primal decision variables with a linear system solve.

It's been a while since I took linear programming, so double check what I said before using it in your own work.

Chris Harshaw
  • 1,124
  • Thanks a lot! I checked complimentary slackness and now I understand what you mean. Really appreciate your help! – J Allan Sep 20 '16 at 00:55
  • @JAllan Sure thing - glad I could help! Several algorithms for solving LPs actually rely on duality for speed ups. You can also use duality bounds to obtain classic graph theory bounds as well. It's something that comes in handy often. – Chris Harshaw Sep 21 '16 at 05:04