Introduction

Linear Programming (LP) is one of the most important and widely used optimization techniques in computer science, operations research, and applied mathematics. Unlike many optimization problems that are NP-complete, Linear Programming can be solved efficiently in polynomial time, making it a powerful tool for solving real-world optimization problems. This post provides a comprehensive introduction to Linear Programming, covering its theory, algorithms, and applications.

What is Linear Programming?

Linear Programming is a mathematical optimization technique for finding the best outcome (maximum or minimum) of a linear objective function subject to linear equality and inequality constraints.

Problem Definition

Linear Programming Problem:

Input:

  • Variables: x₁, x₂, …, x_n (real numbers)
  • Objective function: c₁x₁ + c₂x₂ + … + c_nx_n (linear)
  • Constraints: Linear inequalities or equations
  • Domain: Variables may be restricted (e.g., xᵢ ≥ 0)

Output:

  • Values for variables that satisfy all constraints
  • Optimize (maximize or minimize) the objective function

Key Characteristics

  1. Linearity: All functions (objective and constraints) are linear
  2. Continuous Variables: Variables can take any real values (unlike integer programming)
  3. Convexity: Feasible region is a convex polyhedron
  4. Polynomial-Time Solvable: Can be solved efficiently

Standard Forms

Linear Programming problems can be written in different standard forms. Understanding these forms is crucial for applying algorithms.

Standard Form (Inequality Form)

Maximize: c^T x

Subject to:

  • Ax ≤ b
  • x ≥ 0

Where:

  • A is an m × n matrix (constraint coefficients)
  • b is an m-dimensional vector (right-hand side)
  • c is an n-dimensional vector (objective coefficients)
  • x is an n-dimensional vector (decision variables)

Canonical Form (Equality Form)

Maximize: c^T x

Subject to:

  • Ax = b
  • x ≥ 0

Conversion: Add slack variables to convert inequalities to equalities:

  • Constraint: a₁x₁ + a₂x₂ ≤ b becomes a₁x₁ + a₂x₂ + s = b, s ≥ 0
  • Slack variable s represents the “slack” or unused capacity

General Form Conversions

Minimization → Maximization:

  • Minimize c^T x ↔ Maximize -c^T x

Unrestricted Variables:

  • Variable x unrestricted ↔ Replace with x = x⁺ - x⁻ where x⁺, x⁻ ≥ 0

≥ Constraints:

  • a^T x ≥ b ↔ -a^T x ≤ -b

Equality Constraints:

  • a^T x = b ↔ a^T x ≤ b and a^T x ≥ b

Geometric Interpretation

Understanding the geometry of Linear Programming provides crucial intuition.

Feasible Region

Definition: The set of all points x that satisfy all constraints.

Properties:

  • Convex Polyhedron: Intersection of half-spaces (from inequalities)
  • Vertices: Corner points of the polyhedron
  • Edges: Lines connecting vertices
  • Faces: Flat surfaces bounding the polyhedron

Fundamental Theorem of Linear Programming

Theorem: If an LP has an optimal solution, then there exists an optimal solution at a vertex (extreme point) of the feasible region.

Implications:

  • We only need to check vertices, not all points
  • This is why algorithms like Simplex work (they move between vertices)
  • Number of vertices can be exponential, but algorithms are still efficient

Example: 2D Visualization

Consider the LP:

Maximize: 3x₁ + 2x₂

Subject to:

  • 2x₁ + x₂ ≤ 6
  • x₁ + 2x₂ ≤ 8
  • x₁, x₂ ≥ 0

Feasible Region:

  • Bounded polygon (quadrilateral)
  • Vertices: (0,0), (0,4), (4/3, 10/3), (3,0)
  • Optimal solution: (4/3, 10/3) with value 32/3 ≈ 10.67

Graphical Method:

  1. Plot constraints as lines
  2. Identify feasible region (intersection of half-spaces)
  3. Plot objective function as a line
  4. Move objective line parallel to itself to find optimal vertex

