Recipe
Recover a missing LP solution with complementary slackness
Use when: you have one side's optimal solution (primal or dual) for a linear program and need the other side, without solving a second LP
Goal: the complete optimal solution on the missing side, verified against complementary slackness's own conditions
Taught in Complementary slackness for linear programs
Quick recipe
-
1
Decide whether you're holding the primal optimum x^* and need the dual y^*, or the reverse. This decides which direction of the theorem you'll apply.
Example
Given only x^*=(4,3) for Meadowbrook, the dual y^*=(y_1,y_2) is what's missing.
Why: the two implications point in opposite directions, so knowing which side you're solving FOR tells you which fact to read off the known side.
-
2
Check each constraint on the known side for equality (tight) versus strict inequality (slack). Check each variable for being positive versus zero.
Example
Meadowbrook's x^*=(4,3) has both x_1>0 and x_2>0. Clearwater's x^*=(6,0) has constraint 1 tight (6+0=6) and constraint 2 slack (12>8).
Why: these are exactly the facts each complementary-slackness implication consumes — nothing else about the known solution matters for the recovery.
-
3
A positive primal variable x_j^*>0 forces dual constraint j tight. A slack primal constraint i forces y_i^*=0. Apply this pair by pair to every constraint/variable pair — the reverse direction runs symmetrically from a known dual solution.
Example
Meadowbrook: x_1>0 and x_2>0 force both dual constraints tight, y_1+3y_2=4 and 2y_1+y_2=3. Clearwater: constraint 2's slack forces y_2^*=0; x_1=6>0 forces dual constraint 1 tight, y_1+2y_2=2.
Why: this is the exact content of the theorem's either/or — a variable or constraint that isn't at its boundary forces the paired quantity on the other side to vanish, and one that's positive or tight forces the paired constraint to bind.
-
4
Collect every equation and zero from Step 3 into one linear system, usually small, and solve it for the remaining unknowns.
Example
Meadowbrook: y_1=4-3y_2 from the first equation; substituting gives 2(4-3y_2)+y_2=3\Rightarrow y_2=1, so y_1=1. Clearwater: substituting y_2=0 into y_1+2y_2=2 gives y_1=2.
Why: complementary slackness only supplies WHICH constraints bind — finding the actual numbers still requires solving the linear system those binding constraints define.
-
5
Check the recovered solution is feasible for its own problem, including any sign restrictions. Compare its objective value against the known side's, confirming strong duality rather than an arithmetic coincidence.
Example
y^*=(1,1) for Meadowbrook and y^*=(2,0) for Clearwater both match the dual optimum found by direct search earlier — recovered with no second linear program solved.
Why: complementary slackness's conditions are necessary for optimality, so the solved system is worth confirming against the known solution's actual optimal value before trusting it.
Common mistakes
- Applying a tight primal constraint alone as if it forces something about the paired dual variable — only a POSITIVE variable forces its paired constraint tight, and only a SLACK constraint forces its paired variable to zero.
- Forgetting that x_j^*=0 gives no information about dual constraint j — the disjunction is already satisfied by the primal side alone.
- Mixing up which side is primal and which is dual when translating a fact across the pair.
- Skipping the final feasibility or objective-value check and reporting an unverified system solution as the answer.