Chapter 3. Fundamentals of Optimization Models: Linear Programming

Part II:

Models

In Part I, we discussed the central role of descriptive and optimization models in supporting supply chain decision making. In this part, we provide details about how these models are constructed and solved. This part includes five chapters:

Chapter 4. Fundamentals of Optimization Models: Mixed-Integer Programming

Chapter 5. Unified Optimization Methodology for Operational Planning Problems

Chapter 6. Overview of Descriptive Models

Chapter 7. Supply Chain Decision Databases

In these chapters, greater attention is paid to optimization models and methods than descriptive models and methods, although both are equally important. This emphasis is due to several reasons. First, optimization models can provide managers with penetrating analysis of the company’s decision options, goals, commitments, and resource constraints. Second, they can provide a rich and robust framework for merging data, relationships, projections, and forecasts from descriptive models.

Moreover, the fundamentals of optimization models for supply chain planning can be presented in a compact manner. In particular, we explore linear programming (LP) models in Chapter 3 and their extensions to mixed-integer programming (MIP) models in Chapter 4. In Chapter 5, we extend the scope of MIP models for operational planning by presenting a unified optimization methodology that combines model decomposition methods with heuristics. We note that the same modeling techniques and algorithms discussed here have been applied to decision problems arising in investment banking, engineering design, and many other areas.

By contrast, descriptive models are very broad in the methodologies they employ, which include statistics, data mining, management accounting, deterministic and Monte Carlo simulation, and others. It would not be possible to provide an in-depth presentation of all these methodologies in one book. Instead we study an overview of important, illustrative descriptive models in Chapter 6, including forecasting, simulation, and activity-based costing.

Finally, the focus on optimization models is motivated by the belief that decision makers should possess knowledge about their form and function if they are to be used to their full advantage. Much of this book could have been written from the perspective that the analytical engines of optimization modeling systems are “black boxes,” which only specialists need to comprehend. We reject such an approach because it fosters an unnecessary and sometimes dangerous lack of understanding by managers seeking to use models to improve their decision making. If they have little or no knowledge about how details of a model represent decision problems, managers might be unwilling to trust its results or be too willing to blindly trust them.

Still, having committed us to study details of optimization model construction and solution, I wish to reassure you that we are not about to embark on mathematical developments that require graduate training in operations research. Rather, only mathematical constructions taught in high school are used. Although this means that we are restricted to small models that do not convey the richness of larger models for complex problems, a comprehensive knowledge of the fundamentals can be conveyed. Moreover, without going into excessive detail, later chapters describe how large-scale models are constructed by synthesizing smaller, simpler submodels of the types discussed in this chapter and the next.

In Chapter 7, we examine the supply chain decision database that contains the inputs for supply chain optimization models. The tables in this database serve as templates for populating optimization models with data determined by descriptive models and other data input methods. The supply chain decision database also contains optimization model outputs that are combined with the inputs in creating managerial reports and graphical displays of supply chain decisions determined by the models.

Chapter Four:

Fundamentals of

Optimization Models:

Mixed-Integer Programming

Mixed-integer programming (MIP) models are generalizations of linear programming (LP) models in which some variables, called integer variables, are constrained to take on nonnegative integer values, whereas the remaining variables, called continuous variables, are allowed to take on any nonnegative values. The most frequently occurring integer variables are 0-1, or binary variables, which are constrained to take on values of 0 or 1. Such variables are used to describe cost relationships, constraints, and logical conditions that cannot be captured by linear programming. As we demonstrate shortly, MIP constructions overcome many of the limitations of LP models discussed in the previous chapter.

Zero-one variables are employed in different ways in models that address operational, tactical, and strategic supply chain planning problems. For operational problems, they are used to model sequencing and routing decisions associated with the scheduling of machines, vehicles, or people. For tactical problems, they are used to model fixed costs, economies of scale, and a variety of nonnumeric, or logical, policy restrictions such as sole sourcing of markets. For strategic problems, they are used to model the timing, sizing, phasing, and location of investment options.

MIP models and methods provide a rigorous approach to supply chain analysis. The models accurately capture the important decision options, constraints, and objectives of a supply chain problem. The methods are capable of finding demonstrably good solutions to these models and can yield optimal solutions if the decision maker is willing to wait long enough for the algorithms to identify them.

The greater realism of MIP models is not achieved without a cost. In the appendix to this chapter, we discuss the branch-and-bound method for optimizing MIP as a sequence of LP approximations. The number of approximations that must be solved to optimize a given MIP model can grow exponentially with the number of integer variables in the model. Thus, the modeler must use MIP constructs sparingly in balancing the need and desire for realism against the burdens of computation.

Researchers are continuing to devise new and improved approaches for solving MIP models. In recent years, heuristic methods that generate trial solutions to these models or the decision problems underlying them have shown promise for some classes of models and problems. Heuristic methods use problem-specific or general-purpose procedures to search the discrete space of possible solutions. Heuristics sometimes have been oversold. An accurate view of their merit is that heuristics play a complementary role to rigorous MIP modeling and optimization methods. In Chapter 5, we develop a unified optimization methodology for advanced planning and scheduling that exploits this complementarity.

Our discussion of mixed-integer programming begins in Section 4.1 with modeling vignettes illustrating how 0-1 variables and constraints can capture phenomena such as fixed costs, economies of scale, and production changeovers. In Section 4.2, we use mixed-integer programming to model and optimize the problem of locating distribution centers (DCs) in the supply chain network of a distribution company. In so doing, we describe how Solver and What’s Best treat MIP variables and constraints. In Section 4.3, we use mixed-integer programming to model and optimize a variety of strategic supply chain options faced by a manufacturing company.

We continue the chapter with two sections in which we examine issues arising in the implementation of modeling systems based on linear and mixed-integer programming. In Section 4.4, we discuss design principles for modeling systems to analyze strategic and tactical supply chain problems. MIP models and modeling systems for vehicle routing, production scheduling, and other operational planning problems are presented in Chapter 5. A survey of off-the-shelf optimization software is provided in Section 4.5. The chapter concludes with final thoughts in Section 4.6. The branch-and-bound method for mixed-integer programming is presented in Appendix 4A.