This textbook provides a comprehensive modeling, reformulation and optimization approach for solving production planning and supply chain planning problems, covering topics from a basic introduction to planning systems, mixed integer programming (MIP) models and algorithms through the advanced description of mathematical results in polyhedral combinatorics required to solve these problems. Based on twenty years worth of research in which the authors have played a significant role, the book addresses real life industrial production planning problems (involving complex production structures with multiple production stages) using MIP modeling and reformulation approach. The book provides an introduction to MIP modeling and to planning systems, a unique collection of reformulation results, and an easy to use problem-solving library. This approach is demonstrated through a series of real life case studies, exercises and detailed illustrations. Review by Jakub Marecek (Computer Journal) The emphasis put on mixed integer rounding and mixing sets, heuristics in-built in general purpose integer programming solvers, as well as on decompositions and heuristics using integer programming should be praised... There is no doubt that this volume offers the present best introduction to integer programming formulations of lotsizing problems, encountered in production planning. (2007)
Table of Contents
Cover
Production Planning by Mixed Integer Programming
ISBN-10: 0387299599 ISBN-13: 9780387299594
Preface
Case Studies and Web Site
Contents
Part I Production Planning and MIP
Introduction
1 The Modeling and Optimization Approach
1.1 A Tiny Planning Model
o 1.1.1 Problem Description
o 1.1.2 Some Solutions
o 1.1.3 A First Model
o 1.1.4 Optimizing the Model
1.2 A Production Planning Example
o 1.2.1 Problem Description GW and the Global Supply Chain Department
o 1.2.2 Modeling
o 1.2.3 Mathematical Formulation
o 1.2.4 Implementation
o 1.2.5 Optimization Results
Exercises
Notes
2 Production Planning Models and Systems
2.1 Some Production Planning Models
2.2 The MRP Planning Model
o 2.2.1 The Planning Model and Its Inputs
o 2.2.2 The Planning Process: Single Item Decomposition
o 2.2.3 Limitations of MRP and the Optimization Answer
2.3 Advanced Planning Systems
o 2.3.1 Supply Chain Planning
o 2.3.2 Advanced Planning Systems and the Supply Chain Planning Matrix
2.4 Some Supply Chain Planning Problems
o 2.4.1 Strategic Network Design Problems
o 2.4.2 Supply Chain Master Planning Problems
Notes
3 Mixed Integer Programming Algorithms
3.1 Mixed Integer Linear Programs
3.2 Running Time of Algorithms
o 3.2.1 Performance of an Algorithm
o 3.2.2 The Size of a Formulation
3.3 Branch-and-Bound Algorithm
o 3.3.1 The Enumeration Principle
o 3.3.2 The Branch-and-Bound Algorithm
o 3.3.3 Node Selection and Branching Rules
o 3.3.4 Solution Quality and Duality Gap
3.4 Reformulation
o 3.4.1 The Quality of a Formulation Good and Bad Formulations
o 3.4.2 Valid Inequalities
o 3.4.3 A Priori Reformulation
o 3.4.4 A Priori and Extended Reformulation
3.5 Branch-and-Cut Algorithm
o 3.5.1 Separation Algorithm
o 3.5.2 Cutting Plane Algorithm
o 3.5.3 Branch-and-Cut Algorithm
3.6 Primal Heuristics - Finding Feasible Solutions
o 3.6.1 Construction Heuristics
o 3.6.2 Improvement Heuristics
Notes
4 Classi.cation and Reformulation
Motivation
Objective
Contents
4.1 Using Reformulations for Lot-Sizing Models
o 4.1.1 Using A Priori Extended Reformulations
o 4.1.2 Using Cutting Planes
o 4.1.3 Using Approximate Reformulations
4.2 The Decomposition Approach for Complex Models
4.3 Model Classi.cation
o 4.3.1 Single-Item Classi.cation
o 4.3.2 Description of the Field PROB
o 4.3.3 Description of the Field CAP
o 4.3.4 Mathematical Formulations for PROB-CAP
o 4.3.5 Description of the Field VAR
o 4.3.6 Mathematical Formulations for PROB-CAP-VAR Backlogging
o 4.3.7 The Classi.cation PROB-CAP-VAR
4.4 Reformulation Results: What and Where
o 4.4.1 Results for PROB-[U, CC]
o 4.4.2 Results for Backlogging Models PROB-[U, CC]-B
o 4.4.3 Results for Start-Up Cost Models PROB-[U, CC]-SC
o 4.4.4 The Reformulation Procedure
4.5 A Production Planning Example: Reformulation and Solution
Exercises
Notes
5 Reformulations in Practice
Motivation
Objectives
Content
5.1 Extended Reformulations
o 5.1.1 The Classical Approach for WW-U
o 5.1.2 The Black-Box Approach for WW-U
o 5.1.3 The Classical Approach for LS-U
o 5.1.4 The Black-Box Approach for LS-U
5.2 Cut Separation
o 5.2.1 The Classical Approach for LS-U
o 5.2.2 The Black-Box Approach for LS-U
5.3 Heuristics in LS-LIB
o 5.3.1 Calling a Construction Heuristic
o 5.3.2 Calling an Improvement Heuristic
5.4 LS-LIB Procedures
o 5.4.1 Reformulations - XForm
o 5.4.2 Cutting Plane Separation - XCut
o 5.4.3 Heuristics - XHeur
5.5 Two Practice Cases
o 5.5.1 Consumer Goods Production Line: Problem Description
o 5.5.2 Cleaning Liquids Bottling Line: Problem Description
5.6 The Consumer Goods Production Line Case
o 5.6.1 Initial Classi.cation
o 5.6.2 Initial Formulation
o 5.6.3 Reformulation and Algorithms
o 5.6.4 Results
o 5.6.5 Sensitivity Analysis
5.7 The Cleaning Liquids Bottling Line Case
o 5.7.1 Initial Classi.cation
o 5.7.2 Initial Formulation
o 5.7.3 Reformulation and Algorithms
o 5.7.4 Results
o 5.7.5 Sensitivity Analysis
o 5.7.6 Heuristics
Exercises
Notes
Part II Basic Polyhedral Combinatorics for Production Planning and MIP
6 Mixed Integer Programming Algorithms and Decomposition Approaches
6.1 Polyhedra, Formulations, Optimization, and Separation
o 6.1.1 Formulations of an Integer Program De.nition 6.2 The set of points P = x
o 6.1.2 Valid Inequality Representation of Polyhedra
o 6.1.3 Extreme Point Representation of Polyhedra
o 6.1.4 Cutting Planes and the Separation Problem
o 6.1.5 Extended Formulations
o 6.1.6 Optimization and Separation: Polynomial Equivalence
o 6.1.7 Optimization and Separation for Polynomially Solvable Problems
6.2 Decomposition and Reformulation
o 6.2.1 Decomposition of a Multi-Item Lot-Sizing Problem
6.3 Decomposition Algorithms
o 6.3.1 Decomposition Algorithms I: Valid Inequalities and Separation
o 6.3.2 Decomposition Algorithms II: Lagrangian Relaxation and Column Generation
o 6.3.3 Decomposition Algorithms III: Hybrid Algorithms
6.4 Convex Hull Proofs
Exercises
Notes
7 Single-Item Uncapacitated Lot-Sizing
7.1 The Uncapacitated Lot-Sizing Problem (LS-U)
7.2 Structure of Optimal Solutions of LS-U
7.3 A Dynamic Programming Algorithm for LS-U
7.4 Linear Programming Reformulations of LS-U
o 7.4.1 Valid Inequalities for LS-U
o 7.4.2 Extended Formulations for LS-U
7.5 Wagner-Whitin Costs
7.6 Partial Formulations
7.7 Some Convex Hull Proofs
Exercises
Notes
8 Basic MIP and Fixed Cost Flow Models
8.1 A Two-Variable Basic Mixed Integer Set
o 8.1.1 Valid Inequalities and Formulations Proposition 8.1 i. Let f = b -b=0. The simple mixed integer rounding
o 8.1.2 Optimal Solutions
8.2 The MIP Set
8.3 The Mixing Set
o 8.3.1 Extreme Points Proposition 8.3 The extreme rays of conv(X MIX
o 8.3.2 Valid Inequalities
o 8.3.3 Separation of the Mixing Inequalities
o 8.3.4 An Extended Formulation for conv(X MIX
o 8.3.5 Application of the Mixing Reformulation
8.4 Reformulation Approaches for More General Mixing Sets
8.5 The Continuous Mixing Set
8.6 Divisible Capacity Mixing Sets
o 8.6.1 The Two-Capacity Mixing Set
o 8.6.2 The Divisible Mixing Set
8.7 The Continuous Integer Knapsack Set and the Gomory Mixed Integer Set
8.8 The Continuous 0-1 Knapsack Set
8.9 The Binary Single-Node Flow Set
8.10 Some Convex Hull Proofs
Exercises
Notes
Part III Single-Item Lot-Sizing
9 Lot-Sizing with Capacities
9.1 Complexity
9.2 Regeneration Intervals
9.3 Discrete Lot-Sizing with Constant Capacities
o 9.3.1 Valid Inequalities for DLS-CC
o 9.3.2 Optimization for DLS-CC
o 9.3.3 Parametric Optimization for DLS-CC
9.4 Discrete Lot-Sizing with Initial Stock and Constant Capacities
o 9.4.1 Valid Inequalities for DLSI-CC
o 9.4.2 Extended Formulation for DLSI-CC
9.5 Lot-Sizing with Wagner-Whitin Costs and Constant Capacities
o 9.5.1 Optimization for WW-CC
o 9.5.2 Valid Inequalities for WW-CC
o 9.5.3 Extended Formulations for WW-CC
9.6 Lot-Sizing with Constant Capacities
o 9.6.1 Optimization: An Algorithm for LS-CC
o 9.6.2 Valid Inequalities for LS-CC
o 9.6.3 Extended Formulation for LS-CC
o 9.6.4 R�esum�e of Results
9.7 Lot-Sizing with Varying Capacities
o 9.7.1 Valid Inequalities for WW-C
o 9.7.2 Simple Valid Inequalities for LS-C
o 9.7.3 Submodular Inequalities for LS-C
o 9.7.4 Lifted (l, S) Inequalities for DLSI-C Valid Inequalities for DLSI-C
Exercises
Notes
10 Backlogging and Start-Ups
10.1 Backlogging
10.2 Backlogging: The Uncapacitated Case
o 10.2.1 Extreme Points and Optimization
o 10.2.2 Tight Formulations and Inequalities for LS-U-B Valid inequalities
o 10.2.3 Tight Formulations and Inequalities for WW-U-B
10.3 Backlogging: The Constant Capacity Case
o 10.3.1 Discrete Lot-Sizing with Backlogging DLS-CC-B
o 10.3.2 Discrete Lot-Sizing with Initial Stocks and Backlogging
o 10.3.3 Lot-Sizing with Wagner-Whitin Costs and Backlogging
o 10.3.4 Lot-Sizing with Backlogging LS-CC-B The Optimization Problem
o 10.3.5 R�esum�e of Results
10.4 Start-Up Costs: The Uncapacitated Case
o 10.4.1 A Dynamic Programming Algorithm for LS-U-SC
o 10.4.2 Tight Formulations and Inequalities for LS-U-SC Valid Inequalities and Convex Hull of X LS-U-SC
10.5 Start-Up Costs: The Capacitated Case
o 10.5.1 The Discrete Lot-Sizing Problem DLS-CC-SC
o 10.5.2 Capacitated Lot-Sizing with Start-Up Costs LS-C-SC Valid Inequalities
o 10.5.3 R�esum�e of Results
10.6 Backlogging and Start-Ups WW-U-B, SC
Exercises
Notes
11 Single-Item Variants
11.1 Sales or Variable Demand (SL)
o 11.1.1 The Uncapacitated Case: Sales and Arbitrary Demands
o 11.1.2 The Uncapacitated Case: Sales and Nonnegative Demands
11.2 Lower Bounds on Production (LB)
o 11.2.1 A Wagner-Whitin Relaxation WW-CC-LB
o 11.2.2 A Wagner-Whitin Relaxation with Backlogging
11.3 Lower Bounds on Production in a Set-Up Sequence
o 11.3.1 Almost Full Capacity Production (AF C)
o 11.3.2 Minimum Production Level per Set-Up Sequence (MR)
11.4 Restricted Length Set-Up Sequences (RLS)
o 11.4.1 Varying Length Sequences
o 11.4.2 Constant Length Sequences
11.5 Piecewise Concave Production Costs (CP)
11.6 Production Time Windows (TWP)
o 11.6.1 An Algorithm for WW-U-TWP and Extended Formulation for WW-CC-TWP
o 11.6.2 Indistinguishable Time Windows LS-C-TWP(I)andan Equivalent Problem
o 11.6.3 A Dynamic Programming Algorithm for LS-U-TWP(I)
o 11.6.4 A Tight Extended Formulation for LS-U-TWP(I)
11.7 Upper Bounds on Stocks (SUB)
o 11.7.1 Equivalence to LS-CAP-TWP(I)
o 11.7.2 Valid Inequalities for LS-U-SUB
o 11.7.3 Valid Inequalities for WW-CC-SUB and WW-CC-B, SUB
11.8 Safety Stocks or Piecewise Convex Storage Costs (SS)
o 11.8.1 Mixing Set Relaxations for LS-CC-SS
11.9 A Model with Backlogging, Sales Markets, and Concave Production Costs
11.10 Stochastic Lot-Sizing on a Tree
o 11.10.1 Mixing Set Relaxations with Constant Capacities
o 11.10.2 Valid Inequalities for LS-CC-TREE
Exercises
Notes
Part IV Multi-Item Lot-Sizing
12 Multi-Item Single-Level Problems
12.1 Joint Resource Classi.cation
o 12.1.1 Production Mode Classi.cation
o 12.1.2 Production Quantity Classi.cation
12.2 Production Mode Models: One Set-Up
o 12.2.1 Single Set-Up Constraint: M1
o 12.2.2 Start-Ups and Changeovers M1-{SC, SQ}
12.3 Production Modes: Two or More Set-Ups
o 12.3.1 Two Set-Ups: M2
o 12.3.2 Any Number of Set-Ups
12.4 Production Quantity Constraints PQ
o 12.4.1 Product Resource Constraints PC and PC-SU
12.5 Family Set-Ups: PC-FAM
Exercises
Notes
13 Multi-Level Lot-Sizing Problems
13.1 Production in Series ML-S
o 13.1.1 Optimization for ML-S/LS-U
o 13.1.2 The Echelon Stock Reformulation for ML-S
o 13.1.3 Multi-Commodity Reformulations: Uncapacitated Case
o 13.1.4 Valid Inequalities for ML-S/LS-U
o 13.1.5 Nested Solutions
13.2 Assembly Systems
o 13.2.1 Nested Solutions
o 13.2.2 Lead-Times and Echelon Stocks
13.3 General Systems
13.4 Production and Distribution
o 13.4.1 Production Center and Sales Area Aggregation
o 13.4.2 Sales Area Aggregation
Exercises
Notes
Part V Problem Solving
14 Test Problems
14.1 Making and Packing
o 14.1.1 Problem Description General Context
o 14.1.2 Classi.cation
o 14.1.3 Initial Formulation
o 14.1.4 Reformulations and Algorithms
o 14.1.5 Analysis of Capacity and Customer Service Level
14.2 Storage Rack Production
o 14.2.1 Problem Description General Context
o 14.2.2 Classi.cation
o 14.2.3 Initial Formulation
o 14.2.4 Improving the Initial Formulation
o 14.2.5 Choosing the Appropriate Extended Reformulations
o 14.2.6 Results with Extended Reformulations
o 14.2.7 Results with Primal Heuristics
14.3 Insulating Board Extrusion
o 14.3.1 Problem Description General Context
o 14.3.2 Classi.cation
o 14.3.3 Initial Formulation
o 14.3.4 Improving the Initial Formulation
o 14.3.5 Results with Reformulations
o 14.3.6 The Multi-Period Planning and Scheduling Extension
14.4 Pigment Sequencing
o 14.4.1 Initial Formulation
o 14.4.2 Classi.cation
o 14.4.3 Reformulations Reformulation of the Changeover Variables
o 14.4.4 Computational Results with Reformulations
o 14.4.5 Modeling Periods with No Production
14.5 Process Manufacturing
o 14.5.1 Classi.cation
o 14.5.2 Initial Formulation
o 14.5.3 Reformulation
o 14.5.4 Computational Results
14.6 Powder Production
o 14.6.1 Classi.cation
o 14.6.2 Initial Formulation
o 14.6.3 Testing the Initial Formulation and Reformulations
o 14.6.4 Finding Lower Bounds for Powder Production
o 14.6.5 Finding Upper Bounds for Powder Production
Exercises
Notes
References
Index
Author(s): Yves Pochet, Laurence A. Wolsey
Series: Springer Series in Operations Research and Financial Engineering
Edition: 2006
Publisher: Springer
Year: 2006
Language: English
Pages: 524
Cover......Page 1
Production Planning by Mixed Integer Programming......Page 4
ISBN-10: 0387299599 ISBN-13: 9780387299594......Page 5
Preface......Page 8
Case Studies and Web Site......Page 14
Contents......Page 16
Part I Production Planning and MIP......Page 26
Introduction......Page 28
1 The Modeling and Optimization Approach......Page 32
1.1.1 Problem Description......Page 34
1.1.2 Some Solutions......Page 35
1.1.3 A First Model......Page 36
1.1.4 Optimizing the Model......Page 40
1.2.1 Problem Description GW and the Global Supply Chain Department......Page 41
1.2.2 Modeling......Page 46
1.2.3 Mathematical Formulation......Page 50
1.2.4 Implementation......Page 51
1.2.5 Optimization Results......Page 55
Exercises......Page 58
Notes......Page 61
2 Production Planning Models and Systems......Page 64
2.1 Some Production Planning Models......Page 66
2.2 The MRP Planning Model......Page 71
2.2.1 The Planning Model and Its Inputs......Page 72
2.2.2 The Planning Process: Single Item Decomposition......Page 80
2.2.3 Limitations of MRP and the Optimization Answer......Page 87
2.3.1 Supply Chain Planning......Page 91
2.3.2 Advanced Planning Systems and the Supply Chain Planning Matrix......Page 93
2.4.1 Strategic Network Design Problems......Page 96
2.4.2 Supply Chain Master Planning Problems......Page 97
Notes......Page 99
3 Mixed Integer Programming Algorithms......Page 102
3.1 Mixed Integer Linear Programs......Page 103
3.2.1 Performance of an Algorithm......Page 106
3.2.2 The Size of a Formulation......Page 109
3.3.1 The Enumeration Principle......Page 110
3.3.2 The Branch-and-Bound Algorithm......Page 113
3.3.3 Node Selection and Branching Rules......Page 116
3.3.4 Solution Quality and Duality Gap......Page 117
3.4.1 The Quality of a Formulation Good and Bad Formulations......Page 118
3.4.2 Valid Inequalities......Page 120
3.4.3 A Priori Reformulation......Page 122
3.4.4 A Priori and Extended Reformulation......Page 125
3.5.1 Separation Algorithm......Page 126
3.5.2 Cutting Plane Algorithm......Page 127
3.5.3 Branch-and-Cut Algorithm......Page 129
3.6 Primal Heuristics – Finding Feasible Solutions......Page 132
3.6.1 Construction Heuristics......Page 133
3.6.2 Improvement Heuristics......Page 136
Notes......Page 138
Motivation......Page 140
Contents......Page 141
4.1 Using Reformulations for Lot-Sizing Models......Page 142
4.1.1 Using A Priori Extended Reformulations......Page 143
4.1.2 Using Cutting Planes......Page 146
4.1.3 Using Approximate Reformulations......Page 150
4.2 The Decomposition Approach for Complex Models......Page 151
4.3 Model Classi.cation......Page 153
4.3.1 Single-Item Classi.cation......Page 154
4.3.3 Description of the Field CAP......Page 155
4.3.4 Mathematical Formulations for PROB-CAP......Page 156
4.3.5 Description of the Field VAR......Page 159
4.3.6 Mathematical Formulations for PROB-CAP-VAR Backlogging......Page 161
4.3.7 The Classi.cation PROB-CAP-VAR......Page 164
4.4 Reformulation Results: What and Where......Page 165
4.4.1 Results for PROB-[U, CC]......Page 166
4.4.3 Results for Start-Up Cost Models PROB-[U, CC]-SC......Page 167
4.4.4 The Reformulation Procedure......Page 168
4.5 A Production Planning Example: Reformulation and Solution......Page 170
Notes......Page 178
Objectives......Page 180
5.1.1 The Classical Approach for WW-U......Page 181
5.1.2 The Black-Box Approach for WW-U......Page 182
5.1.3 The Classical Approach for LS-U......Page 184
5.1.4 The Black-Box Approach for LS-U......Page 185
5.2.2 The Black-Box Approach for LS-U......Page 186
5.3.1 Calling a Construction Heuristic......Page 187
5.3.2 Calling an Improvement Heuristic......Page 188
5.4.1 Reformulations – XForm......Page 189
5.4.3 Heuristics – XHeur......Page 190
5.5.1 Consumer Goods Production Line: Problem Description......Page 192
5.5.2 Cleaning Liquids Bottling Line: Problem Description......Page 193
5.6.2 Initial Formulation......Page 194
5.6.3 Reformulation and Algorithms......Page 195
5.6.4 Results......Page 196
5.6.5 Sensitivity Analysis......Page 197
5.7.2 Initial Formulation......Page 198
5.7.4 Results......Page 199
5.7.5 Sensitivity Analysis......Page 200
5.7.6 Heuristics......Page 201
Exercises......Page 202
Notes......Page 205
Part II Basic Polyhedral Combinatorics for Production Planning and MIP......Page 208
6 Mixed Integer Programming Algorithms and Decomposition Approaches......Page 210
6.1.1 Formulations of an Integer Program De.nition 6.2 The set of points P = x......Page 211
6.1.2 Valid Inequality Representation of Polyhedra......Page 212
6.1.3 Extreme Point Representation of Polyhedra......Page 214
6.1.4 Cutting Planes and the Separation Problem......Page 215
6.1.5 Extended Formulations......Page 216
6.1.6 Optimization and Separation: Polynomial Equivalence......Page 217
6.1.7 Optimization and Separation for Polynomially Solvable Problems......Page 218
6.2 Decomposition and Reformulation......Page 220
6.2.1 Decomposition of a Multi-Item Lot-Sizing Problem......Page 221
6.3.1 Decomposition Algorithms I: Valid Inequalities and Separation......Page 222
6.3.2 Decomposition Algorithms II: Lagrangian Relaxation and Column Generation......Page 223
6.3.3 Decomposition Algorithms III: Hybrid Algorithms......Page 226
6.4 Convex Hull Proofs......Page 228
Exercises......Page 229
Notes......Page 230
7.1 The Uncapacitated Lot-Sizing Problem (LS-U)......Page 232
7.2 Structure of Optimal Solutions of LS-U......Page 234
7.3 A Dynamic Programming Algorithm for LS-U......Page 237
7.4.1 Valid Inequalities for LS-U......Page 242
7.4.2 Extended Formulations for LS-U......Page 246
7.5 Wagner–Whitin Costs......Page 249
7.6 Partial Formulations......Page 251
7.7 Some Convex Hull Proofs......Page 253
Exercises......Page 256
Notes......Page 258
8 Basic MIP and Fixed Cost Flow Models......Page 260
8.1.1 Valid Inequalities and Formulations Proposition 8.1 i. Let f = b -b=0. The simple mixed integer rounding......Page 262
8.1.2 Optimal Solutions......Page 264
8.2 The MIP Set......Page 265
8.3 The Mixing Set......Page 266
8.3.2 Valid Inequalities......Page 267
8.3.3 Separation of the Mixing Inequalities......Page 269
8.3.4 An Extended Formulation for conv(X MIX......Page 270
8.4 Reformulation Approaches for More General Mixing Sets......Page 272
8.5 The Continuous Mixing Set......Page 274
8.6.2 The Divisible Mixing Set......Page 278
8.7 The Continuous Integer Knapsack Set and the Gomory Mixed Integer Set......Page 280
8.8 The Continuous 0–1 Knapsack Set......Page 282
8.9 The Binary Single-Node Flow Set......Page 285
8.10 Some Convex Hull Proofs......Page 288
Exercises......Page 289
Notes......Page 294
Part III Single-Item Lot-Sizing......Page 296
9 Lot-Sizing with Capacities......Page 298
9.2 Regeneration Intervals......Page 299
9.3.2 Optimization for DLS-CC......Page 301
9.3.3 Parametric Optimization for DLS-CC......Page 302
9.4 Discrete Lot-Sizing with Initial Stock and Constant Capacities......Page 304
9.4.2 Extended Formulation for DLSI-CC......Page 305
9.5.1 Optimization for WW-CC......Page 306
9.5.2 Valid Inequalities for WW-CC......Page 308
9.6.1 Optimization: An Algorithm for LS-CC......Page 309
9.6.2 Valid Inequalities for LS-CC......Page 312
9.6.3 Extended Formulation for LS-CC......Page 313
9.6.4 R´esum´e of Results......Page 314
9.7.1 Valid Inequalities for WW-C......Page 315
9.7.2 Simple Valid Inequalities for LS-C......Page 317
9.7.3 Submodular Inequalities for LS-C......Page 319
9.7.4 Lifted (l, S) Inequalities for DLSI-C Valid Inequalities for DLSI-C......Page 323
Exercises......Page 325
Notes......Page 326
10 Backlogging and Start-Ups......Page 328
10.2.1 Extreme Points and Optimization......Page 329
10.2.2 Tight Formulations and Inequalities for LS-U-B Valid inequalities......Page 331
10.2.3 Tight Formulations and Inequalities for WW-U-B......Page 333
10.3.1 Discrete Lot-Sizing with Backlogging DLS-CC-B......Page 336
10.3.2 Discrete Lot-Sizing with Initial Stocks and Backlogging......Page 340
10.3.3 Lot-Sizing with Wagner–Whitin Costs and Backlogging......Page 341
10.3.4 Lot-Sizing with Backlogging LS-CC-B The Optimization Problem......Page 343
10.4 Start-Up Costs: The Uncapacitated Case......Page 344
10.4.1 A Dynamic Programming Algorithm for LS-U-SC......Page 345
10.4.2 Tight Formulations and Inequalities for LS-U-SC Valid Inequalities and Convex Hull of X LS-U-SC......Page 346
10.5.1 The Discrete Lot-Sizing Problem DLS-CC-SC......Page 348
10.5.2 Capacitated Lot-Sizing with Start-Up Costs LS-C-SC Valid Inequalities......Page 351
10.5.3 R´esum´e of Results......Page 354
10.6 Backlogging and Start-Ups WW-U-B, SC......Page 355
Exercises......Page 356
Notes......Page 358
11 Single-Item Variants......Page 360
11.1 Sales or Variable Demand (SL)......Page 361
11.1.1 The Uncapacitated Case: Sales and Arbitrary Demands......Page 362
11.1.2 The Uncapacitated Case: Sales and Nonnegative Demands......Page 363
11.2.1 A Wagner–Whitin Relaxation WW-CC-LB......Page 364
11.3.2 Minimum Production Level per Set-Up Sequence (MR)......Page 365
11.4.1 Varying Length Sequences......Page 366
11.4.2 Constant Length Sequences......Page 367
11.5 Piecewise Concave Production Costs (CP)......Page 369
11.6 Production Time Windows (TWP)......Page 370
11.6.1 An Algorithm for WW-U-TWP and Extended Formulation for WW-CC-TWP......Page 371
11.6.2 Indistinguishable Time Windows LS-C-TWP(I)andan Equivalent Problem......Page 373
11.6.3 A Dynamic Programming Algorithm for LS-U-TWP(I)......Page 374
11.6.4 A Tight Extended Formulation for LS-U-TWP(I)......Page 375
11.7.2 Valid Inequalities for LS-U-SUB......Page 376
11.7.3 Valid Inequalities for WW-CC-SUB and WW-CC-B, SUB......Page 377
11.8 Safety Stocks or Piecewise Convex Storage Costs (SS)......Page 378
11.8.1 Mixing Set Relaxations for LS-CC-SS......Page 379
11.9 A Model with Backlogging, Sales Markets, and Concave Production Costs......Page 381
11.10 Stochastic Lot-Sizing on a Tree......Page 383
11.10.1 Mixing Set Relaxations with Constant Capacities......Page 384
Exercises......Page 386
Notes......Page 388
Part IV Multi-Item Lot-Sizing......Page 392
12 Multi-Item Single-Level Problems......Page 394
12.1.1 Production Mode Classi.cation......Page 396
12.1.2 Production Quantity Classi.cation......Page 397
12.2.1 Single Set-Up Constraint: M1......Page 399
12.2.2 Start-Ups and Changeovers M1-{SC, SQ}......Page 401
12.3 Production Modes: Two or More Set-Ups......Page 403
12.3.1 Two Set-Ups: M2......Page 404
12.3.2 Any Number of Set-Ups......Page 405
12.4.1 Product Resource Constraints PC and PC-SU......Page 408
12.5 Family Set-Ups: PC-FAM......Page 411
Exercises......Page 413
Notes......Page 416
13 Multi-Level Lot-Sizing Problems......Page 420
13.1 Production in Series ML-S......Page 422
13.1.1 Optimization for ML-S/LS-U......Page 423
13.1.2 The Echelon Stock Reformulation for ML-S......Page 425
13.1.3 Multi-Commodity Reformulations: Uncapacitated Case......Page 427
13.1.4 Valid Inequalities for ML-S/LS-U......Page 428
13.1.5 Nested Solutions......Page 430
13.2 Assembly Systems......Page 431
13.2.2 Lead-Times and Echelon Stocks......Page 432
13.3 General Systems......Page 434
13.4 Production and Distribution......Page 436
13.4.1 Production Center and Sales Area Aggregation......Page 437
13.4.2 Sales Area Aggregation......Page 439
Exercises......Page 440
Notes......Page 441
Part V Problem Solving......Page 444
14 Test Problems......Page 446
14.1.1 Problem Description General Context......Page 447
14.1.2 Classi.cation......Page 451
14.1.3 Initial Formulation......Page 452
14.1.4 Reformulations and Algorithms......Page 456
14.1.5 Analysis of Capacity and Customer Service Level......Page 459
14.2.1 Problem Description General Context......Page 461
14.2.2 Classi.cation......Page 464
14.2.3 Initial Formulation......Page 465
14.2.4 Improving the Initial Formulation......Page 468
14.2.5 Choosing the Appropriate Extended Reformulations......Page 469
14.2.6 Results with Extended Reformulations......Page 470
14.2.7 Results with Primal Heuristics......Page 471
14.3.1 Problem Description General Context......Page 473
14.3.2 Classi.cation......Page 476
14.3.3 Initial Formulation......Page 477
14.3.4 Improving the Initial Formulation......Page 480
14.3.5 Results with Reformulations......Page 484
14.3.6 The Multi-Period Planning and Scheduling Extension......Page 485
14.4.2 Classi.cation......Page 491
14.4.4 Computational Results with Reformulations......Page 492
14.4.5 Modeling Periods with No Production......Page 493
14.5.1 Classi.cation......Page 495
14.5.2 Initial Formulation......Page 496
14.5.3 Reformulation......Page 497
14.6 Powder Production......Page 498
14.6.2 Initial Formulation......Page 499
14.6.3 Testing the Initial Formulation and Reformulations......Page 500
14.6.5 Finding Upper Bounds for Powder Production......Page 502
Exercises......Page 503
Notes......Page 505
References......Page 508
Index......Page 518
