The simplex method has exponential worst-case complexity (Klee-Minty examples), yet it is the dominant algorithm in practice. Why does worst-case analysis fail to predict practical performance?
AKlee-Minty examples never arise in real problems
BSmoothed analysis (Spielman-Teng) shows that the simplex method runs in polynomial expected time when the input is subject to tiny random perturbations — real-world instances are never exactly worst-case, and the algorithm's practical efficiency reflects its polynomial smoothed complexity rather than exponential worst-case
CModern implementations use a completely different algorithm that just looks like simplex
DHardware improvements have made exponential algorithms practical
Spielman and Teng's smoothed analysis bridges the gap between worst-case (exponential) and practical observation (fast). They showed that for any LP instance, adding Gaussian noise with standard deviation sigma to the constraint coefficients yields expected simplex running time polynomial in n and 1/sigma. Since real-world instances have inherent measurement noise or roundoff, they are always 'slightly perturbed,' explaining why simplex empirically runs in polynomial time. This result won the Gödel Prize and Fulkerson Prize, and established smoothed analysis as a new framework for algorithm analysis.
Question 2 Short Answer
Interior point methods for LP achieve polynomial worst-case complexity by traversing the INTERIOR of the feasible region rather than its boundary. What prevents them from replacing simplex entirely in practice?
Think about your answer, then reveal below.
Model answer: Interior point methods find a near-optimal solution in the interior of the polytope, which must then be 'rounded' to a vertex (the optimal LP solution is always at a vertex for bounded LPs). Each iteration of interior point methods involves solving a large linear system (cost O(n^3) or O(n^(2.37)) with fast matrix multiplication), making individual iterations expensive. The simplex method's per-iteration cost is much lower (O(n) for a pivot). Interior point methods also lack warm-starting: changing a constraint or objective slightly requires restarting from scratch, while simplex can resume from the previous optimal vertex. In practice, simplex dominates for small-to-medium LPs and for problems requiring sensitivity analysis, while interior point methods win for very large, sparse LPs where the linear systems can be solved efficiently.
The complementary strengths have led to hybrid solvers: use interior point for the initial solve of a large LP, then switch to simplex for sensitivity analysis and re-optimization. Commercial solvers like Gurobi and CPLEX implement both and choose automatically.
Question 3 True / False
Every linear program has an optimal solution at a vertex (extreme point) of the feasible polytope, provided the LP is bounded and feasible.
TTrue
FFalse
Answer: True
This is the fundamental theorem of linear programming. The feasible region of an LP is a convex polytope. A linear objective achieves its maximum (or minimum) over a convex set at an extreme point — because if the optimum were in the interior, moving along the objective gradient would improve it, contradicting optimality. The simplex method exploits this by only examining vertices, hopping between adjacent vertices along improving edges. Interior point methods, by contrast, approach the optimal vertex from the interior using a sequence of barrier-modified objectives that steer the trajectory toward the optimum.
Question 4 True / False
LP duality guarantees that for every feasible LP, the optimal primal and dual values are equal (strong duality). This fails for nonlinear convex programs.
TTrue
FFalse
Answer: False
Strong duality — that the optimal primal and dual values are equal when both are finite — holds for LP and more generally for convex programs under mild constraint qualification conditions (like Slater's condition: the existence of a strictly feasible point). Strong duality is NOT limited to LP. What IS special about LP is that strong duality holds without any constraint qualification — it follows purely from the polyhedral geometry of LP feasible regions. For general convex programs, you need Slater's condition or a similar regularity condition to guarantee that the duality gap closes.