Wait… what? Doesn’t the strong duality theorem imply that there is no duality gap in linear programming? Mostly, yes, although there is a sense in which there actually is a duality gap; it occurs when the primal and dual problems are both infeasible. To see this, let’s take a closer look at what the strong duality theorem is saying.
Strong Duality Theorem: If x is an optimal solution for the primal problem with objective c, and y is an optimal solution for the dual problem with objective b, then .
So if the primal and dual problems have optimal solutions, then the optimal objective function values must be equal. But what if either the primal or the dual doesn’t have an optimal solution? The weak duality theorem tells us something about this.
Weak Duality Theorem: If x is a feasible solution for a maximizing primal problem with objective c, and y is a feasible solution for its minimizing dual problem with objective b, then .
If the primal problem is unbounded, then a feasible solution to the dual would contradict weak duality. Thus weak duality says that primal unboundedness implies dual infeasibility. Similarly, dual unboundedness implies primal infeasibility.
But there’s one more case that we haven’t considered: Is it possible for both the primal and dual problems to be infeasible? Yes, it is. Here’s an example.
The primal and dual are both clearly infeasible. (In fact, except for maximizing vs. minimizing, they are the same problem!)
The case in which both primal and dual problems are infeasible is the sense in which there is a duality gap. If we take the view that the maximum of a function over the empty set is , and the minimum of a function over the empty set is , then when both problems are infeasible we have a duality gap of .