ClpSimplex

Simplex Method for Linear Programming: Maintains a basic feasible solution (BFS) at a vertex of the polytope. Each iteration moves along an edge to an adjacent vertex with better objective.

• Primal simplex: maintains primal feasibility, achieves dual feasibility
• Dual simplex: maintains dual feasibility, achieves primal feasibility Terminates when both primal and dual feasibility achieved (optimality).

Complexity: $O(2^n)$ worst-case (Klee-Minty), but typically polynomial in practice. Per-iteration cost: $O(m²)$ for basis update + $O(mn)$ for pricing. Iteration count: typically $O(m)$ to $O(3m)$ for practical problems.