Algorithms for Linear Programming

1. Simplex Method

Inventor: George Dantzig (1947)

Basic Idea: Move from vertex to vertex along edges, improving objective at each step.

Algorithm Outline:

  1. Start at a feasible vertex (basic feasible solution)
  2. While not optimal:
    • Choose a non-basic variable to enter basis (improves objective)
    • Choose a basic variable to leave basis (maintains feasibility)
    • Pivot: update tableau
  3. Return optimal solution

Key Concepts:

  • Basic Variables: Variables set to their bounds (usually 0)
  • Non-Basic Variables: Variables that can change
  • Basis: Set of basic variables
  • Tableau: Matrix representation of the LP
  • Pivoting: Moving from one basis to another

Advantages:

  • Very efficient in practice
  • Often requires O(m) to O(m+n) iterations
  • Can handle degeneracy

Disadvantages:

  • Exponential worst-case time (Klee-Minty examples)
  • Can cycle if not careful (Bland’s rule prevents this)

Time Complexity:

  • Worst-case: Exponential (2^n iterations possible)
  • Average-case: Polynomial (O(m+n) iterations typical)
  • Practical: Very fast, often faster than polynomial methods

2. Ellipsoid Method

Inventor: Leonid Khachiyan (1979)

Basic Idea: Shrink an ellipsoid containing the feasible region until finding a solution.

Algorithm Outline:

  1. Start with large ellipsoid containing feasible region
  2. While ellipsoid is large:
    • Check if center is feasible
    • If not, use violated constraint to shrink ellipsoid
    • Update ellipsoid
  3. Return solution

Significance:

  • First polynomial-time algorithm for LP
  • Proved LP ∈ P theoretically

Time Complexity:

  • O(n^4 L) where L is input size (bit complexity)

Disadvantages:

  • Large constants make it impractical
  • Not used in practice

3. Interior-Point Methods

Inventor: Narendra Karmarkar (1984)

Basic Idea: Move through the interior of the feasible region toward the optimal solution.

Algorithm Outline:

  1. Start at interior point
  2. While not optimal:
    • Compute search direction (toward optimal)
    • Choose step size (stay in interior)
    • Update solution
  3. Return optimal solution

Key Concepts:

  • Barrier Function: Keeps solution away from boundaries
  • Newton’s Method: Used to compute search direction
  • Path-Following: Follow central path to optimal solution

Advantages:

  • Polynomial-time: O(n^{3.5} L)
  • Practical and efficient
  • Widely used in modern solvers

Time Complexity:

  • O(n^{3.5} L) using path-following methods
  • Typically O(√n log(1/ε)) iterations for ε-accuracy

Modern Variants:

  • Primal-dual interior-point methods
  • Predictor-corrector methods
  • Self-dual embedding

4. Comparison of Methods

Method Worst-Case Average-Case Practical Use
Simplex Exponential Polynomial Very common
Ellipsoid Polynomial Polynomial Rarely used
Interior-Point Polynomial Polynomial Very common

Modern Solvers: Use combination of methods:

  • Simplex for warm starts
  • Interior-point for initial solution
  • Hybrid approaches

Duality Theory

Duality is one of the most beautiful and powerful concepts in Linear Programming.

Primal and Dual Problems

Primal LP:

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

Dual LP:

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

Key Relationship: Every LP has a corresponding dual LP.

Duality Theorems

Weak Duality Theorem:

  • For any feasible x (primal) and y (dual): c^T x ≤ b^T y
  • Dual provides upper bound for primal (maximization)
  • Primal provides lower bound for dual (minimization)

Strong Duality Theorem:

  • If both primal and dual have feasible solutions, then:
    • Primal optimal = Dual optimal
  • If one is unbounded, the other is infeasible
  • If one is infeasible, the other is either infeasible or unbounded

