Table of Contents

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

1.4   About this Book
Exercises


2. Linear Programming Modeling

2.1  Resourse 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 Flows

Exercises

 

3. Integer Programming 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 Techniques

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 Design

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  Examples of Constructive Methods

5.6  Example of a Local Search Method

5.7  Other Heuristic Methods

5.8  Designing Exact Methods: Optimality Conditions

Exercises

 

6. Improving Search Algorithms and Convexity

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: Generating 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  Ecomonic 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"?

 

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

 

References

Index