Linear Programming – Optimization, Duality & Applications | Chapter 29 in Introduction to Algorithms

Chapter 29 of Introduction to Algorithms presents a comprehensive foundation in linear programming (LP), a powerful optimization tool widely used in computer science, operations research, and economics. The chapter walks through how to formulate LP problems, introduces geometric intuition, and compares algorithmic approaches like the simplex method, ellipsoid algorithm, and interior-point methods. It also explores advanced topics such as duality theory and integer linear programming (ILP).

Watch the full video above for a visual summary of Chapter 29, and be sure to subscribe to Last Minute Lecture for more high-quality textbook breakdowns every week.

What Is Linear Programming?

Linear programming is a method for optimizing a linear objective function subject to linear equality and inequality constraints. A typical LP seeks to maximize or minimize an expression like cᵗx, where x is a vector of decision variables and the solution must satisfy constraints expressed in the form Ax ≥ b and x ≥ 0.

Key Components:

• Decision Variables: The unknowns to optimize (e.g., x₁, x₂, ...)
• Constraints: Linear inequalities or equalities that restrict variable values
• Objective Function: A linear expression to maximize or minimize

One classic example given in the chapter is the political advertising problem, where the goal is to minimize advertising costs while satisfying regional voting targets.

Feasibility, Boundedness, and Optimality

Understanding solution types is essential in LP:

• Feasible Solution: Satisfies all constraints
• Infeasible Solution: Violates one or more constraints
• Bounded LP: The objective function has a finite optimal value
• Unbounded LP: The objective can grow without bound within the feasible region
• Optimal Solution: A feasible solution with the best objective value

In two-variable problems, these solutions can be visualized geometrically—the feasible region forms a convex polygon, and the optimal point often lies at one of its vertices (corners).

Algorithms for Solving Linear Programs

Chapter 29 compares several algorithms used in practice and theory:

• Simplex Method: Moves along edges of the feasible region to reach optimality. Though it has exponential worst-case complexity, it's very fast in practice.
• Ellipsoid Algorithm: First algorithm to solve LPs in polynomial time; significant theoretically but slower in practice.
• Interior-Point Methods: Polynomial-time algorithms that travel through the interior of the feasible region. These are more efficient for large, sparse problems.

Applications and Geometric Intuition

Linear programs model many real-world optimization problems:

• Single-Source Shortest Path: Can be formulated as an LP using triangle inequality constraints.
• Maximum Flow and Minimum-Cost Flow: Modeled by setting flow conservation, capacity, and cost constraints.
• Multicommodity Flow: Involves multiple flows sharing a network while respecting shared capacities.

The geometric understanding of LPs—visualizing half-spaces and convex regions—helps explain why optimal solutions often occur at vertices and how constraints shape the solution space.

Duality in Linear Programming

Every LP (called the primal) has an associated dual problem. The dual swaps the roles of constraints and decision variables:

• Weak Duality: The value of the primal is always less than or equal to the dual.
• Strong Duality: If both problems are feasible, their optimal values are equal.
• Complementary Slackness: Links primal and dual solutions at optimality.

These principles are essential for verifying optimality and for the design of efficient algorithms. Farkas’s Lemma provides the theoretical foundation for feasibility and duality.

Integer Linear Programming (ILP)

When variables must take integer values, we enter the realm of integer linear programming—a significantly more complex problem class. ILP is NP-hard and cannot be solved efficiently in general. Techniques used include:

• Branch-and-bound
• Cutting planes
• Relaxation methods

ILPs are common in scheduling, routing, and resource allocation problems where partial values aren’t meaningful.

Conclusion

Linear programming is one of the most versatile and widely used optimization frameworks in modern computation. Chapter 29 provides the foundational tools and theoretical insights to formulate and solve LPs, interpret geometric constraints, and apply them across a range of real-world problems. Understanding simplex geometry, duality, and LP-solving algorithms is essential for anyone studying computer science, engineering, or applied mathematics.

👉 Want a fast, visual guide to this chapter? Watch the embedded video above and explore more on the Last Minute Lecture channel.

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.