Linear Programming

Chapter 1: Standard and Slack Forms

Before we can solve an LP algorithmically, we need a canonical representation. There are many equivalent ways to write the same LP — maximizing vs. minimizing, ≤ vs. ≥ constraints, variables that can be negative vs. non-negative. The standard form picks one convention and sticks to it.

Standard Form

An LP is in standard form if it:

• Maximizes the objective (not minimizes)
• All constraints are ≤ inequalities (not ≥ or =)
• All variables are non-negative (x_i ≥ 0)

In matrix notation:

Where c is the n×1 objective vector, A is the m×n constraint matrix, b is the m×1 resource vector, and x is the n×1 decision variable vector. Our furniture LP is already in standard form: we maximize, all constraints are ≤, and x₁, x₂ ≥ 0.

Converting to Standard Form

Any LP can be converted to standard form using three transformations:

1. Minimization → Maximization. If the original LP minimizes c^Tx, negate the objective: maximize (-c)^Tx. The optimal x is the same; the optimal value has opposite sign.

2. Equality constraints. Replace each equality a_i^Tx = b_i with two inequalities: a_i^Tx ≤ b_i and a_i^Tx ≥ b_i. The second inequality is then flipped: -a_i^Tx ≤ -b_i.

3. Unrestricted variables. If x_j can be negative, replace it with x_j = x_j⁺ - x_j^- where both x_j⁺, x_j^- ≥ 0. The difference can represent any real number.

Slack Form

Standard form uses inequalities. But algebraic manipulation (like the simplex algorithm) prefers equalities. We convert each inequality to an equality by introducing a slack variable.

The constraint 4x₁ + 3x₂ ≤ 240 becomes 4x₁ + 3x₂ + s₁ = 240 where s₁ ≥ 0 is the slack — it measures how much "room" we have left. If 4x₁ + 3x₂ = 200, then s₁ = 40: we have 40 unused carpentry hours.

For our furniture LP, slack form is:

Now we have 5 variables (2 original + 3 slack) and 3 equality constraints. The slack variables s₁, s₂, s₃ are the basic variables — they are expressed in terms of the non-basic variables x₁, x₂. Setting the non-basic variables to zero gives the basic feasible solution (BFS): x₁ = 0, x₂ = 0, s₁ = 240, s₂ = 100, s₃ = 200. This corresponds to producing nothing — all resources are slack.

Worked Conversion Example

Let us convert a non-standard LP to standard form step by step. The original problem:

Step 1: Convert minimize to maximize. Negate the objective: maximize -2x₁ + 3x₂.

Step 2: Handle the equality constraint. Replace x₁ + x₂ = 10 with two inequalities: x₁ + x₂ ≤ 10 and -x₁ - x₂ ≤ -10.

Step 3: Flip the ≥ inequality. x₁ - x₂ ≥ 2 becomes -x₁ + x₂ ≤ -2.

Step 4: Handle unrestricted x₂. Replace x₂ = x₂⁺ - x₂^- with x₂⁺, x₂^- ≥ 0.

The result in standard form (3 variables, 3 constraints):

Note the negative RHS values (-10 and -2). This means the origin x = 0 is not feasible. The simplex algorithm needs a feasible starting point, so it uses Phase I: add artificial variables, solve an auxiliary LP to find a feasible BFS, then switch to Phase II (optimize the real objective). Most textbooks and solvers handle this automatically.

Visualizing the Transformation

The canvas below shows the transformation from standard form (inequalities) to slack form (equalities with slack variables). Each constraint is shown with its slack variable. As you move the point (x₁, x₂) around the feasible region, watch the slack values change: they are zero on the boundary and positive in the interior.

Data Flow Summary

The transformation from general to standard to slack is mechanical and reversible. No information is lost. But the slack form is what the simplex algorithm actually operates on. It needs equalities so it can do algebra — solving for one variable in terms of others, pivoting variables between basic and non-basic sets.

Chapter 2: The Simplex Algorithm

The simplex algorithm, invented by George Dantzig in 1947, is one of the most important algorithms in all of computing. It solves linear programs by walking along the edges of the feasible polytope, moving from vertex to vertex, always improving the objective value, until it reaches the optimum.

The Idea: Vertex Hopping

Here is the high-level strategy. Start at some vertex (a basic feasible solution). Look at all adjacent vertices — those reachable by moving along one edge of the polytope. Pick the neighbor that improves the objective the most (or any improving neighbor). Move to it. Repeat until no neighbor is better. Because the feasible region is convex, this greedy uphill walk always finds the global optimum.

