Linear Programming & Optimization

Optimization of linear objective functions subject to linear constraints. Linear programming is the Swiss Army knife of optimization—one of the most versatile algorithmic techniques with applications spanning operations research, economics, machine learning, network flows, game theory, and approximation algorithms. LP provides both a powerful modeling framework and a rich source of algorithmic techniques including duality theory, which has become a fundamental tool for algorithm design.

Intermediate to Advanced

• Basic LP formulation: Intermediate
• Simplex algorithm: Intermediate to Advanced
• Duality theory: Advanced
• Interior point methods: Advanced
• LP-based approximation algorithms: Advanced

The optimization backbone of industry: Linear programming isn’t an academic curiosity—it’s a foundational technology driving billions in economic value:

• Airlines: Crew scheduling, route planning, yield management (saving billions annually)
• Walmart: Supply chain optimization affecting $500+ billion in annual revenue
• Energy: Power grid optimization, electricity market clearing
• Finance: Portfolio optimization, risk management
• Manufacturing: Production planning, cutting stock problems
• Transportation: Vehicle routing, logistics optimization

War Story - The Berlin Airlift (1948): The Berlin Airlift was one of LP’s first major real-world applications. Supplying West Berlin by air required optimizing cargo loads across flights under complex constraints (weight, volume, runway capacity, nutritional requirements). Hand calculations proved impossible. The military consulted George Dantzig, who formulated it as an LP and solved it with his newly invented simplex algorithm. LP found solutions allocating resources that human planners couldn’t achieve—demonstrating mathematical optimization’s power at scale. This success launched operations research as a field.

War Story - Airline Crew Scheduling: In the 1990s, American Airlines faced an impossible scheduling problem: assign thousands of crew members to tens of thousands of flight segments while respecting:

• FAA rest requirements
• Union rules
• Aircraft types and certifications
• Minimum layover times
• Crew bases and domiciles

Manual scheduling was inefficient and costly. LP formulations with millions of variables and constraints found near-optimal solutions, saving American Airlines an estimated $20 million annually. Today, every major airline uses LP-based scheduling. The economic impact across the industry: hundreds of millions saved annually.

1. LP Formulation - Converting problems to standard/canonical form
2. Graphical Method - Solving 2-variable LPs by geometry
3. Basic Feasible Solutions - Vertices of feasible region
4. Fundamental Theorem of LP - Optimal solution at vertex (if exists)

5. Simplex Algorithm - Pivot between adjacent vertices toward optimum
6. Two-Phase Simplex - Finding initial feasible solution
7. Duality Theory - Every LP has a dual; strong duality theorem
8. Complementary Slackness - Optimality conditions relating primal and dual
9. Ellipsoid Method - First polynomial-time LP algorithm (Khachiyan 1979)
10. Interior Point Methods - Karmarkar’s algorithm, practical polynomial-time method

11. LP Relaxation - Relaxing integer constraints for approximation algorithms
12. Primal-Dual Algorithms - Using LP duality for algorithm design
13. Column Generation - Solving LPs with exponentially many variables
14. Network Simplex - Specialized simplex for network flow problems
15. Semidefinite Programming - Optimization over positive semidefinite matrices

• Required:

  • Linear algebra (matrices, vectors, rank, systems of equations)
  • Basic multivariable calculus (gradients, for interior point methods)
  • Mathematical maturity for proof techniques
  • Understanding of basic algorithms and complexity

• Helpful:

  • Convex geometry
  • Graph algorithms (network flows as LP special case)
  • Basic optimization intuition

Setup: You run a factory making tables and chairs:

• Tables require 3 hours labor, 2 units wood, profit $50
• Chairs require 1 hour labor, 1 unit wood, profit $20
• You have 240 hours labor, 100 units wood available this week
• How many of each should you make to maximize profit?

Intuitive exploration:

• Make only tables? 240/3 = 80 tables max (but only 50 wood available, so 50 tables = $2500)
• Make only chairs? 100 chairs = $2000
• Mix? Must balance the resources cleverly

LP Formulation: Let x₁ = tables, x₂ = chairs

• Maximize: 50x₁ + 20x₂ (profit)
• Subject to:
  • 3x₁ + x₂ ≤ 240 (labor constraint)
  • 2x₁ + x₂ ≤ 100 (wood constraint)
  • x₁, x₂ ≥ 0 (non-negativity)

Graphical solution: Plot constraints as lines. Feasible region is polygon. Corners are:

• (0, 0): profit $0
• (50, 0): profit $2500
• (0, 100): profit $2000
• (20, 60): profit $2200 [intersection of constraints]

The revelation: Optimal solution is at a corner (vertex) of feasible region! This is NOT a coincidence—it’s fundamental.

