Summary of "The Art of Linear Programming"

Purpose

Introduce linear programming (LP): how to model and solve LPs geometrically and with the Simplex algorithm, explain duality and how it proves optimality, and show how integer constraints lead to integer linear programming (ILP) and NP‑hard problems (example: knapsack). Short Python examples using the pulp package are shown.

Takeaway: LPs are problems of maximizing (or minimizing) a linear objective subject to linear inequalities. Geometrically the feasible region is a convex polyhedron and an optimum (if it exists) is attained at a vertex. The Simplex algorithm walks vertex-to-vertex to find that optimum; duality gives certificates of optimality; adding integer constraints usually makes the problem much harder (often NP‑hard), but practical solvers can still be effective.

Main ideas, concepts and lessons

1. What is a linear program (LP)

Variables are real (often nonnegative).
Constraints are linear inequalities; each constraint defines a half‑plane (2D) or half‑space (higher D).
The objective is a linear function to maximize or minimize.
The feasible region is the intersection of the half‑spaces — a convex polyhedron.
Optimum property: if an optimum exists, at least one vertex (extreme point) of the feasible region attains it.

2. Worked example — “farmer’s problem”

Data:
- Potato seed: 3 tons = 3000 kg
- Carrot seed: 4 tons = 4000 kg
- Fertilizer: 5 tons = 5000 kg (used 1:1 with seeds)
- Profit: $1.20/kg potatoes, $1.70/kg carrots
Variables:
- x_p = kilograms of potatoes (≥ 0)
- x_c = kilograms of carrots (≥ 0)
Constraints:
- x_p ≤ 3000 (seed availability)
- x_c ≤ 4000
- x_p + x_c ≤ 5000 (fertilizer limit)
Objective: maximize 1.2 x_p + 1.7 x_c
Geometric solution: plot feasible polygon and move level lines of the objective until last contact; optimum at the vertex x_p = 1000 kg, x_c = 4000 kg, profit = $8000.

3. The Simplex method (vertex‑walking algorithm)

Key idea: since an optimum occurs at a vertex, move from vertex to adjacent vertex (pivot) improving the objective until no improvement is possible.

Preparation - Convert ≤ constraints to equalities by adding slack variables (one slack per ≤): slack = RHS − LHS. Slack = 0 means the constraint is tight. - Partition variables into basic (currently nonzero in the basis) and nonbasic (set to zero). - Rewrite the system so each basic variable is isolated with coefficient 1 — the tableau / canonical form. Setting nonbasic = 0 gives the current basic feasible solution.

Numerical pivot steps 1. Choose an entering (nonbasic) variable to increase: typically pick the nonbasic variable with the largest positive coefficient in the objective row (Dantzig’s rule). 2. Determine how far it can increase without violating feasibility: for each row where the entering variable has positive coefficient, compute ratio = RHS / coefficient. The smallest nonnegative ratio identifies the leaving basic variable (minimum ratio test). 3. Perform the pivot: use the leaving variable’s equation to solve for the entering variable, substitute into other equations, and update the objective row. 4. Repeat until no positive coefficients remain in the objective row (for maximization); then the current basic feasible solution is optimal.

Notes and caveats - If the obvious starting vertex (e.g., origin) isn’t feasible, a Phase I method is needed to find an initial basic feasible solution. - Worst case: Simplex can be exponential time and can cycle; practical pivot rules and anti‑cycling measures mitigate these issues. - The video demonstrates two pivots on the farmer example and reaches the same optimal solution as the geometric method.

4. Slack variables and tableau bookkeeping

Slack variables convert ≤ constraints to equalities and measure how “loose” a constraint is.
Tableau form (basic variables expressed in terms of nonbasic variables and constants) makes reading the current solution and objective immediate by setting nonbasic = 0.

5. Duality (primal and dual programs)

