Chapter 16. Linear Programming

Formulating and solving optimization problems with linear constraints.

Overview

This chapter introduces linear programming (LP) — the optimization of a linear objective function subject to linear inequality constraints. Topics include the simplex method, LP duality, and applications to combinatorial optimization. The chapter focuses on the theory and formulations rather than algorithmic implementations in the LLP framework; consequently, no companion programs are provided for this chapter.