How do you actually find the best corner?
Start with what a feasible region is (topic 01) and why the best point of a linear problem sits at one of its corners (02). Topic 16 is the algorithm that walks from corner to corner to find it, topic 03 shows that every such problem has a mirror problem whose answer is the price of each limit, and topic 17 lets the objective curve, ending at Goemans–Williamson's semidefinite relaxation of Max-Cut, the classical result that QAOA on the quantum side has to beat. Turn six of these shapes over in 3D →
Topic 02 proved something remarkable and then left a practical question hanging: the best plan is always at a corner, so you never have to search the infinite interior. But a feasible region can still have an enormous number of corners. Which ones do you actually visit?
Dantzig's answer: developed in 1947 while he was at the Pentagon and later at RAND, and written up in full in Linear Programming and Extensions (Princeton University Press, 1963): is the simplex method, and it is almost insultingly simple once stated plainly: start at any vertex. Look at every neighbouring vertex. One along each edge. If any neighbour scores better, move to the best-looking one. If none does, stop. You are provably at the optimum, because topic 02's own convexity argument already ruled out anything better hiding elsewhere. That is the whole algorithm. Everything else: representing a vertex as a "basic feasible solution", choosing which improving neighbour to try, avoiding a degenerate vertex that loops back on itself: is bookkeeping around that one idea.
The figure above walks a real instance three pivots deep: origin → (4,0) → (4,2) → (2.5,5), stopping the moment the next neighbour, (0,5), would score worse. Three moves against five vertices is not much of a saving on a toy example. The saving is that, in practice, the number of pivots needed grows nowhere near as fast as the number of vertices does, which is exactly the complexity story the mathematics below has to tell honestly, because it is not always true.
Maintain a basic feasible solution: a vertex, expressed as which variables (decision plus slack) are currently "basic". At each iteration, compute the reduced cost of every non-basic variable: how much the objective would improve per unit if that variable entered the basis. Dantzig's original rule enters the variable with the most attractive reduced cost; a ratio test then finds which basic variable must leave to keep the solution feasible, and pivoting swaps the two:
enter: the non-basic variable with the best reduced cost
leave: arg min over rows i with a_ij > 0 of b_i / a_ij (the ratio test)
stop: when no reduced cost is still improving. That is the certificate
Worst case: exponential, and provably so. Klee & Minty, "How Good is the Simplex Algorithm?", in Inequalities III (O. Shisha, ed.), Academic Press (1972), pp. 159–175, built a family of feasible regions (a mildly skewed n-dimensional cube) on which the standard largest-coefficient pivot rule visits every one of the 2ⁿ vertices before stopping. Re-running the classic n = 3 instance confirms it: starting from the origin, the rule takes exactly 7 pivots to reach all 8 vertices of the cube in turn, the objective climbing 0 → 20 → 30 → 50 → 75 → 95 → 105 → 125, never once revisiting a vertex or finding a shortcut.
And yet simplex is, empirically, one of the fastest algorithms known for typical linear programs: solving instances with millions of variables in seconds. That gap between the proven worst case and lived reality went unexplained for three decades, until Spielman & Teng, "Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time," Journal of the ACM 51(3) (2004), 385–463: perturb any input instance by a small amount of random noise, and simplex's expected running time is polynomial in the input size and the inverse of the perturbation size. Pathological instances like the Klee–Minty cube turn out to be fragile, not typical: nudge them slightly and the exponential behaviour disappears.
Note what this settles and what it doesn't. It does not contradict Klee–Minty. That cube is still there, and an adversary who knows your pivot rule can still build one on purpose. It explains why nobody runs into one by accident. Topic 02 already noted that linear programming as a decision problem is in P via Khachiyan's ellipsoid method and Karmarkar's interior-point method; smoothed analysis is the separate, later result explaining why the much older, and in practice much faster, simplex method was never really the outlier its worst case suggested.
Still inside the solver, decades after being "obsoleted" Interior-point methods (Karmarkar, 1984, and the barrier methods descended from it: topic 17 below builds on exactly that machinery) are usually the faster choice for solving one enormous linear program from a cold start. But branch and bound (topic 05) does not solve one LP. It solves thousands of closely related LPs, each just one added constraint away from the last, and needs an answer to each quickly. That is a warm-start problem, and it is where simplex, specifically its dual variant, still wins decisively: it can resume from a previous solution and restore feasibility in a handful of pivots, where a standard interior-point method has no equivalent warm start and effectively begins again. That is a structural reason rather than a single benchmark number, and it is honestly why commercial mixed-integer solvers still run (dual) simplex at every node of the search tree even when they reach for interior-point methods to solve the very first relaxation.
Check yourself
The Klee-Minty cube forces simplex to visit every vertex. Why is that not a practical problem?
Klee-Minty is still there, and an adversary who knows your pivot rule can build one. Smoothed analysis (Spielman and Teng) explains why nobody runs into one by accident.