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

Posted in linear programming, optimization | Leave a comment

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

Posted in combinatorial optimization, games, graph theory | 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

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

Posted in optimization, probability | Leave a comment

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

Posted in gender, operations research, optimization, statistics | 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

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

Posted in asymptotics, combinatorial optimization, probability | Leave a comment