Complementary Slackness:

  • At optimality:
    • If constraint is not tight, corresponding dual variable = 0
    • If dual constraint is not tight, corresponding primal variable = 0

Economic Interpretation

Primal: Resource allocation problem

  • Variables: Amount of each activity
  • Objective: Maximize profit
  • Constraints: Resource limitations

Dual: Pricing problem

  • Variables: Prices (shadow prices) of resources
  • Objective: Minimize total cost
  • Constraints: Activities must be profitable

Shadow Prices: Dual variables represent the value of an additional unit of each resource.

Example: Duality

Primal:

  • Maximize: 3x₁ + 2x₂
  • Subject to: 2x₁ + x₂ ≤ 6, x₁ + 2x₂ ≤ 8, x₁, x₂ ≥ 0

Dual:

  • Minimize: 6y₁ + 8y₂
  • Subject to: 2y₁ + y₂ ≥ 3, y₁ + 2y₂ ≥ 2, y₁, y₂ ≥ 0

Optimal Solutions:

  • Primal: (4/3, 10/3) with value 32/3
  • Dual: (4/3, 1/3) with value 32/3
  • Both have same optimal value (Strong Duality)

Special Cases and Degeneracy

Unbounded Problems

Definition: Objective can be made arbitrarily large (maximization) or small (minimization).

Causes:

  • Feasible region is unbounded
  • Objective direction points toward unbounded direction

Detection: Simplex method identifies unboundedness when no variable can leave basis.

Infeasible Problems

Definition: No solution satisfies all constraints.

Causes:

  • Conflicting constraints
  • Over-constrained problem

Detection: Phase I of Simplex method detects infeasibility.

Degeneracy

Definition: More than m constraints are tight at a vertex (where m is number of constraints).

Causes:

  • Redundant constraints
  • Special problem structure

Issues:

  • Simplex may cycle (use Bland’s rule to prevent)
  • May require extra iterations

Multiple Optimal Solutions

Definition: More than one optimal solution exists.

Causes:

  • Objective function parallel to a face of feasible region
  • Entire face is optimal

Characterization: If x* and x** are both optimal, then any convex combination is also optimal.

Applications of Linear Programming

1. Resource Allocation

Problem: Allocate limited resources to maximize profit or minimize cost.

Example: Production planning

  • Resources: Labor, materials, machine time
  • Products: Different products with different resource requirements
  • Objective: Maximize profit

Formulation:

  • Variables: Amount of each product to produce
  • Constraints: Resource limitations
  • Objective: Total profit

2. Transportation Problems

Problem: Transport goods from sources to destinations at minimum cost.

Example: Shipping

  • Sources: Warehouses with supply
  • Destinations: Stores with demand
  • Costs: Shipping cost per unit from each source to each destination
  • Objective: Minimize total shipping cost

Formulation:

  • Variables: Amount shipped from each source to each destination
  • Constraints: Supply limits, demand requirements
  • Objective: Total shipping cost

3. Network Flow Problems

Problem: Send maximum flow through a network.

Example: Data routing, water distribution

  • Network: Graph with capacities on edges
  • Source and sink: Where flow starts and ends
  • Objective: Maximize flow

Formulation:

  • Variables: Flow on each edge
  • Constraints: Flow conservation, capacity limits
  • Objective: Flow from source to sink

Note: Specialized algorithms (Ford-Fulkerson) are faster than general LP.

4. Diet Problem

Problem: Find cheapest diet meeting nutritional requirements.

Example: Meal planning

  • Foods: Different foods with different nutrients and costs
  • Requirements: Minimum amounts of each nutrient
  • Objective: Minimize cost

Formulation:

  • Variables: Amount of each food
  • Constraints: Nutritional requirements
  • Objective: Total cost

5. Portfolio Optimization

Problem: Allocate investments to maximize return subject to risk constraints.

Example: Financial planning

  • Investments: Stocks, bonds with expected returns and risks
  • Constraints: Risk limits, budget
  • Objective: Maximize expected return

