Deterministic Operations Research

Models and Methods in Linear Optimization

David J. Rader

• Publisher: Wiley
• Year: 2013
• Print ISBN: 9780470484517
• eBook ISBN: 9781118627358
• Edition: 1
• Topic: Mathematics
• Subtopic: Discrete Mathematics
• Index: Mathematics

Uniquely blends mathematical theory and algorithm design for understanding and modeling real-world problems

Optimization modeling and algorithms are key components to problem-solving across various fields of research, from operations research and mathematics to computer science and engineering. Addressing the importance of the algorithm design process. Deterministic Operations Research focuses on the design of solution methods for both continuous and discrete linear optimization problems. The result is a clear-cut resource for understanding three cornerstones of deterministic operations research: modeling real-world problems as linear optimization problem; designing the necessary algorithms to solve these problems; and using mathematical theory to justify algorithmic development.

Treating real-world examples as mathematical problems, the author begins with an introduction to operations research and optimization modeling that includes applications form sports scheduling an the airline industry. Subsequent chapters discuss algorithm design for continuous linear optimization problems, covering topics such as convexity. Farkas' Lemma, and the study of polyhedral before culminating in a discussion of the Simplex Method. The book also addresses linear programming duality theory and its use in algorithm design as well as the Dual Simplex Method. Dantzig-Wolfe decomposition, and a primal-dual interior point algorithm. The final chapters present network optimization and integer programming problems, highlighting various specialized topics including label-correcting algorithms for the shortest path problem, preprocessing and probing in integer programming, lifting of valid inequalities, and branch and cut algorithms.

Concepts and approaches are introduced by outlining examples that demonstrate and motivate theoretical concepts. The accessible presentation of advanced ideas makes core aspects easy to understand and encourages readers to understand how to think about the problem, not just what to think. Relevant historical summaries can be found throughout the book, and each chapter is designed as the continuation of the "story" of how to both model and solve optimization problems by using the specific problems-linear and integer programs-as guides. The book's various examples are accompanied by the appropriate models and calculations, and a related Web site features these models along with Maple™ and MATLAB® content for the discussed calculations.

Thoroughly class-tested to ensure a straightforward, hands-on approach, Deterministic Operations Research is an excellent book for operations research of linear optimization courses at the upper-undergraduate and graduate levels. It also serves as an insightful reference for individuals working in the fields of mathematics, engineering, computer science, and operations research who use and design algorithms to solve problem in their everyday work.

CHAPTER 1

INTRODUCTION TO OPERATIONS RESEARCH

1.1 WHAT IS DETERMINISTIC OPERATIONS RESEARCH?

Today, many “operations” problems are routinely solved throughout business and industry. These include determining work shifts for large departments, designing production facilities to maximize the throughput, allocating scarce resources (such as raw materials and labor) to meet demands at a minimum cost, or determining which investments to place available funds. Such problems are very different from the traditional problems that students of mathematics, science, and engineering often face, because there are no physical laws that can be used; for example, knowing how to use Newton’s second law or Ohm’s law will not help solve these industrial problems. To handle such problems, different mathematical models must be used.

Mathematical Model A mathematical model is a collection of variables and the relationships needed to describe important features of a given problem.

Until World War II, most businesses and industries did not worry about such operations problems. This was partly because no formal mathematical discipline directly handled these problems, and partly because there was no urgent need for them. During World War II, military planners began working with scientists and mathematicians in order to apply a scientific approach to the management of the war effort, in which they began to devise mathematical models to deal with such issues. After the war, others began to look at these techniques for industry, which brought about the beginning of Operations Research.

Operations Research Operations research (OR) is the study of how to form mathematical models of complex science, engineering, industrial, and management problems and how to analyze them using mathematical techniques.

Operations research is the name most often used to describe the mathematical study of such problems. In business, it is also known as Management Science or Operations Management. Typically, OR is divided into two areas: deterministic operations research, where all parameters are fixed, and stochastic operations research, where we assume some of the problem parameters are random. This book deals exclusively with deterministic operations research.

There have been many successful and interesting applications of operations research techniques since the 1940s. In fact, operations research has been used to solve many diverse problems.

1. Scheduling ACC Basketball. Nemhauser and Trick [67] discussed how they used OR techniques to determine successful schedules for the Atlantic Coast Conference basketball season, which consists of a round-robin schedule among 10 teams stretching from Maryland to Florida.

2. Designing Communication Networks. Balakrishnan, Magnanti, and Mirchandani [4] look at the problem of designing survivable networks with high bandwidth in order to minimize costs. These problems have great importance due to the explosion of phone, cable, and video services.

3. Scheduled Aircraft Maintenance. Gopalan and Talluri [51] studied how to schedule aircraft maintenance when there are many operating restrictions in place, such as making sure the aircraft is at the correct maintenance location within a certain amount of time.

4. Truck Dispatching for Oil Pickup. Bixby and Lee [16] look at the vehicle routing and scheduling problem that arise from an oil company’s desire to better utilize truck fleets and drivers.

5. Component Assignment in Printed Circuit Board Manufacturing. Hillier and Brandeau [58] consider the problem of determining the minimum cost assignment of various components to insertion machines that are used in the automated assembly of printed circuit boards.

OR is much more than the formation of mathematical models of problems; it also deals with the solution of these models and the evaluation of their solutions with regard to the real-world problem. In deterministic OR models, we typically formulate the problem as an optimization problem, where we want to minimize or maximize a function (such as costs, profits, time, etc.) given that the solution must satisfy certain restrictions and requirements (demand met, scarce resources, etc.). Such optimization problems are often referred to as Mathematical Programs.

