Category Archives: linear programming

Intuition for the Dual in Linear Programming

One of the most important theoretical results in linear programming is that every LP has a corresponding dual program. Where, exactly, this dual comes from can often seem mysterious. Several years ago I answered a question on a couple of … Continue reading

Posted in linear programming, optimization | Leave a comment

The Max Flow-Min Cut Theorem via Linear Programming Duality

The Max Flow-Min Cut Theorem states that the maximum flow from the source node to the sink node through a capacitated network is equal to the capacity of the minimum cut that separates that source node from the sink node.  … Continue reading

Posted in linear programming, optimization | Leave a comment

Some Uses of Duality in Linear Programming

For most of my students, the first time they see duality in linear programming their first reaction is “What’s the big deal?”  There was a recent post on math.SE asking the same question.  Duality in linear programming seems to me … Continue reading

Posted in linear programming | 1 Comment

The Duality “Gap” in Linear Programming

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 … Continue reading

Posted in linear programming, optimization | 3 Comments