The insight: This motivates simplex algorithm: walk from vertex to vertex, improving objective at each step.

Setup: Military needs to feed soldiers nutritiously at minimum cost. Each food has:

• Cost per unit
• Nutritional content (calories, protein, vitamins, etc.)

Find cheapest combination meeting all nutritional requirements.

Historical note: Dantzig actually solved this by hand before computers! 9 foods, 9 nutrients. The solution included 5 foods in specific quantities. Remarkably, the optimal diet was cheaper than anyone anticipated—but unpalatable (heavy on dried beans and flour).

Key insight: Optimal doesn’t mean desirable in all dimensions. This spawned “palatable” variants with additional constraints (minimum variety, maximum amounts of any single food).

The formulation:

• Variables: x_i = amount of food i
• Minimize: Σ(cost_i × x_i)
• Subject to: Σ(nutrient_{ij} × x_i) ≥ requirement_j for each nutrient j
• x_i ≥ 0

Why LP works here: Linear costs, linear nutritional contributions, linear constraints. Real world is approximately linear in this problem.

Setup: You’re selling your factory. A buyer offers to purchase your resources:

• w₁ = price per hour of labor
• w₂ = price per unit of wood

The buyer’s problem: Minimize 240w₁ + 100w₂ (total cost to buy your resources)

Your constraint: The prices must be high enough that you wouldn’t rather just produce and sell products yourself!

• To make table: requires 3 labor + 2 wood, gives $50. So: 3w₁ + 2w₂ ≥ 50
• To make chair: requires 1 labor + 1 wood, gives $20. So: w₁ + w₂ ≥ 20

The dual problem:

• Minimize: 240w₁ + 100w₂
• Subject to:
  • 3w₁ + 2w₂ ≥ 50
  • w₁ + w₂ ≥ 20
  • w₁, w₂ ≥ 0

The stunning result: The buyer’s minimum cost equals your maximum profit! This is strong duality.

Why this matters:

• Every LP has a dual LP
• Optimal values are equal (if feasible and bounded)
• Provides optimality certificates
• Fundamental to approximation algorithms

The economic interpretation: Prices of resources (dual) reflect their contribution to profit (primal). This connects LP to economic equilibrium theory.

Setup: Max flow problem—pump maximum flow from source to sink in network with capacity constraints.

LP formulation:

• Variables: f_e = flow on edge e
• Maximize: (flow out of source)
• Subject to:
  • f_e ≤ capacity_e for all edges (capacity constraints)
  • Flow conservation at each vertex (except source/sink)
  • f_e ≥ 0

The revelation: Network flow is just LP with special structure!

Special structure enables faster algorithms:

• Generic LP: polynomial but slow in practice
• Network simplex: exploits graph structure, much faster
• Max flow algorithms: specialized techniques (augmenting paths, push-relabel)

The lesson: LP is a unifying framework. Many specific algorithms can be viewed as exploiting structure in LP formulations.

Geometric intuition: Feasible region is a polyhedron. Optimal solution is at a vertex (assuming non-degenerate). Simplex walks from vertex to adjacent vertex, improving objective each step.

Algebraic description:

1. Start at basic feasible solution (vertex)
2. Choose entering variable (move along edge that improves objective)
3. Choose leaving variable (determine how far to move before hitting constraint)
4. Pivot: update basis, compute new solution
5. Repeat until no improving direction exists

Complexity:

• Worst case: exponential (Klee-Minty cube example)
• Practice: typically O(m) to O(3m) iterations for m constraints
• Remarkably efficient on real-world problems

Why it works despite exponential worst-case: Real problems have special structure that simplex exploits. Random perturbations (interior point starting, randomized pivoting) avoid pathological cases.

The breakthrough (1979): Khachiyan proved LP is in P using ellipsoid method.

The idea:

1. Start with ellipsoid containing feasible region
2. Query: is center feasible? If yes, try to improve objective. If no, a constraint is violated.
3. Constraint defines half-space. Feasible region is in this half-space.
4. Compute smallest ellipsoid containing intersection of current ellipsoid and half-space
5. Repeat until ellipsoid is tiny (convergence to optimum)

Complexity: Polynomial! O(n⁴L) where L = bit complexity of input.

Catch: Constant factors huge. Simplex is faster in practice despite exponential worst-case.

Impact: Theoretical breakthrough showing LP is tractable. Also gave polynomial algorithms for many problems reducible to LP (e.g., combinatorial optimization via ellipsoid + separation oracle).

The insight: Instead of walking on boundary (simplex), walk through interior of feasible region.

Barrier method approach:

1. Replace constraints with barrier function (logarithmic barriers)
2. Optimization problem becomes unconstrained but with barrier term
3. Use Newton’s method to optimize with current barrier weight
4. Gradually reduce barrier weight (approaching true optimum)

