Lecture notes for CMUâ€™s course on Linear Programming & Semidefinite Programming
By: Anupam Gupta & Ryan O’Donnel
Introduction to Linear Programming
Linear programs began to get a lot of attention in 1940's, when people were interested in minimizing costs of various systems while meeting different constraints. We care about them today because we can solve them efficiently and a very general class of problems can be expressed as LPs. A linear program has variables, linear constraints on those variables, and a linear objective function which we aim to maximize or minimize.