Formulation:

  • Variables: Fraction of portfolio in each investment
  • Constraints: Risk limits, budget (sum to 1)
  • Objective: Expected return

6. Scheduling Problems

Problem: Schedule tasks to minimize completion time or maximize resource utilization.

Example: Project scheduling, workforce scheduling

  • Tasks: Activities with durations and resource requirements
  • Resources: Limited resources (workers, machines)
  • Constraints: Precedence, resource availability
  • Objective: Minimize makespan or maximize utilization

Formulation:

  • Variables: Start times or resource assignments
  • Constraints: Precedence, resource limits
  • Objective: Completion time or utilization

Computational Complexity

Polynomial-Time Solvability

Result: Linear Programming ∈ P

Proof: Interior-point methods solve LP in polynomial time:

  • Time: O(n^{3.5} L) where L is input size
  • Space: O(n²) for storing matrices

Significance: Unlike Integer Linear Programming (NP-complete), LP is efficiently solvable.

Input Size

Definition: Number of bits needed to represent the input.

Components:

  • Matrix A: O(mn log(max aᵢⱼ ))
  • Vector b: O(m log(max bᵢ ))
  • Vector c: O(n log(max cⱼ ))

Total: L = O(mn log(max coefficients))

Practical Performance

Modern Solvers:

  • Can solve problems with millions of variables and constraints
  • Use preprocessing, advanced algorithms, parallel processing
  • Very efficient in practice

Typical Performance:

  • Small problems (< 1000 variables): Milliseconds
  • Medium problems (1000-100000 variables): Seconds to minutes
  • Large problems (> 100000 variables): Minutes to hours

Software and Tools

Commercial Solvers

CPLEX (IBM):

  • Industry standard
  • Very fast and robust
  • Good for large-scale problems

Gurobi:

  • Excellent performance
  • Good academic licenses
  • Modern, well-documented

XPRESS:

  • Commercial solver
  • Good performance

Open-Source Solvers

GLPK (GNU Linear Programming Kit):

  • Free and open-source
  • Good for small to medium problems

CLP (COIN-OR Linear Programming):

  • Part of COIN-OR project
  • Free and open-source

HiGHS:

  • Modern, high-performance
  • Open-source
  • Actively developed

Modeling Languages and Interfaces

Python:

  • PuLP: Simple, intuitive interface
  • CVXPY: More advanced, supports conic programming
  • OR-Tools: Google’s optimization tools

Julia:

  • JuMP: Mathematical modeling language
  • Very fast and expressive

MATLAB:

  • linprog: Built-in LP solver
  • Optimization Toolbox: More advanced features

R:

  • lpSolve: R interface to lp_solve
  • Rglpk: Interface to GLPK

Formulating Problems as LPs

Step-by-Step Process

  1. Identify Decision Variables:
    • What quantities do we need to decide?
    • What are the units?
  2. Formulate Objective Function:
    • What are we trying to optimize?
    • Is it maximize or minimize?
    • Write as linear function of variables
  3. Identify Constraints:
    • What limitations exist?
    • What relationships must hold?
    • Write as linear inequalities or equations
  4. Specify Variable Domains:
    • Are variables non-negative?
    • Are there upper bounds?
  5. Verify Linearity:
    • All functions must be linear
    • No products, powers, or nonlinear functions

Common Formulation Patterns

Pattern 1: Allocation

  • Variables: Amount allocated to each option
  • Constraints: Total allocation limits
  • Objective: Maximize value or minimize cost

Pattern 2: Selection

  • Variables: Binary (0-1) selection variables
  • Constraints: Must select certain combinations
  • Objective: Maximize value of selection

Pattern 3: Flow

  • Variables: Flow on each edge/path
  • Constraints: Flow conservation, capacity
  • Objective: Maximize flow or minimize cost

Pattern 4: Assignment

  • Variables: Assignment indicators
  • Constraints: Each item assigned exactly once
  • Objective: Minimize total assignment cost