In algebraic terms, "moving to an adjacent vertex" means performing a pivot operation: one non-basic variable enters the basis, one basic variable leaves. The entering variable is chosen because increasing it improves the objective. The leaving variable is determined by the minimum ratio test — it is the basic variable that reaches zero first as we increase the entering variable.

Worked Example

Let us solve our furniture LP step by step. Starting slack form:

Initial BFS: x₁ = 0, x₂ = 0, s₁ = 240, s₂ = 100, s₃ = 200. Objective z = 0. This is the origin — produce nothing.

Iteration 1: Choose entering variable. Look at the objective z = 70x₁ + 50x₂. Both coefficients are positive, so increasing either variable improves z. We pick x₁ (coefficient 70 is largest). This is the largest-coefficient rule.

Minimum ratio test. How much can we increase x₁ (keeping x₂ = 0) before some basic variable goes negative?

The tightest constraint is s₂ (lumber), giving x₁ ≤ 33.3. So s₂ is the leaving variable — it becomes zero. We solve the lumber equation for x₁:

Now substitute this expression for x₁ everywhere else:

After pivot 1: Basic: {x₁, s₁, s₃}. Non-basic: {x₂, s₂}. BFS: x₁ = 100/3 ≈ 33.3, x₂ = 0, z ≈ 2333.3. We moved from the origin to the vertex at (33.3, 0).

Iteration 2: Choose entering variable. z = 7000/3 - 70s₂/3 - 200x₂/3. Both non-basic coefficients are negative. No variable can be increased to improve z. We are optimal!

The optimal solution is x₁ = 100/3 ≈ 33.3 tables, x₂ = 0 chairs, profit z = 7000/3 ≈ $2333.33.

The Simplex Algorithm — Formal Steps

Watch Simplex Walk

The canvas below shows the simplex algorithm walking from vertex to vertex on our furniture LP. Each iteration is one edge traversal. The objective value increases at every step. Click "Step" to advance one pivot, or "Run" to animate.

Understanding the Tableau

The simplex algorithm is often implemented using a tableau — a matrix that encodes the current slack form compactly. Each row corresponds to a basic variable's equation, and the last row is the objective function. Pivoting is just Gaussian elimination on this matrix.

The initial tableau for our furniture LP looks like this:

The objective row uses negated coefficients (for the implementation convention of maximizing). When all entries in the objective row are non-negative, we are optimal.

After pivot 1 (x₁ enters, s₂ leaves): we divide the s₂ row by the pivot element (3) and eliminate x₁ from all other rows. The result:

All entries in the objective row are non-negative (200/3 ≈ 66.7 and 70/3 ≈ 23.3). We are optimal. The solution: x₁ = 33.3, x₂ = 0, z = 2333.3.

Notice the dual solution hiding in the tableau. The objective row entries under the slack variables (s₂ column = 70/3 ≈ 23.3) are the dual variables. The dual variable y₂ = 23.3 is the shadow price of lumber — one more unit of lumber is worth $23.3 in additional profit. The simplex algorithm produces both primal and dual solutions simultaneously.

Python Implementation

python
import numpy as np

def simplex(c, A, b):
    """Solve: maximize c^T x subject to Ax <= b, x >= 0.
    c: (n,) objective coefficients
    A: (m, n) constraint matrix
    b: (m,) resource vector (must be >= 0)
    Returns: optimal x, optimal value z
    """
    m, n = A.shape
    # Build initial tableau: [A | I | b] with objective row [-c | 0 | 0]
    tab = np.zeros((m + 1, n + m + 1))
    tab[:m, :n] = A                            # constraint coefficients
    tab[:m, n:n+m] = np.eye(m)                 # slack variables
    tab[:m, -1] = b                             # RHS
    tab[-1, :n] = -c                             # objective (negated for min)
    basis = list(range(n, n + m))             # initial basis = slack vars

    while True:
        # Step 2: find entering variable (most negative in obj row)
        obj_row = tab[-1, :-1]
        if np.all(obj_row >= -1e-10):
            break                              # optimal!
        enter = np.argmin(obj_row)

        # Step 3: minimum ratio test
        col = tab[:m, enter]
        rhs = tab[:m, -1]
        ratios = np.full(m, np.inf)
        pos = col > 1e-10
        ratios[pos] = rhs[pos] / col[pos]
        if np.all(ratios == np.inf):
            raise ValueError("LP is unbounded")
        leave = np.argmin(ratios)

        # Step 4: pivot
        pivot = tab[leave, enter]
        tab[leave] /= pivot                   # normalize pivot row
        for i in range(m + 1):
            if i != leave:
                tab[i] -= tab[i, enter] * tab[leave]
        basis[leave] = enter

    # Extract solution
    x = np.zeros(n)
    for i, var in enumerate(basis):
        if var < n:
            x[var] = tab[i, -1]
    return x, tab[-1, -1]

