Simplex has its own page

Shortest Path

Cutting Plane

Finding a Cutting Plane

1. Find a constraint with fractional RHS and floor everything.
2. Verify that, given a solution to the LP $a$
   1. $a$ does not satisfy the new LP
   2. Every solution of the IP satisfies the new LP