Linear programming is arguably the single most essential technique in theory and practice of mathematical optimisation. We will introduce the underlying duality theory including complementary slackness and the central path.
As an example for the powerful algorithms available to solve linear programs, we will sketch a primal-dual interior point method. This algorithm solves a linear program by following the central path to an optimal solution.