# Furniture problem
c = np.array([70, 50])
A = np.array([[4, 3], [3, 5], [2, 4]])
b = np.array([240, 100, 200])
x_opt, z_opt = simplex(c, A, b)
print(f"Optimal: x = {x_opt}, z = {z_opt:.2f}")
# Optimal: x = [33.33  0.  ], z = 2333.33

Chapter 3: Degeneracy and Cycling

In Chapter 2, the simplex algorithm improved z at every iteration and terminated quickly. But there is a subtle pitfall: what happens when a pivot does NOT improve the objective? This occurs at degenerate vertices, and it can cause the algorithm to cycle forever.

What Is Degeneracy?

A basic feasible solution is degenerate if one or more basic variables has value zero. Geometrically, this means more than n constraints are active (tight) at the same vertex. In 2D, a non-degenerate vertex has exactly 2 active constraints. A degenerate vertex has 3 or more constraints meeting at the same point.

Why does this cause problems? When the minimum ratio test yields a ratio of zero (because some basic variable is already at zero), the pivot moves to a new basis BUT the BFS stays at the same point in space. The objective does not improve. We changed the algebraic representation of the vertex without actually moving. If this happens repeatedly, the algorithm can cycle through a sequence of bases, all representing the same vertex, never making progress.

Bland's Rule

Bland's rule (1977) is the simplest anti-cycling rule: among all eligible entering variables (those with positive objective coefficient), always choose the one with the smallest index. Among all eligible leaving variables (those with the smallest ratio), always choose the one with the smallest index. That is it. This simple tie-breaking rule provably prevents cycling.

The proof is by contradiction: if cycling occurs, there is a smallest set of variables involved in the cycle. Bland's rule creates a contradiction within this set by showing the last variable to leave the basis could not have re-entered under the smallest-index rule.

Worst-Case Complexity

The simplex algorithm is not polynomial in the worst case. In 1972, Klee and Minty constructed a family of LPs on which the simplex method with the largest-coefficient rule visits every vertex — an exponential number. The Klee-Minty cube in d dimensions has 2^d vertices, and the algorithm visits all of them.

But this is a pathological worst case. In practice, the simplex method is astonishingly fast.

Smoothed Analysis: Why Simplex Works in Practice

In 2001, Daniel Spielman and Shang-Hua Teng introduced smoothed analysis, explaining why simplex works so well despite its exponential worst case. The idea: the Klee-Minty cube is razor-sharp. Even tiny random perturbations to the constraint coefficients destroy the pathological structure. Real-world problems are never perfectly aligned — noise, rounding, and imprecise measurements ensure that the constraints are slightly "jiggled."

Under smoothed analysis, the simplex method runs in polynomial time: O(n³ / σ⁴) where σ is the standard deviation of random perturbation. Spielman and Teng won the Godel Prize for this result. It explains a 50-year mystery: why does an exponential-time algorithm solve real problems so fast?

A Concrete Cycling Example

To understand cycling, consider this LP:

All three constraints are active at (2, 2): 2+2=4, 4+2=6, 2+4=6. This is a degenerate vertex. The simplex tableau at this vertex has a basic variable equal to zero. During the pivot, the minimum ratio test produces a tie (ratio = 0 for multiple basic variables). The choice of leaving variable is ambiguous.

Without Bland's rule, the algorithm might choose the wrong leaving variable, arrive at a different basis representing the same point (2,2), and repeat. The algebraic representation changes — which variables are basic vs. non-basic — but the actual solution does not move. After several such "degenerate pivots," the algorithm might return to the original basis, creating a cycle.

With Bland's rule, we always break ties by choosing the smallest-index variable. This systematic tie-breaking ensures that the algorithm eventually escapes the degenerate vertex and moves to a genuinely better vertex. The proof uses a clever potential function argument: Bland's rule ensures a lexicographic improvement even when the objective value stays flat.

Degeneracy Canvas

The canvas below illustrates a degenerate vertex. Three constraint lines meet at the same point. The simplex algorithm can cycle between different bases at this vertex, but Bland's rule prevents it. Toggle Bland's rule on/off to see the difference.