Mathematical Program A mathematical program or Optimization Model is a mathematical structure where problem choices are represented by decision variables. Using these decision variables, mathematical programs look to optimize some objective function of the decision variables subject to certain constraints that limit the possible choices (values of decision variables). It can be written in the most general form (assuming maximization problem)

where x is a vector of decision variables, f (x) is the objective function, and the set S is the set of values for the decision variables satisfying all of the constraints.

The three highlighted terms in the above definition, decision variables, objective function, and constraints, represent the fundamental concerns of any OR model. In fact, it is the objective function that makes a model an optimization model. This was fairly revolutionary in 1947, when George Dantzig used an objective function to determine which decisions were better than others. Before that, there was not much thought given in modeling toward objective functions; instead, basic ground rules given by those in authority were used to guide the search for the “best answer.”¹

But how do we create a mathematical model? That is the real question in any study of operations research. The whole modeling process involves a four-stage cycle:

1. Problem Definition and Data Gathering. Here is where the real work begins. Actually knowing what problem we wish to model is more important than most people realize. If we have no idea what we want to determine, how do we know if we have a reasonable solution or not? Next, a modeler must observe the system and collect data to estimate any parameters of the model.

2. Creating the Mathematical Model. Once the problem is defined and data have been collected, it is now time to develop a model of the situation. This involves determining decision variables, constraints, and objectives that are needed in the problem. Sometimes it involves only determining which formula we need to use. Models can be either deterministic, as studied in this book, or stochastic, in which case our data are more important because we need them to verify assumptions on probability distributions, means, and so on.

3. Solving the Mathematical Model. This can have many different forms. If we have a deterministic optimization model, we try to find the values of the decision variables that give the best objective function value. Sometimes, however, this is not tractable. For example, in the infamous traveling salesperson problem, a person has to travel to many different locations and wants to determine the shortest route to visit them all before returning home. For many instances, this problem cannot be solved to optimality. In that case, when a problem is that difficult or intractable, operations researchers often try to develop heuristics that find a reasonable solution in a short amount of time. For stochastic problems, a “solution” is not always easy to find. In many instances, simulation is used to approximate a good solution. Here, we simulate the system many times by generating random numbers for each random variable and determine from these simulations which alternative is best.

4. Using the Mathematical Model to Make Real-World Predictions. Once we have a solution to a mathematical model, we must use that answer to solve the real-world problem. While it is often the case that the values of our decision variables are what we will use, that is not always the case. For example, if we solve a mathematical program and get fractional values, and we wanted an integral solution, we may want to “fudge” the values a little, perhaps by rounding up or down, to get integers. However, this is not always a good idea, because we may end up with a solution that does not satisfy all the constraints.

Once we’ve gone through these four steps, we are done, right? Not quite. Often the model gives answers that we know cannot work in the real problem, which means the model is not quite right. In this case, we may have to start all over again. Mathematical modeling is a very cyclical process, as illustrated in Figure 1.1.

Even when the model seems correct, we are often interested in scenarios where our parameters change. These “What If” scenarios are important, because often our data do not generate the absolutely correct parameters. Therefore, we want to know what small changes to our parameters do to our solutions.

Sensitivity Analysis Sensitivity analysis is the determination of the effect of small changes of parameter values on the solutions to a mathematical model.

FIGURE 1.1 Cyclical nature of mathematical modeling.

Sometimes this is very easy to do, and sometimes it is not. For one important model we’ll study, sensitivity analysis is both straightforward and informative.

In this book we deal with three important parts of operations research: finding a mathematical model, solving it, and analyzing the results obtained and the solution technique itself. To do this, we first spend time on obtaining models, including some common models found in OR applications. This includes doing sensitivity analysis on certain models and ...

Table of contents

• Cover
• Contents
• Title Page
• Copyright
• Dedication
• Preface
• CHAPTER 1: INTRODUCTION TO OPERATIONS RESEARCH
• CHAPTER 2: LINEAR PROGRAMMING MODELING
• CHAPTER 3: INTEGER AND COMBINATORIAL MODELS
• CHAPTER 4: REAL-WORLD OPERATIONS RESEARCH APPLICATIONS: AN INTRODUCTION
• CHAPTER 5: INTRODUCTION TO ALGORITHM DESIGN
• CHAPTER 6: IMPROVING SEARCH ALGORITHMS AND CONVEXITY
• CHAPTER 7: GEOMETRY AND ALGEBRA OF LINEAR PROGRAMS
• CHAPTER 8: SOLVING LINEAR PROGRAMS: SIMPLEX METHOD
• CHAPTER 9: LINEAR PROGRAMMING DUALITY
• CHAPTER 10: SENSITIVITY ANALYSIS OF LINEAR PROGRAMS
• CHAPTER 11: ALGORITHMIC APPLICATIONS OF DUALITY
• CHAPTER 12: NETWORK OPTIMIZATION ALGORITHMS
• CHAPTER 13: INTRODUCTION TO INTEGER PROGRAMMING
• CHAPTER 14: SOLVING INTEGER PROGRAMS: EXACT METHODS
• CHAPTER 15: SOLVING INTEGER PROGRAMS: MODERN HEURISTIC TECHNIQUES
• APPENDIX A BACKGROUND REVIEW
• REFERENCES
• INDEX