Linear programs are solved using the Simplex Method as described in the book Combinatorial Optimization by Christos H. Papadimitriou and Kenneth Steiglitz.