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