Bertsimass, Dimitri : Massachusetts Institute of Technology
Tsitsiklis, John N. : Massachusetts Institute of Technology
John N. Tsitsiklis is a professor in the Department of Electrical Engineering and Computer Science at MIT, and
is affiliated with the Laboratory for Information and Decision Systems (LIDS) and the Operations Research Center.
Summary
This book provides a unified, insightful, and modern treatment of linear optimization, that is, linear programming,
network flow problems, and discrete optimization. It includes classical topics as well as the state of the art,
in both theory and practice.
Among its special features, the book:
develops the major algorithms and duality theory through a geometric perspective
provides a thorough treatment of the geometry, convergence, and complexity of interior point methods
covers the main methods for network flow problems
contains a detailed treatment of integer programming formulations and algorithms
discusses the art of formulating and solving large scale problems through practical case studies
includes a large number of examples and exercises. Has been developed through extensive classroom use in graduate
courses
Table of Contents
Introduction
Variants of the linear programming problem
Examples of linear programming problems
Piecewise linear convex objective functions
Graphical representation and solution
Linear algebra background and notation
Algorithms and operation counts
Exercises
History, notes, notes and sources
The geometry of linear programming
Polyhedra and convex sets
Extreme points, vertices, and basic feasible solutions
Polyhedra in standard form
Degeneracy
Existence of extreme points
Optimality of extreme points
Representation of bounded polyhedra
Projections of polyhedra: Fourier-Motzkin elimination
Summary
Exercises
Notes and sources
The simplex method
Optimality conditions
Development of the simplex method
Implementations of the simplex method
Anticycling: lexicography and Bland's rule
Finding an initial basic feasible solution
Column geometry and the simplex method
Computational efficiency of the simplex method
Summary
Exercises
Notes and sources
Duality theory
Motivation
The dual problem
The duality theorem
Optimal dual variables as marginal costs
Standard form problems and the dual simplex method
Farkas' lemma and linear inequalities
From separating hyperplanes to duality
Cones and extreme rays
Representation of polyhedra
General linear programming duality
Summary
Exercises
Notes and sources
Sensitivity analysis
Local sensitivity analysis
Global dependence on the right-hand side vector
The set of all dual optimal solutions
Global dependence on the cost vector
Parametric programming
Summary
Exercises
Notes and sources
Large scale optimization
Delayed column generation
The cutting stock problem
Cutting plane methods
Dantzig-Wolfe decomposition
Stochastic programming and Benders decomposition
Summary
Exercises
Notes and sources
Network flow problems
Graphs
Formulation of the network flow problem
The network simplex algorithm
The negative cost cycle algorithm
The maximum flow problem
Duality in network flow problems
Dual ascent methods
The assignment problem and the auction algorithm
The shortest path problem
The minimum spanning tree problem
Summary
Exercises
Notes and sources
Complexity of linear programming and the ellipsoid method
Efficient algorithms and computational complexity
The key geometric result behind the ellipsoid method
The ellipsoid method for the feasibility problem
The ellipsoid method for optimization
Problems with exponentially many constraints
Summary
Exercises
Notes and sources
Interior point methods
The affine scaling algorithm
Convergence of affine scaling
The potential reduction algorithm
The primal path following algorithm
The primal-dual path following algorithm
An overview
Exercises
Notes and sources
Integer programming formulations
Modeling techniques
Guidelines for strong formulations
Modeling with exponentially many constraints
Summary
Exercises
Notes and sources
Integer programming methods
Cutting plane methods
Branch and bound
Dynamic programming
Integer programming duality
Approximation algorithms
Local search
Simulated annealing
Summary
Exercises
Notes and sources
The art in linear optimization
Modeling languages for linear optimization
Optimization libraries and general observations
The fleet assignment problem
The air traffic flow management problem
The job shop scheduling problem
Summary
Exercises
Notes and sources