Sensitivity Analysis

Sensitivity analysis studies how changes in input parameters affect the optimal solution.

Shadow Prices (Dual Variables)

Definition: Rate of change in optimal objective value per unit change in right-hand side.

Interpretation: Value of an additional unit of each resource.

Use: Determine which resources are most valuable.

Reduced Costs

Definition: Rate of change in optimal objective value per unit change in objective coefficient.

Interpretation: How much objective coefficient must change before variable enters basis.

Use: Determine which activities are profitable.

Range Analysis

Right-Hand Side Ranges:

  • Range of b values for which current basis remains optimal
  • Shows sensitivity to constraint changes

Objective Coefficient Ranges:

  • Range of c values for which current solution remains optimal
  • Shows sensitivity to objective changes

Key Takeaways

  1. LP is Polynomial-Time: Can be solved efficiently using interior-point methods
  2. Geometric Intuition: Optimal solutions occur at vertices
  3. Duality: Every LP has a dual providing bounds and insights
  4. Wide Applications: Used in many real-world optimization problems
  5. Formulation Skills: Key to applying LP successfully
  6. Modern Solvers: Very efficient and can handle large problems
  7. Foundation for Advanced Topics: Basis for Integer Programming, Approximation Algorithms

Practice Problems

  1. Formulate as LP: A company produces two products. Product 1 requires 2 hours of labor and 1 unit of material, sells for $10. Product 2 requires 1 hour of labor and 2 units of material, sells for $15. Available: 100 hours labor, 80 units material. Maximize profit.

  2. Graphical Solution: Solve the LP from problem 1 graphically. Identify vertices and optimal solution.

  3. Standard Form: Convert the following to standard form:
    • Minimize: x₁ - 2x₂
    • Subject to: x₁ + x₂ = 5, x₁ ≥ 0, x₂ unrestricted
  4. Dual Problem: Write the dual of:
    • Maximize: 3x₁ + 2x₂
    • Subject to: 2x₁ + x₂ ≤ 6, x₁ + 2x₂ ≤ 8, x₁, x₂ ≥ 0

  5. Simplex Method: Solve a small LP using the Simplex method manually. Show all tableaus.

  6. Applications: Research one real-world application of LP. Formulate it as an LP problem.

  7. Sensitivity: For a solved LP, interpret shadow prices. What do they mean in the context of the problem?

  8. Special Cases: Construct examples of:
    • Unbounded LP
    • Infeasible LP
    • Degenerate LP
    • Multiple optimal solutions

  9. Network Flow: Formulate a maximum flow problem as an LP. How does it differ from using specialized algorithms?

  10. Software: Use a solver (PuLP, CVXPY, or other) to solve a small LP problem. Compare with manual solution.

Further Reading

  • Textbooks:
    • Chvátal: “Linear Programming” - Classic, comprehensive
    • Vanderbei: “Linear Programming: Foundations and Extensions” - Modern, clear
    • Bertsimas & Tsitsiklis: “Introduction to Linear Optimization” - Rigorous
  • Algorithms:
    • Dantzig: “Linear Programming and Extensions” - Original Simplex method
    • Nesterov & Nemirovskii: “Interior-Point Polynomial Algorithms” - Interior-point methods
  • Applications:
    • Hillier & Lieberman: “Introduction to Operations Research” - Applications focus
    • Taha: “Operations Research” - Practical applications
  • Software Documentation:
    • CPLEX, Gurobi, or other solver documentation
    • PuLP, CVXPY, or JuMP tutorials

Linear Programming is a fundamental optimization technique with wide-ranging applications. Understanding its theory, algorithms, and formulation techniques provides a strong foundation for tackling optimization problems in computer science, operations research, and many other fields. The polynomial-time solvability of LP makes it a powerful tool, while its relationship to Integer Linear Programming (through LP relaxation) connects it to NP-complete problems and approximation algorithms.