## Linear Programming

##### Abstract

This book is about constrained optimization. It begins with a thorough treatment
of linear programming and proceeds to convex analysis, network flows, integer
programming, quadratic programming, and convex optimization. Along the way,
dynamic programming and the linear complementarity problem are touched on as
well.
The book aims to be a first introduction to the subject. Specific examples and
concrete algorithms precede more abstract topics. Nevertheless, topics covered are
developed in some depth, a large number of numerical examples are worked out
in detail, and many recent topics are included, most notably interior-point methods.
The exercises at the end of each chapter both illustrate the theory and, in some cases,
extend it.
Prerequisites. The book is divided into four parts. The first two parts assume
a background only in linear algebra. For the last two parts, some knowledge of
multivariate calculus is necessary. In particular, the student should know how to use
Lagrange multipliers to solve simple calculus problems in 2 and 3 dimensions.
Associated software. It is good to be able to solve small problems by hand,
but the problems one encounters in practice are large, requiring a computer for their
solution. Therefore, to fully appreciate the subject, one needs to solve large (practical)
problems on a computer. An important feature of this book is that it comes
with software implementing the major algorithms described herein. At the time of
writing, software for the following five algorithms is available:
• The two-phase simplex method as shown in Figure 6.1.
• The self-dual simplex method as shown in Figure 7.1.
• The path-following method as shown in Figure 18.1.
• The homogeneous self-dual method as shown in Figure 22.1.
• The long-step homogeneous self-dual method as described in Exercise
22.4.
The programs that implement these algorithms are written in C and can be
easily compiled on most hardware platforms. Students/instructors are encouraged
to install and compile these programs on their local hardware. Great pains have
been taken to make the source code for these programs readable (see Appendix A).
In particular, the names of the variables in the programs are consistent with the
notation of this book.