# Category Archives: optimization

## 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

## Minimum Number of Wagons to Connect Every City in Ticket to Ride – Europe

How many wagons would you need to create a route network in the board game Ticket to Ride – Europe so that every city is connected to every other city through the network?  If you could do this you could potentially … Continue reading

## 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

## The Secretary Problem With the Two Best

The secretary problem is the following: Suppose a manager wants to hire the best person for his secretary out of a group of n candidates.  He interviews the candidates one by one.  After interviewing a particular candidate he must either (1) … Continue reading

## Operations Research Makes List of Top 5 STEM Professions Employing Women

My February 2016 issue of ORMS Today says that “operations research analyst” is the STEM (Science, Technology, Engineering, and Mathematics) profession with the third-highest percentage of women.  The percentage of OR analysts who are women is 55.4%.  I’m glad to see … Continue reading

## 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

## Random Assignment Problems

The most fundamental problem in combinatorial optimization is probably the assignment problem.  Here we have, say, a set of n resources and a set of n tasks, and we want to assign each resource to exactly one task and exactly … Continue reading