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
References
Index