Chapter Summaries
Chapter 1: Problem Solving with Mathematical Models
An introduction to the operations research approach of dealing with large-scale, operations problems through mathematical modeling. Basic terminology and
modeling a simple problem in several ways to illustrate the tradeoff between tractability and validity.
(21 pages)
Chapter 2: Deterministic Optimization Models in Operations Research
Formulation of all types of mathematical programs. Steps in formulation,
graphic solution, and indexing to represent large models. Definitions and distinctions between
linear versus nonlinear, discrete versus continuous, single versus multiobjective, including recognizing different types and appreciating their relative tractability.
(53 pages)
Chapter 3: Improving Search
A low level introduction to the central ideas of improving search (hillclimbing). Local vs. global optima, the direction-step paradigm, gradients, improving directions, active constraints, feasible directions, step size choices, unimodal and convex cases guaranteeing global optima, two-phase and big-M methods for finding initial feasible solutions.
(54 pages)
Chapter 4: Linear Programming Models
A survey of classic linear programming model forms using examples drawn from operations research practice and emphasizing formulation of typical structures. Allocation models, blending models, operations planning models, shift-scheduling models, time-phased models, and linearized nonlinear models.
(44 pages)
Chapter 5: Simplex Search for Linear Programming
The simplex algorithm for linear programming as an implementation of improving search. LP standard form, basic solutions and extreme-points, simplex directions formed by increasing single nonbasics, degeneracy, revised simplex, lower- and upper-bounded simplex.
(75 pages)
Chapter 6: Interior Point Methods for Linear Programming
An introduction to improving search algorithms for linear programming
that move through the interior of the feasible space. Conveniences of being
in the interior, projection to achieve feasibility, affine scaling search, log barrier methods, and a brief sketch of primal-dual approaches.
(47 pages)
Chapter 7: Duality and Sensitivity in Linear Programming
Sensitivity analysis in linear programming, and duality as a tool for quantifying it. Variables as activities and constraints as supplies or demands for a resource. Qualitative sensitivity to changes in constraints or objectives, quantitative sensitivity leading to derivation of the dual,
forming duals in various cases,
relations between primal and dual, analyzing computer sensitivity outputs and ranges, parametric programming.
(73 pages)
Chapter 8: Multiobjective Optimization and Goal Programming
Formulation of multiobjective LP, NLP and IP models
including finance,
engineering design, and the public sector. Efficient points and
the efficient frontier, preemptive optimization, and weighted sums of objectives. Goal programming both as a method for dealing with soft
constraints and as a technique for reducing multiobjective models to
single criterion minimization.
(36 pages)
Chapter 9: Shortest Paths and Discrete Dynamic Programming
Shortest path models and algorithms, and their extension to discrete dynamic programming. Forms of shortest path models, the dynamic programming solution approach, Bellman-Ford algorithm for one node to all others, Floyd-Warshall algorithm for all nodes to all others, Dijkstra algorithm for nonnegative costs, acyclic cases and CPM project scheduling, Wagner-Whitin lot sizing, and other discrete dynamic programs.
(66 pages)
Chapter 10: Network Flows
Network flow models and algorithms for their solution. Graphs, networks and flow balance;
flow changes arond cycle directions; integrality of optimal flows;
transportation, assignment, maximum flow and time-expanded
examples drawn from operations research practice; network simplex and cycle canceling algorithms; multicommodity and gain/loss flows.
(79 pages)
Chapter 11: Discrete Optimization Models
A survey of classic integer and combinatorial optimization model forms using examples drawn from operations research practice and emphasizing formulation of typical structures. Lumpy LP's and fixed charges; knapsack and capital budgeting; set packing, covering and partition; linear, quadratic, and generalized assignment; matching; traveling salesman problems and routing; facility location and network design; processor scheduling and job shops.
(71 pages)
Chapter 12: Discrete Optimization Methods
Methods for exact or approximate solution of integer and combinatorial optimization models. Enumeration; relaxations and their uses
including ways to strengthen them; branch and bound and refinements including branch and cut; elementary improving search heuristics; extensions to tabu, simulated annealing and
genetic algorithm search; and constructive heuristics.
(88 pages)
Chapter 13: Unconstrained Nonlinear Programming
Unconstrained nonlinear programs and algorithms for their solution. Formulation of single variable, curve fitting and maximum likelihood models. One-dimensional search, derivatives, Taylor series and conditions local optima, convex/concave functions, gradient search, Newton's method, quasi-Newton methods, and Nelder-Mead optimization without derivatives.
(72 pages)
Chapter 14: Constrained Nonlinear Programming
Constrained nonlinear programs and algorithms for their solution. Formulation of large-scale and engineering design cases using examples drawn from operations research practice. Definition and tractability of convex, separable, quadratic and posynomial geometric programs. Lagrange multiplier methods, KKT optimality conditions, penalty and barrier methods, reduced gradient algorithms, quadratic programming methods, separable programming, and geometric programming.
(99 pages)
Selected Answers
Answers to approximately half the numerical and smaller formulation
exercises at ends of chapters.
(18 pages)
Index
Topic index to all material of the book.
(15 pages)
Back to Optimization in Operations Research mainpage