Linear and combinatorial optimization : a basic course

This book is intended for a first course in linear and combinatorial optimization at the university level for students who are highly familiar with linear algebra and multivariable calculus. A general theory is presented for continuous optimization problems with convex objective functions and affine constraints. The simplex, dual simplex and interior-point methods are presented for linear problems with continuous variables. For discrete problems, the general cutting-plane and branch-and-bound methods are introduced. Tailored combinatorial methods are motivated for the transportation, assignment, travelling-salesperson, maximal-flow and cheapest-path problems. The book includes numerous solved examples as well as exercises for which either answers or complete solutions are provided.

The companion book Nonlinear Optimization – A Basic Course can be read independently.