Intuition: taking nonnegative linear combinations of primal constraints yields upper bounds on the primal objective; choosing multipliers cleverly tightens the bound.
Formalization: introduce nonnegative multipliers (dual variables) and minimize the weighted sum of RHSs subject to covering the primal objective coefficients — this is the dual LP.
Weak duality: any feasible primal objective value ≤ any feasible dual objective value (max primal ≤ min dual).
Strong duality: if the primal has an optimal finite solution, the optimal values of primal and dual are equal; solving the dual can certify primal optimality.
Uses beyond certification: sensitivity analysis, pricing, algorithm design (only a brief treatment in the video).

6. Integer linear programming (ILP) and NP‑hardness

Requiring variables to be integers (or binary) yields an ILP.
Knapsack example as an ILP:
- xi ∈ {0,1} indicate whether item i is chosen
- Constraint: sum(weight_i * xi) ≤ capacity
- Objective: maximize sum(value_i * xi)
Complexity: many ILPs (including knapsack) are NP‑hard. Modern solvers use branch‑and‑bound, cutting planes, heuristics, and other engineering techniques to solve many practical instances quickly.
The video shows pulp (Python) examples:
- A knapsack instance with optimal value 84 selecting items {2,4,5,6}
- The farmer’s LP solved in about 20 lines of code

7. Open questions and deeper topics (promised for future videos)

Finding an initial feasible basis when the origin isn’t feasible (Phase I methods).
Preventing cycling and dealing with worst‑case exponential behavior.
Construction and properties of duals for arbitrary LP forms.
Using duality in algorithm design (primal‑dual algorithms).
Classes of ILP solvable in polynomial time and approximation algorithms for hard cases.

Methodologies and step‑by‑step procedures

How to formulate a simple LP 1. Identify decision variables (typically real and nonnegative). 2. Write linear constraints from resource limits and relationships (≤, ≥, =). 3. Define a linear objective to maximize or minimize. 4. (Optional) Convert units so variables are in a convenient scale.

Converting LP for Simplex (practical steps) 1. Turn all ≤ constraints into equalities by adding slack variables. 2. Ensure variables are nonnegative; if not, express them as difference of nonnegatives or shift variables. 3. Arrange equalities so basic variables are isolated with coefficient 1 (tableau). 4. Set nonbasic variables to zero to read the initial basic feasible solution (if feasible).

Simplex pivot procedure (practical) 1. Select an entering variable: pick a nonbasic variable with positive reduced cost in the objective row (often the largest). 2. For each row where the entering variable has positive coefficient, compute ratio = RHS / coefficient. 3. Select leaving variable: the basic variable with the smallest nonnegative ratio (min‑ratio test). 4. Pivot: use the leaving row to solve for the entering variable, substitute and update all rows including the objective. 5. Repeat until no positive coefficients remain in the objective (for maximization).

How to form the dual (conceptual) 1. Associate a nonnegative dual variable with each primal constraint. 2. Dual objective: minimize the sum over constraints of RHS * dual variable. 3. For each primal variable, require the weighted sum of dual coefficients to be at least the primal variable’s objective coefficient (signs depend on inequality directions). 4. Solve the dual for a bound; by strong duality, equality certifies primal optimality.

How to model a 0/1 knapsack ILP 1. For each item i, define xi ∈ {0,1}. 2. Constraint: sum(wi * xi) ≤ capacity. 3. Objective: maximize sum(vi * xi). 4. Feed the model to an ILP solver (pulp, Gurobi, CPLEX, CBC).

Examples & practical tools shown

Farmer example: both geometric and Simplex solutions give x_p = 1000 kg, x_c = 4000 kg, profit = $8000.
Knapsack example: ILP solved with Python pulp, optimal value 84 by selecting items {2, 4, 5, 6}.
Python pulp is recommended for modeling and solving LPs and ILPs quickly.

Speakers, sources and references mentioned

Narrator / video author (unnamed).
George B. Dantzig — inventor of the Simplex method (anecdote noted).
Leonid Kantorovich and Tjalling Koopmans — Nobel Prize (1975) for LP applications in economics.
Tools: pulp (Python LP/ILP modeling package) and Python.
Concepts referenced: Simplex method, slack variables, duality (weak and strong), integer linear programming, knapsack problem, branch‑and‑bound and solver optimizations.