Chapter 4: Duality

Every linear program has a twin. If the original LP (the primal) is a maximization problem, its twin (the dual) is a minimization problem. They are mirror images, and their optimal values are always equal. This is the strong duality theorem, and it is one of the most beautiful results in optimization.

Constructing the Dual

Start with the primal in standard form:

The dual is constructed by a systematic transposition:

The recipe: (1) The primal's resource vector b becomes the dual's objective. (2) The primal's objective c becomes the dual's constraint RHS. (3) The constraint matrix transposes. (4) ≤ becomes ≥. (5) Maximize becomes minimize. (6) Each primal constraint gets a dual variable y_i.

For our furniture LP, the dual is:

Weak Duality

Weak duality theorem: For any feasible primal solution x and any feasible dual solution y:

Every feasible dual solution provides an upper bound on the primal optimum. Every feasible primal solution provides a lower bound on the dual optimum. The proof is one line:

Strong Duality

Strong duality theorem: If the primal has an optimal solution x*, then the dual also has an optimal solution y*, and:

At optimality, the primal and dual values are exactly equal. The gap closes completely. This is remarkable: two different optimization problems, one maximizing and one minimizing, arrive at exactly the same value.

The proof comes from the simplex algorithm itself. The final tableau of the simplex method provides both the optimal primal solution (the basic variables' values) and the optimal dual solution (the objective row's slack variable coefficients). Simplex solves both problems simultaneously.

Complementary Slackness

Strong duality implies complementary slackness: at optimality, for each constraint, either the constraint is tight (active) or the corresponding dual variable is zero. In symbols:

If a resource is not fully used (primal slack > 0), its price must be zero (dual variable = 0). If a resource has a positive price, it must be fully consumed. This makes economic sense: scarce resources (fully consumed) have positive prices; abundant resources (slack left over) are free.

Economic Interpretation of Duality

Duality has a beautiful economic interpretation. The primal problem asks: "Given limited resources, how do I maximize profit?" The dual asks the reverse: "What is the minimum price I should charge for my resources so that no production activity is profitable?"

Consider our furniture LP. The primal solution says: make 33.3 tables, 0 chairs, profit $2333. The dual solution assigns prices to resources: y₁ = 0 (carpentry is abundant), y₂ ≈ 23.3 (lumber is scarce, worth $23.3/unit), y₃ = 0 (finishing is abundant). The total resource value: 240(0) + 100(23.3) + 200(0) = $2333. Exactly the profit.

Why is y₁ = 0? Because the carpentry constraint is not tight — we use only 4(33.3) = 133 of 240 available hours. Abundant resources have zero price. Why is y₂ = 23.3? Because lumber is the binding constraint. Every additional unit of lumber allows us to make 1/3 more table (since each table uses 3 lumber), gaining 70/3 ≈ $23.3 more profit.

Duality in Game Theory

Von Neumann's minimax theorem (1928) for two-person zero-sum games is equivalent to LP duality. Player 1 maximizes their minimum payoff (primal). Player 2 minimizes their maximum loss (dual). The minimax theorem says these values are equal — which is exactly strong duality. The mixed-strategy Nash equilibrium of a zero-sum game can be found by solving an LP.

This connection is not coincidental. Dantzig developed the simplex method partly inspired by von Neumann's game theory work. Von Neumann immediately recognized that his minimax theorem was a special case of LP duality when Dantzig showed him the simplex method in 1947. The two theories developed in parallel and are deeply intertwined.

Primal-Dual Canvas

The canvas below shows the primal and dual problems side by side. As you drag the primal solution toward optimality, the dual bound decreases to meet it. At the optimal solution, the two values are equal — the duality gap is zero.

Chapter 5: LP Showcase

This is the payoff. Below is a fully interactive LP solver. You define the problem — adjust constraint lines, change the objective — and watch the simplex algorithm solve it in real time. You will see the feasible region reshape, the simplex path change, and the dual solution appear alongside.

The Interactive LP Lab

The LP has two variables (x₁, x₂). You can:

• Drag constraint lines — click and drag any colored constraint to change its RHS (the right-hand side b_i).
• Change the objective — use the c₁, c₂ sliders to change the profit coefficients.
• Load presets — try the Diet Problem, Production Planning, or Network Flow formulations.
• Run simplex — watch the algorithm walk from vertex to vertex, with the tableau shown below.

Preset Problems