Complexity: Polynomial with small constants. O(n³L) iterations, each requiring O(m³) work for general LP.

Practice: Competitive with simplex on large-scale problems. Better worst-case guarantees.

Why it matters: Extends to convex optimization, semidefinite programming. Foundation of modern convex optimization solvers.

Primal problem:

• Maximize c^T x
• Subject to Ax ≤ b, x ≥ 0

Dual problem:

• Minimize b^T y
• Subject to A^T y ≥ c, y ≥ 0

Weak duality: For any feasible x (primal) and y (dual): c^T x ≤ b^T y

Primal objective ≤ Dual objective always!

Strong duality: If primal has optimal solution x*, dual has optimal solution y* with c^T x* = b^T y*

Gap closes at optimum!

Complementary slackness: At optimum, for each variable-constraint pair:

• If x_i > 0, then i-th dual constraint is tight
• If i-th primal constraint is slack, then y_i = 0

Why duality is powerful:

1. Certificates: Dual solution proves primal optimality
2. Bounds: Any dual feasible solution bounds primal objective
3. Algorithm design: Primal-dual algorithms maintain approximate primal and dual solutions, improving both toward optimality
4. Approximation: LP relaxation + rounding uses dual for analysis

• Chvátal: “Linear Programming” - Beautiful geometric intuition, clear proofs
• Bertsimas & Tsitsiklis: “Introduction to Linear Optimization” - Comprehensive, excellent exercises
• Vanderbei: “Linear Programming: Foundations and Extensions” - Practical focus with software
• Boyd & Vandenberghe: “Convex Optimization” - Modern treatment including interior point methods (free online)

• CMU 15-750/15-850 lecture notes (advanced algorithms courses covering LP)
• Stanford EE364a (Boyd) - Full video lectures on convex optimization
• MIT 6.854J/18.415J - Advanced algorithms with LP emphasis

• CPLEX, Gurobi - Commercial solvers (free for academics), extremely fast
• GLPK - Open source, good for teaching
• PuLP, CVXPY - Python modeling interfaces

• Dantzig (1947): Original simplex algorithm paper
• Khachiyan (1979): Ellipsoid method (LP in P)
• Karmarkar (1984): Polynomial interior point method
• Spielman & Teng (2004): Smoothed analysis of simplex (explains practical efficiency)

• Network Flows: Special case of LP with graph structure; network simplex is specialized algorithm
• Approximation Algorithms: LP relaxation + rounding gives approximation algorithms for NP-hard problems (vertex cover, set cover, TSP)
• Game Theory: Nash equilibria computable via LP (for zero-sum games)
• Machine Learning: SVM training is QP (quadratic program); many ML problems have LP/convex formulations
• Randomized Algorithms: Randomized rounding of LP solutions
• Semidefinite Programming: Generalization of LP; powerful tool for approximation (Goemans-Williamson MAX-CUT)
• Online Algorithms: Multiplicative weights method connects to online LP
• Computational Geometry: Many geometric optimization problems reduce to LP

1. Simplex Visualizer

   • Implement simplex algorithm with step-by-step visualization
   • Show feasible region, objective function, pivot steps
   • Compare performance on different problem structures
   • Demonstrate Klee-Minty cube (exponential worst case)

2. Diet Problem Solver

   • Build nutritional optimization system with food database
   • Allow constraints on nutrients, variety, palatability
   • Solve with LP, display results with explanations
   • Explore dual solution (shadow prices of nutrients)

3. Airline Crew Scheduling (Simplified)

   • Model small airline scheduling problem
   • Implement column generation for large-scale version
   • Visualize schedules and resource utilization
   • Compare LP solution to heuristics

4. LP-Based Approximation Algorithms

   • Implement vertex cover via LP relaxation and rounding
   • Implement set cover with greedy and LP rounding
   • Compare approximation ratios empirically
   • Visualize primal-dual algorithm execution

5. Portfolio Optimization

   • Implement Markowitz portfolio theory
   • Formulate as LP/QP with risk constraints
   • Add real-world constraints (transaction costs, diversification)
   • Backtest strategies on historical data

6. Network Flow as LP

   • Implement max flow as LP
   • Compare LP solver vs. specialized algorithm (Ford-Fulkerson, Dinic)
   • Visualize dual solution (min cut)
   • Explore min-cost flow variants

3-5 lectures depending on depth

• 2 lectures: LP formulation, graphical method, simplex algorithm basics, duality introduction
• 3 lectures: + Full duality theory, complementary slackness, sensitivity analysis
• 4 lectures: + Ellipsoid method or interior point methods, LP-based approximations
• 5 lectures: + SDP introduction, column generation, advanced applications

