Geometry and numerical algorithms · 45 / 53
Linear programming, Simplex and duality
Understand → trace → implement → justify
2 min reading · allow extra time for practiceLinear programming optimises a linear objective under linear equalities and inequalities. Its feasible region is a polyhedron. A problem may be infeasible, unbounded or have a finite optimum. Integer programming differs: rounding a continuous LP optimum need not give a feasible integer solution.
Simplex pivots between vertices and is powerful in practice, but has no general polynomial worst-case bound. Ellipsoid and interior-point methods provide polynomial theory in suitable models. Degeneracy, cycling, tolerances and ill-conditioned constraints are real implementation concerns; rules such as Bland’s prevent cycling.
Duality models resource values. Weak duality supplies bounds; strong duality equates finite primal and dual optima under the relevant conditions. Complementary slackness helps certify optimality. Special flow and matching formulations link LP to integrality. Check feasibility and certificates, not just the reported objective.
A worked trace
For max 3x+2y with x+y≤4, x≤2 and nonnegative variables, vertices yield optimum (2,2), value 10.
Cost and assumptions
The vertex enumeration below models only this tiny example; it is not a general LP solver. Simplex can take exponential worst-case time.
Executable example
Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.
vertices=[(0,0),(2,0),(2,2),(0,4)]
best=max(vertices,key=lambda p:3*p[0]+2*p[1])
assert best==(2,2)TEST YOUR UNDERSTANDING
Your turn
What if x+y≤−1 while x,y≥0?
Reveal the reasoning
No feasible point exists. This is infeasible, not unbounded; unboundedness requires feasible unlimited improvement.
Take it further
- Write down the input contract and the invariant before changing the example.
- Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
- Derive the cost under the stated model; measure several input sizes and explain discrepancies.
Primary reading & lecture notes
Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.
MIT 6.046J · Design and Analysis ↗Jeff Erickson · Algorithms ↗