Textbook
Deterministic Operations Research: Models and Methods in Linear OptimizationSeptember 2010, ©2010

Optimization modeling and algorithms are key components to problemsolving across various fields of research, from operations research and mathematics to computer science and engineering. Addressing the importance of the algorithm design process. Deterministic Operations Research focuses on the design of solution methods for both continuous and discrete linear optimization problems. The result is a clearcut resource for understanding three cornerstones of deterministic operations research: modeling realworld problems as linear optimization problem; designing the necessary algorithms to solve these problems; and using mathematical theory to justify algorithmic development.
Treating realworld examples as mathematical problems, the author begins with an introduction to operations research and optimization modeling that includes applications form sports scheduling an the airline industry. Subsequent chapters discuss algorithm design for continuous linear optimization problems, covering topics such as convexity. Farkas’ Lemma, and the study of polyhedral before culminating in a discussion of the Simplex Method. The book also addresses linear programming duality theory and its use in algorithm design as well as the Dual Simplex Method. DantzigWolfe decomposition, and a primaldual interior point algorithm. The final chapters present network optimization and integer programming problems, highlighting various specialized topics including labelcorrecting algorithms for the shortest path problem, preprocessing and probing in integer programming, lifting of valid inequalities, and branch and cut algorithms.
Concepts and approaches are introduced by outlining examples that demonstrate and motivate theoretical concepts. The accessible presentation of advanced ideas makes core aspects easy to understand and encourages readers to understand how to think about the problem, not just what to think. Relevant historical summaries can be found throughout the book, and each chapter is designed as the continuation of the “story” of how to both model and solve optimization problems by using the specific problemslinear and integer programsas guides. The book’s various examples are accompanied by the appropriate models and calculations, and a related Web site features these models along with Maple™ and MATLAB content for the discussed calculations.
Thoroughly classtested to ensure a straightforward, handson approach, Deterministic Operations Research is an excellent book for operations research of linear optimization courses at the upperundergraduate and graduate levels. It also serves as an insightful reference for individuals working in the fields of mathematics, engineering, computer science, and operations research who use and design algorithms to solve problem in their everyday work.
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 FixedCharge 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. RealWorld 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: TwoPhase 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 DantzigWolfe Decomposition.
11.5 PrimalDual 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 Branchand Bound Methods.
14.3 Valid Inequalities and Cutting Planes.
14.4 Gomory’s Cutting Plane Algorithm.
14.5 Valid Inequalities for 01 Knapsack Constraints.
14.6 BranchandCut 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.
“Dr. Phillips has used other texts, but he is especially enthused with this book, influenced by student feedback. He says, “Algorithmic ideas are introduced at a pace that emphasizes and encourages intuitive understanding.” (Informs Journal on Computing, 1 June 2012)
"The book is aimed at serving upperundergraduate and graduate students of all fields as a comprehensive textbook or as a reference for studies on the subject." (Zentralblatt MATH, 2011)
"The result is a clearcut resource for understanding three cornerstones of deterministic operations research: modeling realworld problems as linear optimization problems; designing the necessary algorithms to solve these problems; and using mathematical theory to justify algorithmic development." (InfoTECH Spotlight  TMCnet, 8 February 2011)
 Wiley ETexts are powered by VitalSource technologies ebook software.
 With Wiley ETexts you can access your ebook how and where you want to study: Online, Download and Mobile.
 Wiley etexts are nonreturnable and nonrefundable.
 WileyPLUS registration codes are NOT included with the Wiley EText. For informationon WileyPLUS, click here .
 To learn more about Wiley etexts, please refer to our FAQ.
 Ebooks are offered as ePubs or PDFs. To download and read them, users must install Adobe Digital Editions (ADE) on their PC.
 Ebooks have DRM protection on them, which means only the person who purchases and downloads the ebook can access it.
 Ebooks are nonreturnable and nonrefundable.
 To learn more about our ebooks, please refer to our FAQ.