Operations Planning: Mixed Integer Optimization Models

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.

Table of Contents

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

Write a review