Lecture 15: Linear Programming - LP, Reductions, Simplex

What this lecture covers

This MIT 6.046 lecture introduces linear programming (LP) as a general-purpose optimization tool that can express problems you've already solved with specialized algorithms, such as max flow and shortest paths, as a single linear objective function subject to linear constraints. It answers the question of how far a single algorithmic "hammer" can reach across combinatorial optimization problems, and what it costs to gain that generality.

The lecture stands on its own within the course's algorithm-design unit, following max flow and preceding NP-completeness. After watching, you should be able to set up an LP from a word problem, convert an LP into standard form, explain what an LP dual and a certificate of optimality are, reduce max flow and shortest-path problems to LP, and follow one pivot step of the simplex algorithm.

Key ideas

• Linear program: a set of variables, a linear objective function to maximize or minimize, and a set of linear inequality or equality constraints.
• Standard form: maximize c*x subject to A*x <= b and x >= 0; any LP with a different objective direction, inequality direction, or unrestricted variables can be rewritten into this form.
• Simplex algorithm: runs in worst-case exponential time but is efficient in practice; the ellipsoid method (Khachiyan, 1979) was the first proof that LP is solvable in polynomial time, though it performs poorly in practice.
• Certificate of optimality: a short algebraic combination of the constraints that proves a claimed solution cannot be improved, without running or re-verifying an algorithm.
• LP duality: every LP (the primal) has a corresponding dual LP that flips maximization and minimization, swaps the roles of the objective coefficients and the constraint bounds, and yields the same optimal value.
• Reduction to LP: max flow reduces to LP using capacity, conservation, and skew-symmetry constraints; shortest paths reduce to LP using the triangle inequality plus a maximization objective (not the intuitive minimization).
• Slack form: an equivalent representation of an LP that introduces one new "basic" variable per constraint, representing how much room is left before that constraint is tight.
• Pivoting: the core simplex step, swapping a basic and a non-basic variable to move to an equivalent slack form whose objective value has not decreased.

Walkthrough

A political campaign as a linear program (2:06)

The lecture opens with a worked example: allocate advertising dollars across four issues to win a majority in three demographics, using a table of estimated votes per dollar spent (which can be negative). This is translated into variables x1 through x4 (dollars spent per issue), a minimization objective (x1 + x2 + x3 + x4), and one linear inequality constraint per demographic requiring enough votes for a majority, plus non-negativity constraints on all variables.

General and standard form of an LP (18:41)

The lecture generalizes from the example to the standard form used throughout the rest of the course: maximize c*x subject to A*x <= b and x >= 0, where x is a vector of n variables and there are m constraints. It notes that other forms (minimization, greater-than-or-equal constraints, equality constraints) are common in practice and will need to be converted.

Duality and certificates of optimality (23:06)

Returning to the campaign example, the instructor shows that multiplying the three constraints by specific coefficients and adding them together produces a single inequality whose left side is bounded by the objective function and whose right side equals the claimed optimal cost. Because every term is non-negative, this proves the claimed value cannot be beaten, without needing to trust or re-run any algorithm. This generalizes to LP duality: the primal LP's optimal value equals its dual LP's optimal value, where the dual swaps the objective coefficients with the constraint bounds and flips maximization to minimization.

Converting any LP to standard form (32:16)

The lecture works through the mechanical conversions needed for a standard-form LP solver: negate the objective to switch between minimization and maximization, split an unrestricted variable into the difference of two non-negative variables, and replace an equality constraint with two opposing inequality constraints.

Max flow and multicommodity flow as LP (39:39)

Max flow is reduced to LP by maximizing the flow out of the source subject to three families of linear constraints: capacity (f(u,v) <= c(u,v)), conservation (flow in equals flow out at every non-source, non-sink vertex), and skew symmetry (f(u,v) = -f(v,u)). The lecture notes that a dedicated max-flow algorithm will outperform a general LP solver here, but the LP formulation extends naturally to multicommodity flow, where several flows share the same edge capacities, by summing each commodity's flow in the capacity constraint.

Shortest paths as LP (48:52)

Reducing single-source shortest paths to LP is less direct. The triangle inequality (d(v) - d(u) <= w(u,v) for every edge, with d(s) = 0) gives the constraints, but the natural choice of minimizing the sum of distances fails, since setting every d(v) to zero would trivially satisfy the inequalities. The lecture shows that maximizing the sum of d(v) values instead forces each distance up to the tightest constraint that applies to it, which is exactly the shortest-path value.

Simplex algorithm and pivoting (59:04)

The lecture introduces slack form, where each constraint gets a new basic variable representing its slack, and the original variables become non-basic. Starting from the trivial all-zero solution, the instructor works through one pivot step on a small example: select a non-basic variable with a positive objective coefficient, increase it until some constraint becomes tight, and swap that variable with the constraint's basic variable, rewriting all equations by substitution. This single pivot raises the objective value from 0 to 27, and the lecture notes that repeated pivoting converges to the optimum, which becomes obvious once every non-basic variable has a negative coefficient in the objective row.

Before you watch

• Review max flow, capacity, conservation, and residual graphs from the preceding lectures.
• Review Dijkstra's algorithm and the triangle-inequality relaxation used in shortest-path algorithms.
• Basic comfort with matrix and vector notation (A*x <= b) will help with the standard-form discussion.

Check your understanding

1. Why does multiplying and summing the campaign example's three constraints prove the claimed solution is optimal, without running any algorithm?
2. What are the three families of constraints needed to express max flow as a linear program, and which one changes when moving to multicommodity flow?
3. Why does the shortest-path LP need to maximize the sum of distances rather than minimize it?
4. In the simplex pivot example, why does increasing x1 first hit the third constraint rather than the first or second?
5. What is the practical tradeoff between the simplex algorithm and the ellipsoid or interior-point methods?