Diet Problem (1947). The original LP application. George Stigler asked: what is the cheapest diet that meets all nutritional requirements? Minimize cost subject to minimum nutrient constraints. Here, we maximize "nutrition score" subject to budget and calorie limits — a simplified version.

Production Planning. Our furniture workshop with different parameters. Adjust b₁, b₂, b₃ to see how changing resource availability shifts the optimum.

Transport. A simplified transportation problem: ship goods from two factories to meet demand, minimizing shipping cost. Formulated as an LP with supply and demand constraints.

Sensitivity Analysis: What Happens When Things Change

One of the most powerful uses of LP is sensitivity analysis — understanding how the optimal solution changes when the problem data changes. In practice, the constraint coefficients and RHS values are never perfectly known. Material costs fluctuate. Demand shifts. Resources become scarce or abundant. A good decision-maker needs to know: how sensitive is my plan to these changes?

The dual variables provide this directly. The dual variable y_i* for constraint i is the shadow price — it tells you how much the optimal objective would improve if you increased b_i by one unit. If the lumber constraint has shadow price y₂* = 23.3, then one more unit of lumber is worth $23.3 in additional profit. This is exactly what the dual variables compute.

Try it in the simulation above. Increase b₂ (lumber) from 100 to 105 and note the change in z*. The change should be approximately 5 × y₂*. This relationship holds exactly within a sensitivity range — the interval of b_i values over which the current basis remains optimal.

Degeneracy in the Showcase

As you drag b₁, b₂, b₃, you may encounter configurations where three constraint lines pass through the same point. This is degeneracy — the vertex where the optimum sits has more active constraints than strictly necessary. The optimal solution is still correct, but the shadow prices may not be unique: multiple dual solutions exist, each providing different (but equally valid) shadow prices. In practice, commercial solvers handle this gracefully.

Try setting b₁ = 240, b₂ = 100, b₃ = 200. The optimum is at x₁ ≈ 33.3, x₂ = 0, where only the lumber constraint is tight. Now slowly decrease b₁ until it also becomes tight. At that moment, you have a degenerate vertex — two constraints active at the optimum. The feasible region changes shape, but the optimum may not move until one constraint "takes over" from another.

Chapter 6: Reductions to LP

Linear programming is not just one optimization problem. It is a universal language for optimization. An enormous number of seemingly different problems — shortest paths, maximum flow, minimum-cost flow, bipartite matching — can all be expressed as linear programs. If you can formulate a problem as an LP, you can solve it with any LP solver.

Shortest Paths as LP

The single-source shortest path problem: find the shortest path from source s to every other vertex in a weighted graph. This is Bellman-Ford (Chapter 24), but it can also be written as an LP.

For each vertex v, let d_v be the distance from s to v. The LP is:

Wait — maximize? That seems backward. The trick: the triangle inequality constraints force d_v ≤ shortest path length. Maximizing pushes each d_v up to the tightest constraint, which is exactly the shortest path. It is a beautiful application of LP duality: the "maximize subject to upper bounds" formulation naturally computes the tightest (shortest) distances.

Maximum Flow as LP

The max-flow problem (CLRS Chapter 26): maximize flow from source s to sink t through a network with edge capacities. Each edge (u,v) has capacity c(u,v). Flow f(u,v) must satisfy:

This is a linear program. The variables are edge flows f(u,v). The constraints are linear. Ford-Fulkerson, Edmonds-Karp, push-relabel — all specialized algorithms for this LP. They are faster than general simplex because they exploit the network structure. But any LP solver can solve max-flow.

Min-Cost Flow

Min-cost flow generalizes both shortest paths and max-flow. Each edge has a capacity AND a per-unit cost. The LP: minimize total cost while shipping a required amount of flow from s to t. Both shortest path and max-flow are special cases — shortest path has unit flow, max-flow has zero costs.

Bipartite Matching

Given a bipartite graph, find the maximum matching (largest set of edges with no shared vertices). The LP relaxation:

Normally, matching requires x_uv ∈ {0, 1} (integer), making it an ILP. But for bipartite graphs, a miracle occurs: the LP relaxation always has an integer optimal solution. The constraint matrix is totally unimodular — every square submatrix has determinant 0, +1, or -1. Total unimodularity guarantees integer vertices. This is why bipartite matching is polynomial: it reduces to LP, and the LP happens to have integer solutions.

Reductions Canvas

The canvas below shows how max-flow can be expressed as an LP. A small network is shown with edge capacities. The LP variables (one per edge) and constraints (capacity + conservation) are displayed alongside. Run the LP solver to find the max flow.

