دانلود کتاب Business Optimization Using Mathematical Programming: An Introduction with Case Studies and Solutions in Various Algebraic Modeling Languages ... Research & Management Science, 307)

فهرست مطالب :

Dedication (1st Edition) Foreword Preface to the 2nd Edition Preface Contents About the Author List of Figures 1 Optimization: Using Models, Validating Models, Solutions, Answers 1.1 Introduction: Some Words on Optimization 1.2 The Scope of this Book 1.3 The Significance and Benefits of Models 1.4 Mathematical Optimization 1.4.1 A Linear Optimization Example 1.4.2 A Typical Linear Programming Problem 1.5 Using Modeling Systems and Software 1.5.1 Modeling Systems 1.5.2 A Brief History of Modeling Systems 1.5.3 Modeling Specialists and Applications Experts 1.5.4 Implementing a Model 1.5.5 Obtaining a Solution 1.5.6 Interpreting the Output 1.6 Benefiting from and Extending the Simple Model 1.7 A Survey of Real-World Problems 1.8 Summary and Recommended Bibliography 1.9 Appendix 1.9.1 Notation, Symbols, and Abbreviations 1.9.2 A Brief History of Optimization 2 From the Problem to its Mathematical Formulation 2.1 How to Model and Formulate a Problem 2.2 Variables, Indices, Sets, and Domains 2.2.1 Indices, Sets, and Domains 2.2.2 Summation 2.3 Constraints 2.3.1 Types of Constraints 2.3.2 Example 2.4 Objectives 2.5 Building More Sophisticated Models 2.5.1 A Simple Production Planning Problem: The Background 2.5.2 Developing the Model 2.6 Mixed Integer Programming 2.6.1 Example: A Farmer Buying Calves and Pigs 2.6.2 A Formal Definition of Mixed Integer Optimization 2.6.3 Difficult Optimization Problems 2.7 Interfaces: Spreadsheets and Databases 2.7.1 Example: A Blending Problem 2.7.2 Developing the Model 2.7.3 Re-running the Model with New Data 2.8 Creating a Production System 2.9 Collecting Data 2.10 Modeling Logic 2.11 Practical Solution of LP Models 2.11.1 Problem Size 2.11.2 Ease of Solution 2.12 Summary and Recommended Bibliography 2.13 Exercises 3 Mathematical Solution Techniques 3.1 Introduction 3.1.1 Standard Formulation of Linear Programming Problems 3.1.2 Slack and Surplus Variables 3.1.3 Underdetermined Linear Equations and Optimization 3.2 Linear Programming 3.2.1 Simplex Algorithm — A Brief Overview 3.2.2 Solving the Boat Problem with the Simplex Algorithm 3.2.3 Interior-Point Methods — A Brief Overview 3.2.4 LP as a Subroutine 3.3 Mixed Integer Linear Programming 3.3.1 Solving the Farmer's Problem Using Branch and Bound 3.3.2 Solving Mixed Integer Linear Programming Problems 3.3.3 Cutting Planes and Branch and Cut (B&C) 3.3.4 Branch and Price: Optimization with Column Generation 3.4 Interpreting the Results 3.4.1 LP Solution 3.4.2 Outputting Results and Report Writing 3.4.3 Dual Value (Shadow Price) 3.4.4 Reduced Costs 3.5 Duality 3.5.1 Constructing the Dual Problem 3.5.2 Interpreting the Dual Problem 3.5.3 Duality Gap and Complementarity 3.6 Summary and Recommended Bibliography 3.7 Exercises 3.8 Appendix 3.8.1 Linear Programming — A Detailed Description 3.8.2 Computing Initial Feasible LP Solutions 3.8.3 LP Problems with Upper Bounds 3.8.4 Dual Simplex Algorithm 3.8.5 Interior-Point Methods — A Detailed Description 3.8.5.1 A Primal–Dual Interior-Point Method 3.8.5.2 Predictor–Corrector Step 3.8.5.3 Computing Initial Points 3.8.5.4 Updating the Homotopy Parameter 3.8.5.5 Termination Criterion 3.8.5.6 Basis Identification and Cross-Over 3.8.5.7 Interior-Point Versus Simplex Methods 3.8.6 Branch and Bound with LP Relaxation 4 Problems Solvable Using Linear Programming 4.1 Cutting Stock: Trimloss Problems 4.1.1 Example: A Trimloss Problem in the Paper Industry 4.1.2 Example: An Integer Trimloss Problem 4.2 The Food Mix Problem 4.3 Transportation and Assignment Problems 4.3.1 The Transportation Problem 4.3.2 The Transshipment Problem 4.3.3 The Assignment Problem 4.3.4 Transportation and Assignment Problems as Subproblems 4.3.5 Matching Problems 4.4 Network Flow Problems 4.4.1 Illustrating a Network Flow Problem 4.4.2 The Structure and Importance of Network Flow Models 4.4.3 Case Study: A Telephone Betting Scheduling Problem 4.4.4 Other Applications of Network Modeling Technique 4.5 Unimodularity 4.6 Summary and Recommended Bibliography 4.7 Exercises 5 How Optimization Is Used in Practice: Case Studies in Linear Programming 5.1 Optimizing the Production of a Chemical Reactor 5.2 An Apparently Nonlinear Blending Problem 5.2.1 Formulating the Direct Problem 5.2.2 Formulating the Inverse Problem 5.2.3 Analyzing and Reformulating the Model 5.3 Data Envelopment Analysis (DEA) 5.3.1 Example Illustrating DEA 5.3.2 Efficiency 5.3.3 Inefficiency 5.3.4 More Than One Input 5.3.5 Small Weights 5.3.6 Applications of DEA 5.3.7 A General Model for DEA 5.4 Vector Minimization and Goal Programming 5.4.1 Solution Approaches for Multi-Criteria Optimization Problems 5.4.2 A Case Study Involving Soft Constraints 5.4.3 A Case Study Exploiting a Hierarchy of Goals 5.5 Limitations of Linear Programming 5.5.1 Single Objective 5.5.2 Assumption of Linearity 5.5.3 Satisfaction of Constraints 5.5.4 Structured Situations 5.5.5 Consistent and Available Data 5.6 Summary 5.7 Exercises 6 Modeling Structures Using Mixed Integer Programming 6.1 Using Binary Variables to Model Logical Conditions 6.1.1 General Integer Variables and Logical Conditions 6.1.2 Transforming Logical into Arithmetical Expressions 6.1.3 Logical Expressions with Two Arguments 6.1.4 Logical Expressions with More Than Two Arguments 6.2 Logical Restrictions on Constraints 6.2.1 Bound Implications on Single Variables 6.2.2 Bound Implications on Constraints 6.2.3 Disjunctive Sets of Implications 6.3 Modeling Non-Zero Variables 6.4 Modeling Sets of All-Different Elements 6.5 Modeling Absolute Value Terms 6.6 Nonlinear Terms and Equivalent MILP Formulations 6.7 Modeling Products of Binary Variables 6.8 Special Ordered Sets 6.8.1 Special Ordered Sets of Type 1 6.8.2 Special Ordered Sets of Type 2 6.8.3 Linked Ordered Sets 6.8.4 Families of Special Ordered Sets 6.9 Improving Formulations by Adding Logical Inequalities 6.10 Summary 6.11 Exercises 7 Types of Mixed Integer Linear Programming Problems 7.1 Knapsack and Related Problems 7.1.1 The Knapsack Problem 7.1.2 Case Study: Float Glass Manufacturing 7.1.3 The Generalized Assignment Problem 7.1.4 The Multiple Binary Knapsack Problem 7.2 The Traveling Salesman Problem 7.2.1 Postman Problems 7.2.2 Vehicle Routing Problems 7.2.3 Case Study: Heating Oil Delivery 7.3 Facility Location Problems 7.3.1 The Uncapacitated Facility Location Problem 7.3.2 The Capacitated Facility Location Problem 7.4 Set Covering, Partitioning, and Packing 7.4.1 The Set Covering Problem 7.4.2 The Set Partitioning Problem 7.4.3 The Set Packing Problem 7.4.4 Additional Applications 7.4.5 Case Study: Airline Management at Delta Air Lines 7.5 Satisfiability 7.6 Bin Packing 7.6.1 The Bin Packing Problem 7.6.2 The Capacitated Plant Location Problem 7.7 Clustering Problems 7.7.1 The Capacitated Clustering Problem 7.7.2 The p-Median Problem 7.8 Scheduling Problems 7.8.1 Example A: Scheduling Machine Operations 7.8.2 Example B: A Flowshop Problem 7.8.3 Example C: Scheduling Involving Job Switching 7.8.4 Case Study: Bus Crew Scheduling 7.9 Summary and Recommended Bibliography 7.10 Exercises 8 Case Studies and Problem Formulations 8.1 A Depot Location Problem 8.2 Planning and Scheduling Across Time Periods 8.2.1 Indices, Data, and Variables 8.2.2 Objective Function 8.2.3 Constraints 8.3 Distribution Planning for a Brewery 8.3.1 Dimensions, Indices, Data, and Variables 8.3.2 Objective Function 8.3.3 Constraints 8.3.4 Running the Model 8.4 Financial Modeling 8.4.1 Optimal Purchasing Strategies 8.4.2 A Yield Management Example 8.5 Post-Optimal Analysis 8.5.1 Getting Around Infeasibility 8.5.2 Basic Concept of Ranging 8.5.3 Parametric Programming 8.5.4 Sensitivity Analysis in MILP Problems 8.6 Summary and Recommended Bibliography 9 User Control of the Optimization Process and Improving Efficiency 9.1 Preprocessing 9.1.1 Presolve 9.1.1.1 Arithmetic Tests 9.1.1.2 Tightening Bounds 9.1.2 Disaggregation of Constraints 9.1.3 Coefficient Reduction 9.1.4 Clique Generation 9.1.5 Cover Constraints 9.2 Efficient LP Solving 9.2.1 Warm Starts 9.2.2 Scaling 9.3 Good Modeling Practice 9.4 Choice of Branch in Integer Programming 9.4.1 Control of the Objective Function Cut-Off 9.4.2 Branching Control 9.4.2.1 Entity Choice 9.4.2.2 Choice of Branch or Node 9.4.3 Priorities 9.4.4 Branching on Special Ordered Sets 9.4.5 Branching on Semi-Continuous and Partial Integer Variables 9.5 Symmetry and Optimality 9.6 Summary 9.7 Exercises 10 How Optimization Is Used in Practice: Case Studies in Integer Programming 10.1 What Can be Learned from Real-World Problems? 10.2 Three Instructive Solved Real-World Problems 10.2.1 Contract Allocation 10.2.2 Metal Ingot Production 10.2.3 Project Planning 10.2.4 Conclusions 10.3 A Case Study in Production Scheduling 10.4 Optimal Worldwide Production Plans 10.4.1 Brief Description of the Problem 10.4.2 Mathematical Formulation of the Model 10.4.2.1 General Framework 10.4.2.2 Time Discretization 10.4.2.3 Including Several Market Demand Scenarios 10.4.2.4 The Variables 10.4.2.5 The State of the Production Network 10.4.2.6 Exploiting Fixed Setup Plans 10.4.2.7 Keeping Track of Mode Changes 10.4.2.8 Coupling Modes and Production 10.4.2.9 Minimum Production Requirements 10.4.2.10 Modeling Stock Balances and Inventories 10.4.2.11 Modeling Transport 10.4.2.12 External Purchase 10.4.2.13 Modeling Sales and Demands 10.4.2.14 Defining the Objective Function 10.4.3 Remarks on the Model Formulation 10.4.3.1 Including Minimum Utilization Rates 10.4.3.2 Exploiting Sparsity 10.4.3.3 Avoiding Zero Right-Hand Side Equations 10.4.3.4 The Structure of the Objective Function 10.4.4 Model Performance 10.4.5 Reformulations of the Model 10.4.5.1 Estimating the Quality of the Solution 10.4.5.2 Including Mode-Dependent Capacities 10.4.5.3 Modes, Change-Overs and Production 10.4.5.4 Reformulated Capacity Constraints 10.4.5.5 Some Remarks on the Reformulation 10.4.6 What Can be Learned from This Case Study? 10.5 A Complex Scheduling Problem 10.5.1 Description of the Problem 10.5.2 Structuring the Problem 10.5.2.1 Orders, Procedures, Tasks, and Jobs 10.5.2.2 Labor, Shifts, Workers and Their Relations 10.5.2.3 Machines 10.5.2.4 Services 10.5.2.5 Objectives 10.5.3 Mathematical Formulation of the Problem 10.5.3.1 General Framework 10.5.3.2 Time Discretization 10.5.3.3 Indices 10.5.3.4 Data 10.5.3.5 Main Decision Variables 10.5.3.6 Other Variables 10.5.3.7 Auxiliary Sets 10.5.4 Time-Indexed Formulations 10.5.4.1 The Delta Formulation 10.5.4.2 The Alpha Formulation 10.5.5 Numerical Experiments 10.5.5.1 Description of Small Scenarios 10.5.5.2 A Client's Prototype 10.5.6 What Can be Learned from This Case Study? 10.6 Telecommunication Service Network 10.6.1 Description of the Model 10.6.1.1 Technical Aspects of Private Lines 10.6.1.2 Tariff Structure of Private Line Services 10.6.1.3 Demands on Private Line Services 10.6.1.4 Private Line Network Optimization 10.6.2 Mathematical Model Formulation 10.6.2.1 General Foundations 10.6.2.2 Flow Conservation Constraints 10.6.2.3 Edge Capacity Constraints 10.6.2.4 Additional Constraints 10.6.2.5 Objective Function of the Model 10.6.2.6 Estimation of Problem Size 10.6.2.7 Computational Needs 10.6.3 Analysis and Reformulations of the Models 10.6.3.1 Basic Structure of the Model 10.6.3.2 Some Valid Inequalities: Edge Capacity Cuts 10.6.3.3 Some Improvements to the Model Formulation 10.6.3.4 A Surrogate Problem with a Simplified Cost Function 10.6.3.5 More Valid Inequalities: Node Flow Cuts 10.6.3.6 Some Remarks on Performance 10.7 Synchronization of Batch and Continuous Processes 10.7.1 Time Sequencing Constraints 10.7.2 Reactor Availability Constraints 10.7.3 Exploiting Free Reactor Time — Delaying Campaign Starts 10.7.4 Restricting the Latest Time a Reactor Is Available 10.8 Summary and Recommended Bibliography 10.9 Exercises 11 Beyond LP and MILP Problems 11.1 Fractional Programming * 11.2 Recursion or Successive Linear Programming 11.2.1 An Example 11.2.2 The Pooling Problem 11.3 Optimization Under Uncertainty* 11.3.1 Motivation and Overview 11.3.2 Stochastic Programming 11.3.2.1 Example: The Newsvendor Problem 11.3.2.2 Scenario-Based Stochastic Optimization 11.3.2.3 Terminology and Technical Preliminaries 11.3.2.4 Practical Usage and Policies 11.3.2.5 The Value of the Stochastic Extension 11.3.3 Recommended Literature 11.4 Quadratic Programming 11.5 Summary and Recommended Bibliography 11.6 Exercises 12 Mathematical Solution Techniques — The Nonlinear World 12.1 Unconstrained Optimization 12.2 Constrained Optimization — Foundations and Theorems 12.3 Reduced Gradient Methods 12.4 Sequential Quadratic Programming 12.5 Interior-Point Methods 12.6 Mixed Integer Nonlinear Programming 12.6.1 Definition of an MINLP Problem 12.6.2 Some General Comments on MINLP 12.6.3 Deterministic Methods for Solving MINLP Problems 12.6.4 Algorithms and Software for Solving Non-convex MINLP Problems 12.7 Global Optimization — Mathematical Background 12.8 Summary and Recommended Bibliography 12.9 Exercises 13 Global Optimization in Practice 13.1 Global Optimization Applied to Real-World Problems 13.2 A Trimloss Problem in Paper Industry 13.3 Cutting and Packing Involving Convex Objects 13.3.1 Modeling the Cutting Constraints 13.3.1.1 Cutting Constraints for Circles 13.3.1.2 Cutting Conditions for Polygons 13.3.2 Problem Structure and Symmetry 13.3.3 Some Results 13.4 Summary and Recommended Bibliography 13.5 Exercises 14 Polylithic Modeling and Solution Approaches 14.1 Polylithic Modeling and Solution Approaches (PMSAs) 14.1.1 Idea and Foundations of Polylithic Solution Approaches 14.1.1.1 Monolithic Models and Solution Approaches 14.1.1.2 Polylithic Modeling and Solution Approaches 14.1.2 Problem-Specific Preprocessing 14.1.2.1 Dynamic Reduction of Big-M Coefficients 14.1.2.2 Bound Tightening for Integer Variables 14.1.2.3 Data Consistency Checks 14.1.3 Mathematical Algorithms 14.1.3.1 Branch-and-Bound and Branch-and-Cut Methodologies 14.1.3.2 Decomposition Methods 14.1.3.3 Lagrange Relaxation 14.1.3.4 Bilevel Programming 14.1.4 Primal Heuristics 14.1.4.1 Structured Primal Heuristics 14.1.4.2 Hybrid Methods 14.1.5 Proving Optimality Using PMSAs 14.2 PMSAs Applied to Real-World Problems 14.2.1 Cutting Stock and Packing 14.2.1.1 Complete Enumeration 14.2.1.2 Incremental, Swapping, and Tour-Reversing Approaches 14.2.2 Evolutionary Approach 14.2.3 Optimal Breakpoints 14.3 Summary and Recommended Bibliography 14.4 Exercises 15 Cutting and Packing Beyond and Within Mathematical Programming 15.1 Introduction 15.2 Phi-objects 15.2.1 Phi-objects 15.2.2 Primary and Composed Phi-objects 15.2.3 Geometric Parameters of Phi-objects 15.2.4 Position Parameters of Phi-objects 15.2.5 Interaction of Phi-objects 15.3 Phi-functions: Relating Phi-objects 15.3.1 Construction of Phi-functions for Various Situations 15.3.1.1 Phi-function for Two Circles 15.3.1.2 Phi-function for Two Spheres 15.3.1.3 Phi-function for Two Rectangles 15.3.1.4 Phi-function for Two Cuboids 15.3.1.5 Phi-function for Two Parallel Circular Cylinders 15.3.1.6 Phi-function for Convex Polygons 15.3.1.7 Phi-function for Non-convex Polygons 15.3.1.8 Phi-function for a Rectangle and a Circle 15.3.1.9 Phi-function for a Convex Polygon and a Circle 15.3.1.10 Phi-function for a Composed Object and a Circle 15.3.1.11 Phi-functions for More General Objects 15.3.1.12 Phi-functions with Rotational Angles 15.3.1.13 Normalized Phi-function 15.3.1.14 Normalized Phi-function for Two Circles 15.3.2 Properties of Phi-functions 15.4 Mathematical Optimization Model 15.4.1 Objective Function 15.4.2 Constraints 15.4.3 Simplifying Distance Constraints 15.4.4 General Remarks 15.5 Solving the Optimization Problem 15.6 Numerical Examples 15.6.1 Arranging Two Triangles 15.6.2 Arranging Two Irregular Objects 15.7 Conclusions 15.8 Summary and Recommended Bibliography 15.9 Exercises 16 The Impact and Implications of Optimization 16.1 Benefits of Mathematical Programming to Users 16.2 Implementing and Validating Solutions 16.3 Communicating with Management 16.4 Keeping a Model Alive 16.5 Mathematical Optimization in Small and Medium Size Business 16.6 Online Optimization by Exploiting Parallelism? 16.6.1 Parallel Optimization: Status and Perspectives in 1997 16.6.1.1 Algorithmic Components Suitable for Parallelization 16.6.1.2 Non-determinism in Parallel Optimization 16.6.1.3 Platforms for Parallel Optimization Software 16.6.1.4 Design Decisions 16.6.1.5 Implementation 16.6.1.6 Performance 16.6.1.7 Acceptability 16.6.2 Parallel Optimization: Status and Perspectives in 2020 16.6.2.1 Parallel Algorithms and Solver Worlds 16.6.2.2 Parallel Metaheuristics 16.6.2.3 Machine Learning and Hyper-Parameter Optimization 16.6.2.4 Parallel Optimization in the Real World 16.7 Summary 17 Concluding Remarks and Outlook 17.1 Learnings from the Examples and Models 17.2 Future Developments 17.2.1 Pushing the Limits 17.2.2 Cloud Computing 17.2.3 The Importance of Modeling 17.2.4 Tools Around Optimization 17.2.5 Visualization of Input Data and Output Results 17.2.5.1 Tools and Software 17.2.5.2 The Broader Company Picture: IT 17.2.5.3 Summary 17.2.6 Increasing Problem Size and Complexity 17.2.7 The Future of Planning and Scheduling 17.2.8 Simultaneous Operational Planning & Design and Strategic Optimization 17.3 Mathematical Optimization for a Better World * A Software Related Issues A.1 Accessing Data from Algebraic Modeling Systems A.2 List of Case Studies and Model Files B Glossary C Mathematical Foundations: Linear Algebra and Calculus C.1 Sets and Quantifiers C.2 Absolute Value and Triangle Inequality C.3 Vectors in Rn and Matrices in M(mn,R) C.4 Vector Spaces, Bases, Linear Independence, and Generating Systems C.5 Rank of Matrices, Determinant, and Criteria for Invertible Matrices C.6 Systems of Linear Equations C.7 Some Facts on Calculus References Index