Take the 2-minute tour ×

I have a question regarding complementary slackness, the answer should be true of false.

The complementary slackness conditions connect pairs of optimal basic feasible solution of primal and dual linear programs. They correspond to connection between non zero variables in the solution to one linear program and constraints that are satisfied with equality in the other linear program. If there is optimal solution that is not basic feasible solution, complementary slackness condition may not be held.

In my opinion, the answer is false, but I am not completely sure. Why it mentions the optimal solution which is not basic feasible solution? I thought it's impossible, optimal solution has to be one of the BFSs. The following remark made the issue completely ambiguous Deterministic Operations Research: Models and Methods in Linear Optimization. So, on every iteration the complementary slackness conditions are held? But this is not what the complementary slackness theorem was talking about.

If you have good understanding of the topic, please point out what exactly I missed. Thanks!

share|improve this question

1 Answer 1

up vote 1 down vote accepted

If there are multiple optimal solutions then some of them won't be basic. Instead, they will be strictly convex combinations of optimal solutions that are basic. (For example, an entire facet of a polytope could be optimal. The extreme points of the facet will be basic, but the interior points won't be.) For the nonbasic optimal solutions, complementary slackness will not be guaranteed to hold. (The complementary slackness theorem refers to basic solutions.) Thus the statements are true.

As far as your other question, yes, the complementary slackness conditions hold for the current basic feasible solution at every iteration of the primal - or dual - simplex method. The output of the simplex method will be an optimal basic feasible solution, and complementary slackness will hold for that solution. Again, though, if there are other optimal solutions, complementary slackness will not hold for the ones that aren't also basic.

share|improve this answer
thank you very much, this is great answer, I very appreciate your help. I am still want to be your student :) –  com Dec 5 '11 at 8:00
@com: You're welcome. I'm glad it was helpful. :) –  Mike Spivey Dec 6 '11 at 5:12

Your Answer