LP as a Modeling Language

The power of LP reductions is not just theoretical. In practice, operations researchers formulate problems in LP modeling languages like AMPL, GAMS, or PuLP (Python). You describe the problem declaratively — variables, objective, constraints — and the solver handles the rest. The formulation is separated from the algorithm. This separation is LP's greatest practical strength.

python
# Max flow as LP using PuLP (Python)
from pulp import *

# Network: s->a (cap 5), s->b (cap 4), a->b (cap 2), a->t (cap 3), b->t (cap 6)
prob = LpProblem("MaxFlow", LpMaximize)

# Flow variables (one per edge)
f_sa = LpVariable("f_sa", 0, 5)  # 0 <= f <= capacity
f_sb = LpVariable("f_sb", 0, 4)
f_ab = LpVariable("f_ab", 0, 2)
f_at = LpVariable("f_at", 0, 3)
f_bt = LpVariable("f_bt", 0, 6)

# Objective: maximize total flow out of source
prob += f_sa + f_sb

# Flow conservation at a: in = out
prob += f_sa == f_ab + f_at  # flow into a = flow out of a
# Flow conservation at b: in = out
prob += f_sb + f_ab == f_bt  # flow into b = flow out of b

prob.solve(PULP_CBC_CMD(msg=0))
print(f"Max flow = {value(prob.objective)}")
print(f"f(s,a)={f_sa.varValue}, f(s,b)={f_sb.varValue}")
# Max flow = 7.0
# f(s,a)=3.0, f(s,b)=4.0

Notice how clean the formulation is. You declare variables with bounds (capacity constraints). You write the objective (maximize flow from source). You write conservation constraints (flow in = flow out at internal nodes). Then you call solve(). The solver — which internally may use simplex, interior point, or a hybrid — handles everything. You never write a single line of algorithm code.

Chapter 7: Interior Point Methods

The simplex algorithm walks along the boundary of the feasible polytope, hopping from vertex to vertex. Interior point methods take a radically different approach: they go straight through the middle. Instead of staying on the edges, they carve a path through the interior, converging to the optimum from the inside.

The Barrier Idea

The key insight: instead of treating constraints as hard walls (simplex bounces off them), treat them as soft barriers that repel you more strongly as you approach. Add a barrier function to the objective that penalizes getting close to any constraint boundary:

The logarithmic barrier μ ∑ ln(slack_i) goes to -∞ as any slack approaches zero, creating a "force field" that keeps the solution away from the boundary. The parameter μ controls the barrier strength. As μ → 0, the barrier weakens and the solution approaches the true LP optimum.

The algorithm works by solving a sequence of barrier problems with decreasing μ. Each barrier problem is a smooth, unconstrained optimization (because the barrier prevents constraint violation) that can be solved by Newton's method. The sequence of solutions traces a curve called the central path, which converges to the LP optimum.

Karmarkar's Algorithm (1984)

Narendra Karmarkar published the first practical interior point method in 1984. His algorithm was the first to be both (1) polynomial-time and (2) competitive with simplex in practice. It runs in O(n^3.5L) time where L is the bit length of the input. This was a breakthrough: for the first time, there was a provably polynomial algorithm for LP that was also fast in practice.

Before Karmarkar, the only known polynomial LP algorithm was the ellipsoid method (Khachiyan, 1979). The ellipsoid method was a theoretical triumph (it proved LP is in P) but was impractical — much slower than simplex on real problems. Karmarkar's algorithm changed the game by being both theoretically polynomial and practically competitive.

Simplex vs. Interior Point: When to Use Which

Modern LP solvers (CPLEX, Gurobi, HiGHS) implement both methods. Rules of thumb:

• Simplex wins on small to medium problems, and when you need to solve many similar problems (warm-starting from a nearby vertex is efficient).
• Interior point wins on very large, sparse problems (100,000+ variables). The per-iteration cost depends on matrix factorization, and sparse LPs factor efficiently.
• Hybrid: Most solvers run both in parallel and use whichever finishes first. Interior point can also produce a "near-optimal" interior solution that simplex then "crossover" converts to a vertex.

Interior Point Canvas

The canvas below contrasts simplex (green, walks along edges) with interior point (blue, curves through the interior). Both arrive at the same optimum, but by completely different paths.

The Central Path in Detail

The central path is the curve traced by the unique minimizer of the barrier problem as μ varies from ∞ to 0. At μ = ∞, the barrier dominates and the solution is the analytic center of the polytope — the point that maximizes the product of all slacks, the "most interior" point. As μ → 0, the solution slides along the central path toward the optimal vertex.

