Low-Dimensional Linear Programming

Presentation by: Marc Lebovitz

Classical LP: Simplex Algorithm

Pick vertex in feasible region.

Vertex is constrained by H2 and H4.
Relax one constraint of vertex (H4 here).
We are left with d-1 constraints active.

Move along H2 in the direction which maximizes the inner product with the
objective function.

Stop when hit another constraint.

Repeat steps 2-4: Relax a constraint and move along direction which
increases the inner product with the objective function.

Halt when movement no longer increases the inner product with the
objective function.

Conclusion:

The Simplex algorithm moves from vertex to vertex along the boundary of the
feasible region. It stops when it reaches the extreme vertex with respect to the
objective function.