# Deterministic Operations Research: Models and Methods in Linear Optimization

Publisher:
John Wiley
Publication Date:
2010
Number of Pages:
613
Format:
Hardcover
Price:
121.00
ISBN:
9780470484517
Category:
Textbook
BLL Rating:

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
John McCleary
, on
01/23/2015
]

Operations Research (OR) is a wonderful example of mathematics applied to real problems. I became acquainted with OR in graduate school and I have been a fan of it since. It offers methods derived from rich mathematics, and it tackles problems of all sorts with ingenuity and frequent success. The book under review makes OR accessible to undergraduate math majors. What better lesson in applied mathematics could an undergraduate learn?

The focus of the book is deterministic OR, which includes linear and integer programming as well as combinatorial methods. This leaves out probabilistic aspects of OR such as game theory, queueing theory, and various probabilistic versions of certain models. The author uses the focus to introduce and discuss algorithm design, with the simplex method as a case study.

The development through the chapters makes a particularly nice story. OR is introduced as the study of “mathematical models of complex science, engineering, industrial,and management problems and how to analyze them using mathematical techniques.” The book emphasizes

• how to construct a model of a real-world problem, in particular as a linear optimization problem;
• how to solve such linear optimization problems; and
• analysis of the results and methods.

Constructing the model occupies chapters 2 to 4. Typically, the author presents a particular case of a problem, then abstracts the salient features of the example. For example, the Terre Haute Door Company provides an example of a resource allocation problem. Solutions to the problems posed can be obtained through a black box solver, and the emphasis is on the modeling process. In these chapters the classic problems are posed and discussed: scheduling, blending, inventory, network flow, vehicle routing, and facility location. Combinatorial problems and integer models are also discussed.

The author next turns to algorithm design. The distinction is made between exact and heuristic algorithms; the Traveling Salesman Problem makes the distinction clear. The ingenuity needed to pose an optimization problem is certainly attractive, but finding a successful algorithm to solve the problem may require even more ideas. The main example is developed next: the simplex method with its beautiful geometry and manageable algebra. The convergence and possible degeneracy are discussed with some of the computational issues. The next few chapters treat the more subtle notion of duality and its consequences. The transportation model is featured as a novel application of these ideas.

The final chapters of the book treat discrete problems, including network flow and knapsack problems. Discussion of exact and heuristic methods includes ideas such as relaxation, branch-and-bound, simulated annealing, and genetic algorithms. Various algorithms are introduced.

Exercises abound and the author has provided additional material on his website. Although the opportunity to teach OR may not come often, having such a well presented and rich text on which to base such an undergraduate course ought to generate more interest. I recommend the book for every serious undergraduate library.

John McCleary (mccleary@vassar.edu) is Professor of Mathematics at Vassar College.

Preface.

1. Introduction to Operations Research.

1.1 What is Deterministic Operations Research?

1.2 Introduction to Optimization Modeling.

1.3 Common Classes of Mathematical Programs.

Exercises.

2. Linear Programming Modeling.

2.1 Resource Allocation Models.

2.2 Work Scheduling Models.

2.3 Models and Data.

2.4 Blending Models.

2.5 Production Process Models.

2.6 Multiperiod Models: Work Scheduling and Inventory.

2.7 Linearization of Special Nonlinear Models.

2.8 Various Forms of Linear Programs.

2.9 Network Models.

Exercises.

3. Integer and Combinatorial Models.

3.1 Fixed-Charge Models.

3.2 Set Covering Models.

3.3 Models Using Logical Constraints.

3.4 Combinatorial Models.

3.5 Sports Scheduling and an Introduction to IP Solution Technques.

Exercises.

4. Real-World Operations Research Applications:  An Introduction.

4.1 Vehicle Routing Problems.

4.2 Facility Location and Network Design Models.

4.3 Applications in the Airline Industry.

Exercises.

5. Introduction to Algorithm.

5.1 Exact and Heuristic Algorithms.

5.2 What to Ask When Designing Algorithms?

5.3 Constructive versus Local Search Algorithms.

5.4 How Good is our Heuristic Solution?

5.5 Example of a Local Search Method.

5.7 Other Heuristic Methods.

5.8 Designing Exact Methods: Optimality Conditions.

Exercises.

6. Improving Search Algorithms and Comvexity.

6.1 Improving Search and Optimal Solutions.

6.2 Finding Better Solutions.

6.3 Convexity: When Does Improving Search Imply Global Optimality?

6.4 Farkas’ Lemma: When Can No Improving Feasible Direction be Found?

Exercises.

7. Geometry and Algebra of Linear Programs.

7.1 Geometry and Algebra of “Corner Points”.

7.2 Fundamental Theorem of Linear Programming.

7.3 Linear Programs in Canonical Form.

Exercises.

8. Solving Linear Programs: Simplex Method.

8.1 Simplex Method.

8.2 Making the Simplex Method More Efficient.

8.3 Convergence, Degeneracy, and the Simplex Method.

8.4 Finding an Initial Solution: Two-Phase Method.

8.5 Bounded Simplex Method.

8.6 Computational Issues.

Exercises.

9. Linear Programming Duality.

9.1 Motivation: Generation Bounds.

9.2 Dual Linear Program.

9.3 Duality Theorems.

9.4 Another Interpretation of the Simplex Method.

9.5 Farkas’ Lemma Revisited.

9.6 Economic Interpretation of the Dual.

9.7 Another Duality Approach: Lagrangian Duality.

Exercises.

10. Sensitivity Analysis of Linear Programs.

10.1 Graphical Sensitivity Analysis.

10.2 Sensitivity Analysis Calculations.

10.3 Use of Sensitivity Analysis.

10.4 Parametric Programming.

Exercises.

11. Algorithmic Applications of Duality.

11.1 Dual Simplex Method.

11.2 Transportation Problem.

11.3 Column Generation.

11.4 Dantzig-Wolfe Decomposition.

11.5 Primal-Dual Interior Point Method.

Exercises.

12. Network Optimization Algorithms.

12.1 Introduction to Network Optimization.

12.2 Shortest Path Problems.

12.3 Maximum Flow Problems.

12.4 Minimum Cost Network Flow Problems.

Exercises.

13. Introduction to Integer Programming.

13.1 Basic Definitions and Formulations.

13.2 Relaxations and Bounds.

13.3 Preprocessing and Probing.

13.4 When are Integer Programs “Easy?’

Exercises.

14. Solving Integer Programs: Exact Methods.

14.1 Complete Enumeration.

14.2 Branch-and Bound Methods.

14.3 Valid Inequalities and Cutting Planes.

14.4 Gomory’s Cutting Plane Algorithm.

14.5 Valid Inequalities for 0-1 Knapsack Constraints.

14.6 Branch-and-Cut Algorithms.

14.7 Computational Issues.

Exercises.

15. Solving Integer Programs: Modern Heuristic Techniques.

15.1 Review of Local Search Methods: Pros and Cons.

15.2 Simulated Annealing.

15.3 Tabu Search.

15.4 Genetic Algorithms.

15.5 GRASP Algorithms.

Exercises.

Appendix A: Background Review.

A.1 Basic Notation.

A.2 Graph Theory.

A.3 Linear Algebra.

Reference.

Index.