Each point on the central path satisfies the KKT conditions (Karush-Kuhn-Tucker) of the barrier problem. These conditions require:

The third condition x_is_i = μ is the key. As μ → 0, either x_i → 0 or s_i → 0 (or both) — which is exactly complementary slackness. The central path smoothly transitions from "everything is interior" (μ large) to "complementary slackness holds" (μ = 0). Each iteration of the interior point method takes a Newton step toward the current μ-target, then decreases μ.

The convergence is remarkably fast: the number of iterations is O(√n · log(1/ε)) where n is the number of variables and ε is the desired accuracy. This is polynomial and, crucially, almost independent of the constraint coefficients. Compare this to simplex, whose iteration count depends on the geometry of the polytope.

Chapter 8: Interview Arsenal

LP rarely appears directly in coding interviews, but it appears constantly in system design, optimization, and ML interviews. The key skill is recognizing when a problem is an LP in disguise — and knowing how to formulate it. Here is your cheat sheet.

LP Formulation Patterns

Formulation Recipe

Coding Drill: scipy.optimize.linprog

python
from scipy.optimize import linprog

# linprog MINIMIZES c^T x subject to A_ub @ x <= b_ub
# To maximize, negate c.

# Furniture problem: max 70x1 + 50x2
c = [-70, -50]  # negate for minimization
A_ub = [
    [4, 3],   # 4x1 + 3x2 <= 240
    [3, 5],   # 3x1 + 5x2 <= 100
    [2, 4],   # 2x1 + 4x2 <= 200
]
b_ub = [240, 100, 200]
bounds = [(0, None), (0, None)]  # x1, x2 >= 0

res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds)
print(f"x1 = {res.x[0]:.2f}, x2 = {res.x[1]:.2f}")
print(f"Optimal profit = {-res.fun:.2f}")  # negate back
# x1 = 33.33, x2 = 0.00
# Optimal profit = 2333.33

Linearization Tricks

Many "non-linear" objectives can be converted to LP:

Absolute value: Minimize |x| can be written as: minimize t, subject to t ≥ x, t ≥ -x, t ≥ 0. The variable t captures the absolute value.

Minimax: Minimize max(x₁, x₂, ..., x_n) becomes: minimize t, subject to t ≥ x_i for all i. The extra variable t acts as the "worst case."

L1 regression: Minimize ∑ |y_i - a_i^Tx| becomes an LP with 2m extra variables (one positive deviation and one negative deviation for each residual). This is why L1 regression produces sparse solutions — the LP optimal is at a vertex.

Interview Question Bank

Q1: "Design a system to optimize ad placement across web pages."

This is an LP. Variables: x_ij = fraction of time ad i appears on page j. Objective: maximize total click-through revenue. Constraints: each page has limited ad slots, each advertiser has a budget, CTR estimates provide the coefficients. In practice, solved as an LP or ILP billions of times per day by Google, Meta, etc.

Q2: "How would you formulate network routing as an optimization problem?"

Min-cost multi-commodity flow. Variables: flow of each commodity on each edge. Constraints: capacity per edge (shared), flow conservation per commodity. Objective: minimize total cost. This is an LP with network structure — specialized solvers handle billions of variables.

Q3: "What is the relationship between LP and machine learning?"

SVM (support vector machine) training is a quadratic program (QP), which is a generalization of LP. L1-regularized regression (Lasso) can be formulated as an LP. The simplex algorithm inspired the perceptron algorithm. LP duality is the foundation of Lagrangian relaxation, which appears everywhere in constrained ML. Understanding LP gives you the conceptual toolkit for all convex optimization in ML.

Q4: "An airline needs to assign crews to flights. How would you model this?"

This is a set covering / set partitioning problem, naturally modeled as an ILP: binary variable x_j = 1 if we use crew schedule j. Minimize total cost subject to: every flight is covered by at least one crew. The LP relaxation provides a lower bound on cost. In practice, airlines use column generation: start with a small set of schedules, solve the LP, use the dual prices to generate promising new schedules, and iterate. This technique solves problems with millions of potential crew schedules.

Q5: "What is the difference between LP and convex optimization?"

LP is a special case of convex optimization where both the objective and constraints are linear (technically, affine). General convex optimization allows convex objective functions (e.g., quadratic, logarithmic) and convex constraint sets (e.g., second-order cones, semidefinite cones). LP's special structure enables the simplex method (vertex-hopping), which is not applicable to general convex programs. But interior point methods work for both LP and general convex optimization — the barrier approach generalizes naturally.

