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