| |
| |
| Preface | |
| |
| |
| |
| Introduction to Operations Research | |
| |
| |
| |
| What is Deterministic Operations Research? | |
| |
| |
| |
| Introduction to Optimization Modeling | |
| |
| |
| |
| Common Classes of Mathematical Programs | |
| |
| |
| |
| About this Book | |
| |
| |
| Exercises | |
| |
| |
| |
| Linear Programming Modeling | |
| |
| |
| |
| Resource Allocation Models | |
| |
| |
| |
| Work Scheduling Models | |
| |
| |
| |
| Models and Data | |
| |
| |
| |
| Blending Models | |
| |
| |
| |
| Production Process Models | |
| |
| |
| |
| Multiperiod Models: Work Scheduling and Inventory | |
| |
| |
| |
| Linearization of Special Nonlinear Models | |
| |
| |
| |
| Various Forms of Linear Programs | |
| |
| |
| |
| Network Models | |
| |
| |
| Exercises | |
| |
| |
| |
| Integer and Combinatorial Models | |
| |
| |
| |
| Fixed-Charge Models | |
| |
| |
| |
| Set Covering Models | |
| |
| |
| |
| Models Using Logical Constraints | |
| |
| |
| |
| Combinatorial Models | |
| |
| |
| |
| Sports Scheduling and an Introduction to IP Solution Techniques | |
| |
| |
| Exercises | |
| |
| |
| |
| Real-World Operations Research Applications: An Introduction | |
| |
| |
| |
| Vehicle Routing Problems | |
| |
| |
| |
| Facility Location and Network Design Models | |
| |
| |
| |
| Applications in the Airline Industry | |
| |
| |
| Exercises | |
| |
| |
| |
| Introduction to Algorithm Design | |
| |
| |
| |
| Exact and Heuristic Algorithms | |
| |
| |
| |
| What to Ask When Designing Algorithms? | |
| |
| |
| |
| Constructive versus Local Search Algorithms | |
| |
| |
| |
| How Good is our Heuristic Solution? | |
| |
| |
| |
| Examples of Constructive Methods | |
| |
| |
| |
| Example of a Local Search Method | |
| |
| |
| |
| Other Heuristic Methods | |
| |
| |
| |
| Designing Exact Methods: Optimality Conditions | |
| |
| |
| Exercises | |
| |
| |
| |
| Improving Search Algorithms and Convexity | |
| |
| |
| |
| Improving Search and Optimal Solutions | |
| |
| |
| |
| Finding Better Solutions | |
| |
| |
| |
| Convexity: When Does Improving Search Imply Global Optimality? | |
| |
| |
| |
| Farkas' Lemma: When Can No Improving Feasible Direction be Found? | |
| |
| |
| Exercises | |
| |
| |
| |
| Geometry and Algebra of Linear Programs | |
| |
| |
| |
| Geometry and Algebra of "Corner Points" | |
| |
| |
| |
| Fundamental Theorem of Linear Programming | |
| |
| |
| |
| Linear Programs in Canonical Form | |
| |
| |
| Exercises | |
| |
| |
| |
| Solving Linear Programs: Simplex Method | |
| |
| |
| |
| Simplex Method | |
| |
| |
| |
| Making the Simplex Method More Efficient | |
| |
| |
| |
| Convergence, Degeneracy, and the Simplex Method | |
| |
| |
| |
| Finding an Initial Solution: Two-Phase Method | |
| |
| |
| |
| Bounded Simplex Method ?. | |
| |
| |
| |
| Computational Issues | |
| |
| |
| Exercises | |
| |
| |
| |
| Linear Programming Duality | |
| |
| |
| |
| Motivation: Generating Bounds | |
| |
| |
| |
| Dual Linear Program | |
| |
| |
| |
| Duality Theorems | |
| |
| |
| |
| Another Interpretation of the Simplex Method | |
| |
| |
| |
| Farkas' Lemma Revisited | |
| |
| |
| |
| Economic Interpretation of the Dual | |
| |
| |
| |
| Another Duality Approach: Lagrangian Duality | |
| |
| |
| Exercises | |
| |
| |
| |
| Sensitivity Analysis of Linear Programs | |
| |
| |
| |
| Graphical Sensitivity Analysis | |
| |
| |
| |
| Sensitivity Analysis Calculations | |
| |
| |
| |
| Use of Sensitivity Analysis | |
| |
| |
| |
| Parametric Programming | |
| |
| |
| Exercises | |
| |
| |
| |
| Algorithmic Applications of Duality | |
| |
| |
| |
| Dual Simplex Method | |
| |
| |
| |
| Transportation Problem | |
| |
| |
| |
| Column Generation | |
| |
| |
| |
| Dantzig-Wolfe Decomposition | |
| |
| |
| |
| Primal-Dual Interior Point Method | |
| |
| |
| Exercises | |
| |
| |
| |
| Network Optimization Algorithms | |
| |
| |
| |
| Introduction to Network Optimization | |
| |
| |
| |
| Shortest Path Problems | |
| |
| |
| |
| Maximum Flow Problems | |
| |
| |
| |
| Minimum Cost Network Flow Problems | |
| |
| |
| Exercises | |
| |
| |
| |
| Introduction to Integer Programming | |
| |
| |
| |
| Basic Definitions and Formulations | |
| |
| |
| |
| Relaxations and Bounds | |
| |
| |
| |
| Preprocessing and Probing | |
| |
| |
| |
| When are Integer Programs "Easy?" | |
| |
| |
| Exercises | |
| |
| |
| |
| Solving Integer Programs: Exact Methods | |
| |
| |
| |
| Complete Enumeration | |
| |
| |
| |
| Branch-and-Bound Methods | |
| |
| |
| |
| Valid Inequalities and Cutting Planes | |
| |
| |
| |
| Gomory's Cutting Plane Algorithm | |
| |
| |
| |
| Valid Inequalities for 0-1 Knapsack Constraints | |
| |
| |
| |
| Branch-and-Cut Algorithms | |
| |
| |
| |
| Computational Issues | |
| |
| |
| Exercises | |
| |
| |
| |
| Solving Integer Programs: Modern Heuristic Techniques | |
| |
| |
| |
| Review of Local Search Methods: Pros and Cons | |
| |
| |
| |
| Simulated Annealing | |
| |
| |
| |
| Tabu Search | |
| |
| |
| |
| Genetic Algorithms | |
| |
| |
| |
| GRASP Algorithms | |
| |
| |
| Exercises | |
| |
| |
| |
| Background Review | |
| |
| |
| |
| Basic Notation | |
| |
| |
| |
| Graph Theory | |
| |
| |
| |
| Linear Algebra | |
| |
| |
| Reference | |
| |
| |
| Index | |