Complexity Cheat Sheet

Chapter 9: Connections

Linear programming sits at the crossroads of algorithms, complexity theory, and applied mathematics. Here is how it connects to the rest of the CLRS universe and beyond.

LP in the CLRS Landscape

LP vs. Extensions

LP is the simplest member of the convex optimization family. Its special structure (linear objective + linear constraints) enables the simplex method's vertex-hopping strategy. Moving to quadratic objectives (QP) or general convex constraints adds complexity but maintains polynomial solvability. The moment you add integrality constraints (ILP) or non-convexity, the problem becomes NP-hard.

Related Lessons

• CLRS Ch 16: Greedy Algorithms — When LP relaxation has integer vertices, greedy works
• CLRS Ch 24: Shortest Paths — Bellman-Ford is a dual of the shortest-path LP
• CLRS Ch 26: Maximum Flow — Max-flow min-cut theorem = LP strong duality

The Integer Programming Cliff

LP is polynomial. But add the constraint "all variables must be integers" and the problem becomes NP-hard. This is the integer linear programming (ILP) problem. The gap between LP and ILP is one of the sharpest complexity cliffs in all of computer science.

Why is integrality so hard? Because the feasible region is no longer a convex polytope — it is a set of isolated lattice points inside the polytope. You cannot slide smoothly from one feasible solution to another. The LP relaxation (drop the integrality constraint) gives a lower bound, but the gap between the LP relaxation and the true ILP optimum can be arbitrarily large.

In practice, ILP is solved by branch-and-bound: solve the LP relaxation, pick a fractional variable, create two sub-problems (variable ≤ floor and variable ≥ ceil), and recurse. The LP relaxation at each node provides bounds for pruning. Commercial solvers (Gurobi, CPLEX) add cutting planes — additional constraints that cut off fractional solutions without eliminating integer solutions — to tighten the relaxation. The combination of branch-and-bound with cutting planes is called branch-and-cut, and it is the dominant paradigm for solving ILP.

The Bigger Picture

LP was born in 1947 when George Dantzig invented the simplex method for military logistics during World War II. Since then, it has become one of the most practically important algorithms in existence. Every airline schedules flights with LP. Every supply chain optimizes logistics with LP. Every financial firm optimizes portfolios with LP (or its quadratic extension, QP). The US military, which funded Dantzig's original work, still uses LP-based planning tools.

The theoretical importance is equally profound. LP duality underpins the max-flow min-cut theorem, the theory of two-person zero-sum games (von Neumann's minimax theorem is equivalent to LP duality), and the entire field of combinatorial optimization. The polynomial-time solvability of LP (Khachiyan 1979, Karmarkar 1984) was a landmark in complexity theory. And the open question of whether the simplex method has a polynomial-time pivot rule remains one of the great unsolved problems in theoretical computer science.

Open Problems

Despite 75+ years of study, fundamental questions about LP remain open:

Is there a strongly polynomial simplex algorithm? The simplex method's running time depends on the magnitudes of the input numbers (it is weakly polynomial at best, exponential at worst). No one has found a pivot rule that guarantees a polynomial number of pivots independent of the input magnitudes. The Hirsch conjecture — that the diameter of any d-dimensional polytope with n facets is at most n - d — was disproved by Santos in 2010, but the polynomial Hirsch conjecture (diameter polynomial in n and d) remains open.

Is LP in NC? Can LP be solved in polylogarithmic time with polynomially many processors? LP is known to be P-complete (under logspace reductions), which suggests it cannot be efficiently parallelized. But this has not been proven.

Smoothed complexity of interior point methods. Spielman-Teng analyzed simplex under smoothed analysis. The analogous question for interior point methods — does perturbation improve their convergence rate? — is less well understood.

Recommended Further Reading

• CLRS Ch 29 — The source material. Covers standard/slack forms, simplex, duality with rigorous proofs.
• Chvatal, "Linear Programming" — The gold standard textbook. Beautifully written, full of insight.
• Bertsimas & Tsitsiklis, "Introduction to Linear Optimization" — Modern treatment with emphasis on geometry and algorithms.
• Spielman & Teng, "Smoothed Analysis of Algorithms" — The Godel Prize paper explaining why simplex works in practice.
• Boyd & Vandenberghe, "Convex Optimization" — The natural extension to general convex optimization. Free online.

"The world is convex." — Stephen Boyd, 2004