How Linear Programming Solves Real-World Optimization Problems

Airlines Save Hundreds of Millions of Dollars Using a Technique Developed in 1947

American Airlines first applied linear programming to crew scheduling in the 1980s and estimated annual savings of $18 million. FedEx uses LP to route approximately 400 daily cargo flights. The U.S. military used LP to plan logistics during World War II before the formal algorithm even existed. George Dantzig formalized the simplex method in 1947 at the RAND Corporation, and it became one of the most consequential algorithms ever developed for practical computation.

Linear programming (LP) finds the maximum or minimum value of a linear function subject to a set of linear constraints. The word "programming" in its name has nothing to do with computer code — it derives from "program" as in a plan or schedule, reflecting the method's origins in military logistics planning.

The Structure of a Linear Program

Every LP consists of three components:

• Decision variables: The quantities to be determined — how many units to produce, how many packages to ship by which route, how much to invest in each asset.
• Objective function: A linear function of the decision variables to be maximized or minimized — total profit, total cost, total weight.
• Constraints: Linear inequalities or equalities limiting feasible values — available raw material, machine capacity, budget limits, minimum requirements.

A standard LP in matrix form: maximize c^T x subject to Ax ≤ b, x ≥ 0. Here, x is the vector of decision variables, c is the vector of objective coefficients, A is the constraint matrix, and b is the right-hand side vector of constraint limits.

The Geometry of Linear Programming

The feasible region of an LP — the set of all points satisfying every constraint — is a convex polytope in n-dimensional space. For two-variable problems, this is visible as a polygon in the x-y plane. The objective function is a line (or hyperplane in higher dimensions) being "pushed" in the direction of optimization.

A fundamental theorem guarantees that if an LP has an optimal solution, it occurs at a vertex (corner point) of the feasible polytope. This is not obvious geometrically in high dimensions, but it is exactly what the simplex method exploits: rather than searching the entire feasible region, it walks along edges from vertex to vertex, improving the objective at each step, until no improving edge exists.

The Simplex Method: Elegant and Fast in Practice

Dantzig's simplex algorithm works by moving between adjacent vertices of the feasible polytope. At each step, it identifies a pivot element — a variable to increase and another to decrease — that improves the objective value. It continues until no improving pivot exists, at which point the current vertex is optimal.

Theoretically, the simplex method can visit exponentially many vertices before reaching the optimal. In practice, it solves most real-world problems in a number of steps proportional to the number of constraints — a fact that is understood empirically but not fully proven theoretically. Average-case performance is excellent.

Interior point methods — developed by Narendra Karmarkar in 1984 — offer a theoretical polynomial-time alternative by traversing the interior of the feasible region. For very large problems, interior point methods are often faster than simplex. Modern commercial solvers switch between approaches.

Duality: Every LP Has a Mirror Problem

One of the most powerful theoretical results in LP is duality. Every maximization LP (the "primal") corresponds to a related minimization LP (the "dual"), and vice versa. The dual variables have economic interpretations as shadow prices — the marginal value of relaxing each constraint by one unit.

• If producing widgets is constrained by available steel, the shadow price on the steel constraint tells you how much extra profit one additional ton of steel would generate.
• Strong duality theorem: at optimality, the primal and dual objective values are equal. This provides a certificate of optimality.
• Complementary slackness conditions: if a constraint is not binding (slack is positive), its dual variable is zero. If a dual variable is positive, its constraint is binding. These conditions characterize all optimal solutions.

Extensions: Integer and Mixed-Integer Programming

Many real decisions require integer values — you cannot buy half a machine or assign 0.7 pilots to a flight. Integer programming adds integrality constraints: variables must take integer values. Mixed-integer programming (MIP) allows some variables to be continuous and others integer.

Integrality makes the problem NP-hard in general. Practical solvers (CPLEX, Gurobi, SCIP) use branch-and-bound — solving LP relaxations and branching on fractional variables — combined with cutting planes and heuristics. Modern MIP solvers can handle problems with hundreds of thousands of binary variables in reasonable time through these techniques.

Real Applications That Shape Daily Life

Linear programming is embedded in systems most people interact with constantly:

• Airline crew scheduling: Assigning crews to flights while satisfying rest rules, union agreements, and qualification requirements. Delta Air Lines' crew optimization problem has millions of variables.
• Electric grid dispatch: Power grid operators solve LP-based economic dispatch problems every few minutes, determining which generators produce how much power to meet demand at minimum cost while respecting transmission line limits.
• Portfolio optimization: Markowitz mean-variance portfolio optimization is a quadratic program — a natural extension of LP — that determines the allocation of assets to maximize expected return for a given risk level.
• Food and beverage blending: Breweries, refineries, and feed mills use LP to determine the least-cost blend of ingredients meeting product specifications.

In 1975, Leonid Kantorovich and Tjalling Koopmans won the Nobel Prize in Economics partly for their work applying LP to resource allocation problems. The recognition validated what practitioners already knew: linear programming is not a mathematical curiosity but a fundamental tool for making optimal decisions under constraint.