Chapter Summaries

for Optimization in Operations Research
by Ronald L. Rardin, Prentice Hall, 1998

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