Deterministic Operations Research: Models and Methods in Linear Optimization

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 the Book.

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.