A reference for those working at the interface of operations planning and optimization modeling, Operations Planning: Mixed Integer Optimization Models blends essential theory and powerful approaches to practical operations planning problems. It presents a set of classical optimization models with widespread application in operations planning. The discussion of each of these classical models begins with the motivation for studying the problem as well as examples of the problem’s application in operations planning contexts. The book explores special structural results and properties of optimal solutions that have led to effective algorithmic solution approaches for each problem class.
Each of the models and solution methods presented is the result of high-impact research that has been published in the scholarly literature, with appropriate references cited throughout the book. The author highlights the close relationships among the models, examining those situations in which a particular model results as a special case of other related models or how one model generalizes another. Understanding these relationships allows you to more easily characterize new models being developed through their relationships to classical models.
The models and methods presented in the book have widespread application in operations planning. It enables you to recognize the structural similarities between models and to recognize these structural elements within other contexts. It also gives you an understanding of various critical operations research techniques and classical operations planning models, without the need to consult numerous sources.
Introduction and Purpose
Operations Planning
Mixed Integer Optimization
Optimization Models in Operations Planning
The Knapsack Problem
Introduction
Knapsack Problem 0-1 Programming Formulation
Relation to the subset sum problem
Linear Relaxation of the 0-1 Knapsack Problem
Asymptotically Optimal Heuristic
Fast Approximation Algorithm
Valid Inequalities
Review
Set Covering, Packing, and Partitioning
Introduction
Problem Definition and Formulation
Solution Methods
Bin packing heuristics
Column generation and the set partitioning problem
Branch-and-price for the set partitioning problem
Review
The Generalized Assignment Problem
Introduction
GAP Problem Definition and Formulation
Lagrangian Relaxation Technique
Lagrangian Relaxation for the GAP
Branch-and-Price for the GAP
Greedy Algorithms and Asymptotic Optimality
Review
Uncapacitated Economic Lot Sizing
Introduction
The basic UELSP Model
Fixed-charge network flow interpretation
Dynamic programming solution method
Tight Reformulation of UELSP
Lagrangian relaxation shows a tight formulation
An O(T log T) Algorithm for the UELSP
Implications of Backordering
Review
Capacitated Lot Sizing
Introduction
Capacitated Lot Sizing Formulation
Relation to the (J-1 Knapsack Problem
Fixed-charge network flow interpretation
Dynamic programming approach
The Equal-Capacity Case
FPTAS for Capacitated Lot Sizing
Structure of the dynamic programming approach
Approximation of the dynamic program
Valid Inequalities for the CELSP
(S,1) inequalities
Facets for the equal-capacity CELSP
Generalized flow-cover inequalities
Review
Multistage Production and Distribution Planning
Introduction
Models with Dynamic Demand
Serial systems with dynamic demand
Production networks with non-speculative costs
Constrant-factor approximations for special cases
Models with Constant Demand Rates
Stationary, nested, power-of-two policies
The joint replenishment problem
The one-warehouse multi-retailer problem
Review
Discrete Facility Location Problems
Introduction
Relation to Previous Models in this Book
Cost-minimizing version of the FLP
Relationship of the FLP to lot sizing problems
Single-sourcing version of the FLP and the GAP
Set covering and FLP complexity
Dual-Ascent Method for the Uncapacitated FLP
Approximation Algorithms for the Metric UFLP
Randomization and derandomization
Solution Methods for the General FLP
Lagrangian relazation for the FLP
Valid inequalities for the FLP
Approximation algorithms for the FLP
Review
Vehicle Routing and Traveling Salesman Problems
Introduction
The TSP Graph and Complexity
Formulating the TSP as an Optimization Problem
Comb Inequalities
Heuristic Solutions for the TSP
Nearest neighbor heuristic
The sweep method
Minimum spanning tree based methods
Local improvement methods
The Vehicle Routing Problem
Exact solution of the VRP via branch-and-price
A GAP-based heuristic solution approach for the VRP
The Clarke-Wright savings heuristic method
Additional heuristic methods for the VRP
Review
Bibliography
Index
Biography
Joseph Geunes has been on the faculty of the Industrial and Systems Engineering Department at the University of Florida since 1998. His research focuses on applying operations research techniques to large-scale production and logistics planning problems. Professor Geunes serves as Co-Director of the Supply Chain And Logistics Engineering (SCALE) Research Center and as Director of the Outreach Engineering Management professional Master’s Degree program at the University of Florida. He has co-authored more than 30 peer-reviewed journal articles, which have appeared in journals such as Operations Research, Manufacturing & Service Operations Management, IIE Transactions, and Naval Research Logistics. He also serves as an Associate Editor for OMEGA, Computers & IE, and Decision Sciences, and is on the editorial boards of Production and Operations Management and the International Journal of Inventory Research. Professor Geunes received a Ph.D. (1999) and MBA (1993) from Penn State University, as well as a B.S. in Electrical Engineering (1990) from Drexel University.
"The book under review gathers several of the most useful models for optimization with widespread applicability in operation planning. ... With the exception of Chapter 1, each chapter contains several numerical examples and ends with a set of exercises. This approach makes the book very helpful for a graduate course on mixed integer optimization models for non-mathematically oriented, business administration students. With its precise references to a bibliography of 120 titles ranging from 1954 to 2010, the book can serve well as a reference for researchers in the domain of operations planning."
—Mihai Cipu (Bucureşti), Zentralblatt MATH, 1327
"The book provides a technically sound, yet very readable, description of various state-of-the-art mathematical programming techniques that can be used to tackle relevant operations planning problems. In early chapters, important mathematical programming concepts are introduced in the context of archetypical optimization problems, such as the knapsack and the set covering problem. In later chapters, the book covers all classical operations planning problems; i.e., problems in production planning (single and multi-stage), distribution planning, location, and routing. Although none of the material is really new, it is nice to have it well-presented in a single book instead of scattered among various journal papers. Where appropriate, the material is illustrated with meaningful numerical examples and figures. Moreover, every chapter is concluded with challenging exercises, making this book suitable for courses at the advanced undergraduate or graduat level. Because it covers a wide range of techniques, the book can also be used to introduce readers to various concepts in mathematical programming, even if they don’t have a particular interest in operations planning. In that case, the specific operations planning problems merely serve to illustrate the techniques."
—Albert P.M. Wagelmans, Erasmus University Rotterdam, The Netherlands