1. “Simplex is slow because it’s exponential worst-case”

   • FALSE! Simplex is extremely fast in practice. Smoothed analysis explains this: typical problems avoid pathological cases. Commercial solvers handle millions of variables routinely.

2. “LP can only solve problems with linear objectives”

   • FALSE! Many nonlinear problems approximate well with piecewise linear functions. Also, LP is foundation for solving broader convex problems via barrier methods.

3. “Duality is just a theoretical curiosity”

   • FALSE! Duality is essential for practical algorithm design (primal-dual algorithms), approximation analysis, and economic interpretation. It’s one of LP’s most powerful features.

4. “Integer programming is just LP with integrality constraints”

   • TRUE but misleading! IP is NP-hard while LP is P. Adding integrality fundamentally changes difficulty. However, LP relaxations provide bounds and rounding strategies for IP.

5. “Interior point methods made simplex obsolete”

   • FALSE! Both have niches. Interior point better for very large dense problems; simplex better for sparse problems and when warm-starting (resolving with small changes). Modern solvers use both.

Operations research and logistics:

• Supply chain optimization
• Vehicle routing and scheduling
• Facility location
• Inventory management
• Production planning

Finance and economics:

• Portfolio optimization
• Risk management
• Option pricing (linear approximations)
• General equilibrium computation

Energy and utilities:

• Power grid optimization
• Electricity market clearing
• Unit commitment (power plant scheduling)
• Network design and expansion

Manufacturing:

• Cutting stock problem (minimizing waste)
• Blending problems (oil refining, animal feed)
• Workforce scheduling
• Project scheduling (CPM/PERT)

Machine learning:

• SVM training
• Basis pursuit (sparse signal recovery)
• Online learning (multiplicative weights)
• Structured prediction

Telecommunications:

• Network flow allocation
• Bandwidth optimization
• Routing and congestion control

Traditional (banking model):

“Linear programming optimizes linear functions subject to linear constraints. Here’s the standard form. Here’s the simplex algorithm. Memorize the pivot rules.”

Problem-posing approach:

“You have limited resources and multiple ways to use them. How do you decide what to do to maximize profit? Let’s model this mathematically… We get linear equations! How do we solve this system? Let’s visualize—the solution is at a corner! How do we get there efficiently? This leads us to discover the simplex method…”

The difference: Students see WHY optimization matters (real economic decisions), discover mathematical structure organically (constraints form polyhedron, optimum at vertex), and understand algorithmic choices (move from vertex to vertex) rather than memorizing mechanical procedures.

Curriculum placement:

• Week 6-10 for graduate courses (after graph algorithms, often alongside/before approximation algorithms)
• Often a standalone advanced course (linear and convex optimization)
• Essential background for approximation algorithms and algorithmic game theory

Prerequisites check: Students need solid linear algebra. Understanding eigenvalues/eigenvectors helpful for interior point methods but not essential for simplex and duality.

Why this timing: LP provides a powerful lens for viewing many algorithms topics. It’s best covered mid-sequence so that:

• Students have algorithmic maturity
• Connections to other topics (flows, approximation) can be made immediately
• Applications in later topics (game theory, ML) can build on LP foundation

The optimization age: Modern applications generate increasingly complex optimization problems:

• E-commerce: Real-time pricing and inventory optimization
• Ride-sharing: Dynamic pricing and dispatch (Uber, Lyft solve massive LPs continuously)
• Advertising: Ad allocation in auctions (Google, Facebook)
• Supply chains: Global logistics requiring optimization at unprecedented scale
• Healthcare: Resource allocation, scheduling, treatment planning
• Sustainability: Optimizing energy systems for renewable integration

Computational advances: Modern LP solvers are engineering marvels:

• Solve problems with millions of variables in seconds
• Exploit parallel hardware (GPUs)
• Handle mixed-integer programming (MIP) via sophisticated branch-and-bound

Theoretical developments continue:

• Improved algorithms for special structure (network flows, submodular optimization)
• Connections to machine learning (online convex optimization, regret minimization)
• Fast approximation algorithms using LP rounding
• Understanding LP geometry via spectral methods

Cross-disciplinary reach expanding: LP thinking permeates many fields:

• Economics: Market equilibrium and pricing theory
• Biology: Metabolic flux analysis
• Physics: Energy minimization problems
• Social sciences: Resource allocation and fairness

Understanding LP and its extensions (convex optimization, SDP) is essential for modern algorithm designers and researchers across disciplines.

Ready for students? ✓ Yes - strong practical motivation, clear progression from simple to complex, rich theoretical content (duality), extensive real-world applications, provides foundation for approximation algorithms and game theory.