Integer Linear Programming PDF

Chapter 15 Integer Linear Programming 15.1 Types of Integer Linear Programming Models Fixed Cost Distribution System Design 15.2 Graphical and Computer Solutions for an...

Chapter 15 Integer Linear Programming 15.1 Types of Integer Linear Programming Models Fixed Cost Distribution System Design 15.2 Graphical and Computer Solutions for an Planning Location All-Integer Linear Programme Graphical Solution of the LP Relaxation 15.4 Modelling Flexibility Provided by 021 Integer Rounding to Obtain an Integer Solution Variables Graphical Solution of the All-Integer Problem Multiple-Choice and Mutually Exclusive Using the LP Relaxation to Establish Bounds Constraints Computer Solution k Out of n Alternatives Constraint Branch and Bound Solution Conditional and Corequisite Constraints A Cautionary Note About Sensitivity 15.3 Applications Involving 021 Variables Analysis Capital Budgeting Learning objectives By the end of this chapter you will be able to: Formulate integer linear programming problems Interpret the solution to integer linear programming problems Explain the !exibility provided by 0–1 integer variables Use 0–1 integer variables in a number of typical modelling situations 1 For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 2 CHAPTER 15 INTEGER LINEAR PROGRAMMING In this chapter we discuss a class of problems that are modelled as linear programmes! with the additional requirement that one or more variables must be integer. Such problems are called integer linear programmes. If all vari- ables must! be integer, we have an all-integer linear programme (ILP). If some, but not all, variables must be integer, we have a mixed-integer linear programme (MILP).! In! many applications of integer linear programming, one or more inte- ger variables are! required to equal either 0 or 1. Such variables are called 0–1 or binary variables.!If all variables are 0–1 variables, we have a 021 integer linear programme. Integer variables 2 especially 0–1 variables 2 provide substantial modelling "ex- ibility. As a result, the number of applications that can be addressed with linear programming methodology is expanded. For instance, the Management Science in Action, Crew Scheduling at Air New Zealand, describes how that airline company employs 0–1 integer programming models to schedule its pilots and "ight atten- dants. Many other applications of integer programming are described throughout the chapter. The objective of this chapter is to provide an applications-oriented introduction to integer linear programming. First, we discuss the different types of integer linear pro- gramming models. Then we show the formulation, graphical solution and computer solution of an all-integer linear programme. In Section 15.3, we discuss typical applica- tions of integer linear programming that make use of 0–1 variables: capital budgeting, #xed cost, distribution system design, location planning and market share optimization problems. In Section 15.4, we provide additional illustrations of the modelling "exibility provided by 0–1 variables. A chapter appendix illustrates the use of Excel for solving integer programmes. The cost of the added modelling "exibility provided by integer programming is that problems involving integer variables are often much more dif#cult to solve. A linear programming problem with several thousand continuous variables can be solved with a number of commercial linear programming solvers. However, an all-integer linear pro- gramming problem with less than 100 variables can be extremely dif#cult to solve. Expe- rienced management scientists can help identify the types of integer linear programmes that are easy, or at least reasonable, to solve. Commercial computer software packages, such as MPSX-MIP ®, OSL ®, CPLEX ® and LINDO, have extensive integer program- ming capability. Spreadsheet packages, such as Excel, have the capability for solving smaller integer linear programmes. 15.1 Types of Integer Linear Programming Models The only difference between the problems studied in this chapter and the ones studied in earlier chapters on linear programming is that one or more variables are required to be integer. If all variables are required to be integer, we have an all- integer linear programme. The following is a two-variable, all-integer linear pro- gramming model: Max 2x1 1 3x2 s.t. 3x1 1 3x2 # 12 2 y3 x1 1 1x2 # 4 1x1 1 2x2 # 6 x1, x2 $ 0 and integer For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  TYPES OF INTEGER LINEAR PROGRAMMING MODELS 3 MANAGEMENT SCIENCE IN ACTION Crew Scheduling at Air New Zealand A ir New Zealand is the largest national and inter- national airline based in New Zealand. Over a 15-year period, Air New Zealand developed integer objective is to minimize total cost. Air New Zealand solves a separate ToD problem for each crew type (pilot type or flight attendant type). programming models for crew scheduling. In the rostering problem, the tours of duty from Air New Zealand finalizes flight schedules at least the solution to the ToD problem are used to con- 12 weeks in advance of when the flights are to take struct lines of work (LoW) for each crew member. place. At that point the process of assigning crews In the integer programming model of the rostering to implement the flight schedule begins. The crew- problem, a 0–1 variable represents the possible scheduling problem involves staffing the flight sched- LoWs for each crew member. A separate constraint ule with pilots and flight attendants. It is solved in for each crew member guarantees that each will two phases. In the first phase, tours of duty (ToD) are be assigned a single LoW. Other constraints cor- generated that will permit constructing sequences respond to the ToDs that must be covered by any of flights for pilots and flight attendants that will al- feasible solution to the rostering problem. low the airline’s flight schedule to be implemented. A The crew-scheduling optimizers developed by tour of duty is a one-day or multiday alternating se- Air New Zealand showed a significant impact on quence of duty periods (flight legs, training, etc.) and profitability. Over the 15 years it took to develop rest periods (layovers). In the ToD problem, no con- these systems, the estimated development costs sideration is given to which individual crew members were approximately NZ$2million. The estimated will perform the tours of duty. In the second phase, savings are NZ$15.6 million per year. In 1999 the individual crew members are assigned to the tours savings from employing these integer program- of duty, which is called the rostering problem. ming models represented 11 per cent of Air New Air New Zealand employs integer programming Zealand’s net operating profit. In addition to the models to solve both the ToD problem and the ros- direct dollar savings, the optimization systems tering problem. In the integer programming model of provided many intangible benefits such as higher- the ToD problem, each variable is a 0–1 variable that quality solutions in less time, less dependence on a corresponds to a possible tour of duty that could be small number of highly skilled schedulers, flexibility flown by a crew member (e.g., pilot or flight atten- to accommodate small changes in the schedule, dant). Each constraint corresponds to a particular and a guarantee that the airline satisfies legislative flight and ensures that the flight is included in ex- and contractual rules. actly one tour of duty. The cost of variable j reflects Reference: E. Rod Butchers et al., 2001. ‘Optimized Crew Scheduling at the cost of operating the jth tour of duty, and the Air New Zealand’, Interfaces (January/February): 30256. If we drop the phrase ‘and integer’ from the last line of this model, we have the familiar two-variable linear programme. The linear programme that results from dropping the integer requirements is called the LP Relaxation of the integer linear programme. If some, but not necessarily all, variables are required to be integer, we have a mixed- integer linear programme. The following is a two-variable, mixed-integer linear programme: Max 3x1 1 4x2 s.t. 21x1 1 2x2 # 8 1x1 1 2x2 # 12 2x1 1 1x2 # 16 x1, x2 $ 0 and x2 integer For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 4 CHAPTER 15 INTEGER LINEAR PROGRAMMING We obtain the LP Relaxation of this mixed-integer linear programme by dropping the requirement that x2 be integer. In some applications, the integer variables may only take on the values 0 or 1. Then we have a 0–1 linear integer programme. As we see later in the chapter, 0–1 variables provide additional modelling capability. Graphical and Computer Solutions for an All-Integer Linear 15.2 Programme As usual, we will use an example to illustrate the issues and approaches. Eastborne Property is a UK-based company that specializes in purchasing residential property in Spain and Italy which is then rented out to holidaymakers. Eastborne currently has $2 million available for the purchase of new rental property. After an initial screening, Eastborne reduced the invest- ment alternatives to townhouses and apartment buildings. Each townhouse can be purchased for $282 000, and #ve are available. Each apartment building can be purchased for $400 000, and the developer will construct as many buildings as Eastborne wants to purchase. Eastborne’s property manager can devote up to 140 hours per month to these new properties in terms of marketing, managing and responding to enquiries; each town- house is expected to require 4 hours per month, and each apartment building is expected to require 40 hours per month. The annual cash "ow, after deducting mortgage pay- ments and operating expenses, is estimated to be $10 000 per townhouse and $15 000 per apartment building. Eastborne would like to determine the number of townhouses and the number of apartment buildings to purchase to maximize annual cash "ow. We begin by de#ning the decision variables as follows: T 5 number of townhouses A 5 number of apartment buildings The objective function for cash "ow ($1000s) is: Max 10T 1 15A Three constraints must be satis#ed: 282T 1 400A # 2000 Funds available (!1000s) 4T 1 40A # 140 Manager’s time (hours) T # 5 Townhouses available The variables T and A must be nonnegative. In addition, the purchase of a fractional num- ber of townhouses and/or a fractional number of apartment buildings is unacceptable 2 it’s not possible to buy part of a property. So, T and A must be integer. The model for the Eastborne problem is the following all-integer linear programme. Max 10T 1 15A s.t. 282T 1 400A # 2000 4T 1 40A # 140 T # 5 T, A $ 0 and integer Graphical Solution of the LP Relaxation Suppose that to begin with we drop the integer requirements for T and A and solve the LP Relaxation of the Eastborne problem. Using the graphical solution procedure, For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  GRAPHICAL AND COMPUTER SOLUTIONS FOR AN ALL-INTEGER LINEAR PROGRAMME 5 as presented in Chapter 2, the optimal linear programming solution is shown in Fig- ure 15.1. It is T 5 2.479 townhouses and A 5 3.252 apartment buildings. The optimal value of the objective function is 73.574, which indicates an annual cash "ow of $73 574. However, Eastborne cannot purchase fractional numbers of townhouses and apartment buildings; further analysis is necessary. Figure 15.1 Graphical Solution to the LP Relaxation of the Eastborne Problem A 6 5 Manager’s Time Number of Apartment Buildings Constraint 4 Optimal LP Relaxation Solution T = 2.479, A = 3.252 3 Ob jec 2 tiv eF un Feasible Region Available cti on Funds Constraint = 73.57 1 4 Townhouse Availability Constraint T 0 1 2 3 4 5 6 Number of Townhouses Rounding to Obtain an Integer Solution In many cases, a noninteger solution can be rounded to obtain an acceptable integer solution. For instance, a linear programming solution to a production scheduling problem might call for the production of 15 132.4 cases of breakfast cereal. The rounded integer solution of 15 132 cases would probably have minimal impact on the value of the objective function and the feasibility of the solution. Rounding would be a sensible approach. Indeed, whenever rounding has a minimal impact on the objective function and constraints, most managers #nd it acceptable. A near-optimal solution is #ne. However, rounding may not always be a good strategy. When the decision variables take on small values that have a major impact on the value of the objective function or feasibility, an optimal integer solution is needed. Let us return to the Eastborne prob- lem and examine the impact of rounding. The optimal solution to the LP Relaxation for Eastborne resulted in T 5 2.479 townhouses and A 5 3.252 apartment buildings. Because each townhouse costs $282 000 and each apartment building costs $400 000, rounding to an integer solution can be expected to have a signi#cant economic impact on the problem. For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 6 CHAPTER 15 INTEGER LINEAR PROGRAMMING Suppose that we round the solution to the LP Relaxation to obtain the integer so- lution T 5 2 and A 5 3, with an objective function value of 10(2) 1 15(3) 5 65. The annual cash "ow of $65 000 is substantially less than the annual cash "ow of $73 574 provided by the solution to the LP Relaxation. Do other rounding possibilities exist? Exploring other rounding alternatives shows that the integer solution T 5 3 and A 5!3 is infeasible because it requires more funds than the $2 000 000 Eastborne has avail- able. The rounded solution of T 5 2 and A 5 4 is also infeasible for the same reason. At this point, rounding has led to two townhouses and three apartment buildings with an annual cash "ow of $65 000 as the best feasible integer solution to the problem. Unfortunately, we don’t know whether this solution is the best integer solution to the If a problem has only problem. less-than-or-equal-to Rounding to an integer solution is a trial-and-error approach. Each rounded solution constraints with positive coefficients for the must be evaluated for feasibility as well as for its impact on the value of the objective variables, rounding down function. Even in cases where a rounded solution is feasible, we do not have a guarantee will always provide a that we have found the optimal integer solution. We will see shortly that the rounded feasible integer solution. solution (T 5 2 and A 5 3) is not optimal for Eastborne. Graphical Solution of the All-Integer Problem Figure 15.2 shows the changes in the linear programming graphical solution procedure required to solve the Eastborne integer linear programming problem. First, the graph of the feasible region is drawn exactly as in the LP Relaxation of the problem. Then, because the optimal solution must have integer values, we identify the feasible integer solutions with the dots shown in Figure 15.2. Finally, instead Figure 15.2 Graphical Solution of the Eastborne Integer Problem A 6 5 Manager’s Time Number of Apartment Buildings Note: Dots show the location of Constraint feasible integer solutions 4 Available Funds Constraint 3 Optimal Integer Solution T = 4, A = 2 2 Feasible Region Ob jec tiv eF 1 un cti on Townhouse = 70 Availability Constraint T 1 2 3 4 5 6 Number of Townhouses For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  GRAPHICAL AND COMPUTER SOLUTIONS FOR AN ALL-INTEGER LINEAR PROGRAMME 7 of moving the objective function line to the best extreme point in the feasible re- gion, we move it in an improving direction as far as possible until reaching the dot (feasible integer point) providing the best value for the objective function. View- ing Figure! 15.2, we see that the optimal integer solution occurs at T 5 4 town- houses! and! A 5 2 apartment buildings. The objective function value is 10(4) 1 15(2)! 5 70 providing an annual cash "ow of $70 000. This solution is signi#cantly Try Problem 1 for practice with the better than the best solution found by rounding: T 5 2, A 5 3 with an annual cash graphical solution of an "ow of $65 000. Thus, we see that rounding would not have been the best strategy integer programme. for Eastborne. Using the LP Relaxation to Establish Bounds An important observation can be made from the analysis of the Eastborne problem. It has to do with the relationship between the value of the optimal integer solution and the value of the optimal solution to the LP Relaxation. For integer linear programmes involving maximization, the value of the optimal solution to the LP Relaxation provides an upper bound on the value of the op- timal integer solution. For integer linear programmes involving minimization, the value of the optimal solution to the LP Relaxation provides a lower bound on the value of the optimal integer solution. This observation is valid for the Eastborne problem. The value of the optimal integer solution is $70 000, and the value of the optimal solution to the LP Relaxation is $73 574. Thus, we know from the LP Relaxation solution that the upper bound for the value of the objective function is $73 574. The bounding property of the LP Relaxation allows us to conclude that if, by chance, the solution to an LP Relaxation turns out to be an integer solution, it is also optimal for the integer linear programme. This bounding property can also be helpful in determin- ing whether a rounded solution is ‘good enough’. If a rounded LP Relaxation solution is feasible and provides a value of the objective function that is ‘almost as good as’ the Try Problem 3 for the graphical solution value of the objective function for the LP Relaxation, we know the rounded solution is a of a mixed-integer near-optimal integer solution. In this case, we can avoid having to solve the problem as programme. an integer linear programme. Computer Solution As mentioned earlier, commercial software packages that can solve integer linear pro- grammes are widely available. Generally, these packages are reliable for problems having up to approximately 100 integer variables and may be used to solve specially structured problems with several thousand integer variables. We shall illustrate with the Excel solution to the Eastborne problem, shown in Figure 15.3 (Appendix 15.1 shows in detail how to use Excel to solve these types of problems). From the Excel Answer Report we see that the optimal solution gives an objective function value of $70 000 with 4 townhouses and 2 apartments. We also see that the two binding constraints are the requirements that the two decision variables be integer. The other three constraints are nonbinding indicating that we are using less than the $2 000 000 of funding available; we require less than the 140 hours of manager’s time available and we do not need all the 5 townhouses available. The solu- tion of T 5 4 townhouses and A 5 2 apartment buildings has a maximum annual cash "ow of $70 000. The values of the slack variables tell us that the optimal solution has $72 000 of available funds unused, 44 hours of the manager’s time still available, and 1 of the available townhouses not purchased. For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 8 CHAPTER 15 INTEGER LINEAR PROGRAMMING Figure 15.3 Excel Solution for the Eastborne Problem EXCEL !le EASTBORNE NOTES AND COMMENTS 1 Because integer linear programmes are harder the variables will have integer values. The to solve than linear programmes, one should not assignment, transportation and transshipment try to solve a problem as an integer programme problems of Chapter 7 have such structures. If if simply rounding the linear programming the supply and the demand for transportation solution is adequate. In many linear programming and transshipment problems are integer, problems, such as those in previous chapters, the optimal linear programming solution rounding has little economic consequence on the will provide integer amounts shipped. For objective function, and feasibility is not an issue. the assignment problem, the optimal linear But, in problems such as determining how many programming solution will consist of 0s jet engines to manufacture, the consequences and 1s. So, for these specially structured of rounding can be substantial and integer problems, linear programming methodology programming methodology should be employed. can be used to find optimal integer solutions. 2 Some linear programming problems have Integer linear programming algorithms are not a special structure, which guarantees that necessary. Branch and Bound Solution Clearly, the graphical solution method is only helpful for small problems. Whilst we can rely on a computer software solution, we clearly have no idea how this solution has been obtained. In this section we provide an understanding of one solution method for integer linear programmes, the branch and bound method (there are other solution methods available). Branch and bound methods belong to the family of ‘tree search’ For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  GRAPHICAL AND COMPUTER SOLUTIONS FOR AN ALL-INTEGER LINEAR PROGRAMME 9 algorithms and can be applied to a very broad class of problems which includes ILP as a large and important subset. In general they demand very little elaboration of the theory of linear programming, requiring only that the problem-solver has the means to solve considerable numbers of LP models in an acceptably short time. All methods of the branch and bound type exploit the fact that the set of feasible solutions to the prob- lem can be represented as a ‘tree’ structure in which each new ‘branch’ corresponds The branch and bound method was first to the restriction of a particular decision variable to a speci#ed subset of values. The proposed by A. H. Land manner in which the tree is constructed is determined by rules governing the calcula- and A. G. Doig in 1960. tion and use of ‘bounds’. Starting the Tree To illustrate how the method works, we will return to the Eastborne problem. Max 10T 1 15A subject to: 282T 1 400A # 2000 4T 1 40A # 140 T # 5 T, A $ 0 and integer First, we solve the problem using the LP Relaxation giving: T 5 2.479, A 5 3.252 and a value for the objective function (Z) of 73.574. Solving the problem in the absence of the integer requirement provides a starting point for the branch and bound method. We now represent this solution as a circular node, I, as shown: I T = 2.479 A = 3.252 Z = 73.574 Calculating a Bound We show the values of the variables inside the node and have added the value of the objective function. The value of Z will play a crucial role in the progress of the algorithm guiding us to ‘grow’ and explore appropriate branches. It is Z, in fact, that provides the ‘bound’ that gives the method its title. The value of 73.573 is the best we can achieve even with the removal of the integer conditions on the variables. It is therefore an upper bound on the value achievable by Z in the ILP problem. It is evident that no additional restriction applied to a problem can ever result in an improved optimal solution, and the required integer conditions are such additional restrictions. We infer, therefore, that whatever the optimal ILP solution may be, its objective function value cannot exceed 73.574. The Branching Process We next inspect the current values of the decision vari- ables themselves. They are at present non-integer and so inappropriate for our prob- lem. Had they been integer, of course, then our task would be complete already and we could conclude that the optimal LP solution was already optimal for the ILP. We now take a decision variable with a non-integer value (here we will arbitrarily choose A) For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 10 CHAPTER 15 INTEGER LINEAR PROGRAMMING and we partition the set of feasible ILP solutions into two subsets, one containing points for which: A#3 and one for which: A$4 Clearly, since A cannot lie between consecutive integer values, one or other (but not both) of these conditions must apply to the optimal ILP solution which is therefore certain to belong to just one of the subsets we have just de!ned. We represent these two possibilities as branches on the tree: I T = 2.479 A = 3.252 Z = 73.574 A≤3 A≥4 II III T= T= A= A= Z= Z= What we have effectively done is to say that from the original solution there are two possible branches: one where A takes a value of no more than 3 and one where A takes a value of at least 4 (the two integers either side of the current A value of 3.252). The integer solution to the problem that we seek must be down one of these two branches. Effectively, Nodes II and III now represent two amended formulations: Node!II Max 10T 1 15A subject to: 282T 1 400A # 2000 4T 1 40A # 140 T# 5 and A # 3 T, A $ 0 Node!III Max 10T 1 15A subject to: 282T 1 400A # 2000 4T 1 40A # 140 T # 5 and A $ 4 T, A $ 0 For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  GRAPHICAL AND COMPUTER SOLUTIONS FOR AN ALL-INTEGER LINEAR PROGRAMME 11 Using standard LP, we can easily solve each of these two problems and the solutions are shown below. Node II shows that with the extra constraint, A # 3, T takes a value 2.837 and A of 3 giving a Z value of 73.369. Note that the Z value, as it must be, is not higher than that shown in Node I. In fact it is slightly lower. Node III, on the other hand, is infeasible. If we require A $ 4 we see that there is no feasible solu- tion. We can con!rm this by looking at Figure 15.1 where see that A $ 4 is outside the feasible area: I T = 2.479 A = 3.252 Z = 73.574 A≤3 A≥4 II III T = 2.837 Infeasible A=3 Z = 73.369 So, we know that our all-integer solution lies along the branch of Node II. The process now repeats. We form two new branches: one where we add a further constraint on the non-integer variable that T # 2 and one where we add a further constraint that T $ 3. We solve each of these branches again as a straightforward LP problem. The results are shown below: I T = 2.479 A = 3.252 Z = 73.574 A≤3 A≥4 II III T = 2.837 Infeasible A=3 Z = 73.369 T≤2 T≥3 IV V T=2 T=3 A=3 A = 2.885 Z = 65.0 Z = 73.275 For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 12 CHAPTER 15 INTEGER LINEAR PROGRAMMING Node IV gives an integer solution for both variables with a Z value of 65.0. Clearly there is no point branching any further down this part of the tree since we have reached our goal of !nding an integer solution (although we do not yet know whether this solution, although integer, is optimal). Node V gives T as integer at 3 but with A 5 2.885. Note also that the Z value of Node V is lower than that of Node II. The more constraints we add, the lower the objective function value is likely to be. However, it is clear that further branching from Node V is possible since the solution is not all integer. Now we have two branches for A # 2 and A 5 3 (note that we cannot write as we have done previously, A!$ 3, since earlier from Node I we have already constrained A to be no greater than 3. The two new solutions are now shown: I T = 2.479 A = 3.252 Z = 73.574 A≤3 A≥4 II III T = 2.837 Infeasible A=3 Z = 73.369 T≤2 T≥3 IV V T=2 T=3 A=3 A = 2.885 Z = 65.0 Z = 73.275 A≤2 A=3 VI VII T = 4.255 Infeasible A=2 Z = 72.553 We see that Node VII gives an infeasible solution while Node VI is still non-integer. Continuing the branching from Node VI we now get the solution shown below. Node VIII provides another integer solution with T 5 4, A 5 2 and Z 5 70 whilst Node IX remains non-integer. So, we branch again from Node IX. We have now completed the tree. All nodes show either an integer solution or have been deemed as infeasible. Determining the optimal integer solution is now straight- forward: we simply identify the integer solution with the largest objective function value. This is Node VIII with Z 5 70.0, T 5 4 and A 5 2. The branch and bound method may seem like a lot of work but it is ideally suited for a computer solution which is why much of the commercial computer software uses this approach as the solution method. For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  APPLICATIONS INVOLVING 0–1 VARIABLES 13 I T = 2.479 A = 3.252 Z = 73.574 A≤3 A≥4 II III T = 2.837 Infeasible A=3 Z = 73.369 T≤2 T≥3 IV V T=2 T=3 A=3 A = 2.885 Z = 65.0 Z = 73.275 A≤3 A=3 VI VII T = 4.255 Infeasible A=2 Z = 72.553 T≤4 T≥5 VIII IX T=4 T=5 A=2 A = 1.475 Z = 70 Z = 72.125 15.3 Applications Involving 0–1 Variables So far, we have looked at problems where we require some, or all, of the decision vari- ables to take integer values. Apart from that, there does not seem to be much difference between integer programming and LP. However, we now introduce 021 or binary vari- ables and we shall see that much of the usefulness of integer programming comes from the "exibility that such variables provide in terms of business modelling. Binary variables are typically used where there is an either/or choice for the decision maker and there are then different subsequent decisions to be taken. Should we build a new factory or not? Should we launch a new product or not? When we specify that these decision variables are binary variables effectively we are restricting their possible values to either 0 or 1 where 1 typically represents a ‘yes’ decision (yes, we’ll build the new factory; yes, we’ll launch the new product) and 0 represents ‘no’. As we shall see, such "exibility to model this type of decision proves very useful and is something that LP itself cannot do. We shall explore the use of binary variables by looking at a number of common areas of business application: For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 14 CHAPTER 15 INTEGER LINEAR PROGRAMMING capital budgeting; !xed cost problems; distribution system design; location planning. Not all binary decision problems will fall into these categories but many do. I T = 2.479 A = 3.252 Z = 73.574 A≤3 A≥4 II III T = 2.837 Infeasible A=3 Z = 73.369 T≤2 T≥3 IV V T=2 T=3 A=3 A = 2.885 Z = 65.0 Z = 73.275 A≤2 A≥3 VI VII T = 4.255 Infeasible A=2 Z = 72.553 T≤4 T≥5 VIII IX T=4 T=5 A=2 A = 1.475 Z = 70 Z = 72.125 A≤1 A=2 X XI T=5 Infeasible A=1 Z = 65.0 Capital Budgeting The Ice-Cold Refrigerator Company (ICRC) in Greece is considering investing in sev- eral projects over the next four years that have varying capital requirements. Each of the projects varies in terms of the investment required and in terms of the !nancial return it will generate. The four projects are: to expand the production plant that ICRC currently has; to expand the warehouse capacity to allow more production to be stored; to invest For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  APPLICATIONS INVOLVING 0–1 VARIABLES 15 in new production machinery that will improve production and ef#ciency; to invest in new product research. Faced with limited capital each year, management would like to select the most pro#table projects. The estimated net present value for each proj- ect,1 the capital requirements, and the available capital over the four-year period are shown in Table!15.1. So, for example, if the decision is taken to expand the production plant, it is anticipated that over the next four years this will generate a net present value of $90 000 but will require investment of capital in each of the four years of $15 000, $20 000, $20 000 and $15 000. The #nal column of Table 15.1 shows the investment capi- tal that ICRC has available each year and it is apparent from inspection that the avail- able capital will not fund all four projects. Clearly, our decision variables will relate to each of the four projects and we will require these variables to take only integer values. However, requiring the decision variables to take integer values is not enough; we cannot have two Plant Expansion projects or #ve Warehouse Expansion projects. Each project is an either2or decision. Either we invest in the Plant Expansion project or we don’t. Either we invest in the Warehouse Expansion project or we don’t. This is where the use of binary variables becomes so useful. The four 0–1 decision variables are as follows: P 5 1 if the plant expansion project is accepted; 0 if rejected W 5 1 if the warehouse expansion project is accepted; 0 if rejected M 5 1 if the new machinery project is accepted; 0 if rejected R 5 1 if the new product research project is accepted; 0 if rejected Table 15.1 Project Net Present Value, Capital Requirements and Available Capital for the Ice-Cold Refrigerator Company Project Plant Warehouse New New Product Total Capital Expansion Expansion Machinery Research Available Present Value !90 000 !40 000 !10 000 !37 000 Year 1 Cap Rqmt !15 000 !10 000 !10 000 !15 000 !40 000 Year 2 Cap Rqmt !20 000 !15 000 — !10 000 !50 000 Year 3 Cap Rqmt !20 000 !20 000 — !10 000 !40 000 Year 4 Cap Rqmt !15 000 !5 000 !4 000 !10 000 !35 000 In a capital budgeting problem, the company’s objective function is to maximize the net present value of the capital budgeting projects. This problem has four constraints: one for the Total Capital funds available in each of the next four years. A 021 integer linear programming model with euro in thousands is as follows: Max 90P 1 40W 1 10M 1 37R s.t. 15P 1 10W 1 10M 1 15R # 40 (Year 1 capital available) 20P 1 15W 1 10R # 50 (Year 2 capital available) 20P 1 20W 1 10R # 40 (Year 3 capital available) 15P 1 5W 1 4M 1 10R # 35 (Year 4 capital available) P, W, M, R 5 0, 1 It should be apparent how the binary variables work. Let us consider P. This can only take a value of 0 or of 1. If we set P 5 0 (effectively deciding not to invest in the Plant 1 The estimated net present value is the net cash "ow discounted back to the beginning of year 1. For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 16 CHAPTER 15 INTEGER LINEAR PROGRAMMING Expansion) then P will make a zero contribution to the objective function and will also require no capital in any of the four years. Equally if we set P 5 1 (deciding that the Plant Expansion goes ahead) then P will contribute 90 ($000) to the objective function but will also require some of the available capital funding in each of the 4 years ($15 000!in year!1, $20 000 in year 2, $20 000 in year 3, $15 000 in year 4). So, we are effectively look- ing for the combination of 0s and 1s for the four decision variables that will maximize the objective function but satisfy the de#ned constraints. The integer programming solution from Excel is shown in Figure 15.4 (Appendix 15.1 shows how binary variables can be incorporated into an Excel formulation). The opti- mal solution is P 5 1, W 5 1, M 5 1, R 5 0, with a total estimated net present value of $140 000. So, the company should fund the plant expansion, the warehouse expansion and the new machinery projects. The new product research project should be put on hold unless additional capital funds become available. The values of the slack variables show that the company will have $5000 remaining in year 1, $15 000 remaining in year 2 and $11 000 remaining in year 4. Checking the capital requirements for the new product research project, we see that enough funds are available for this project in year 2 and year 4. However, the company would have to #nd additional capital funds of $10 000 in year 1 and $10 000 in year 3 to fund the new product research project. Figure 15.4 The Excel Solution for the Ice-Cold Refrigerator Company Problem EXCEL !le ICE-COLD Fixed Cost In many situations, the cost of production has two components: a setup cost, which is a #xed cost, and a variable cost, which is directly related to the production quantity. The use of 0–1 variables makes including the setup cost possible in a model for a production For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  APPLICATIONS INVOLVING 0–1 VARIABLES 17 application. Such setup costs are typical of many industries where production facilities may be used for different products. For example, consider a company manufacturing cars. One of its models is produced in both a two-door version and a four-door version using the same production line. In a typical situation the company decides to use the production line to manufacture a given number of two-door vehicles. Once these ve- hicles have been produced the line then switches to producing a given number of the four-door version. In order to do this, however, it may have to re-program or recalibrate automated equipment on the production line; different vehicle parts will need to be made ready; maybe the production line will need cleaning. In other words, to switch to producing another product using the same production line will cost the company time and money. These costs are referred to as set up costs 2 they are incurred only if the company decides to switch production and then they are only incurred once. That is, if we decide to produce the four-door version then we have to take these setup costs into account. Clearly, we need to build this into any model that we develop and this is where binary variables again come in useful. As an example of a #xed-cost problem, consider the RMC company. Three raw ma- terials (1, 2, 3) are used to produce three products: a fuel additive, a solvent base and a carpet cleaning "uid. The following decision variables are used: F 5 kilos of fuel additive produced S 5 kilos of solvent base produced C 5 kilos of carpet cleaning fluid produced The pro#t contributions are $40 per kilo for the fuel additive, $30 per kilo for the solvent base, and $50 per kilo for the carpet cleaning "uid. Each kilo of fuel additive is a blend of 0.4 kilos of material 1 and 0.6 kilos of material 3. Each kilo of solvent base requires 0.5!kilos of material 1, 0.2 kilos of material 2 and 0.3 kilos of material 3. Each kilo of carpet cleaning "uid is a blend of 0.6 kilos of material 1, 0.1 kilos of material 2 and 0.3!kilos of material 3. RMC has 20 kilos of material 1, 5 kilos of material 2 and 21 kilos of material!3 and is interested in determining the optimal production quantities for the upcoming planning period. A straight forwardly proved linear programming model of the RMC problem is shown: Max 40F 1 30S 1 50C s.t. 0.4F 1 0.5S 1 0.6C # 20 Material 1 0.2S 1 0.1C # 5 Material 2 0.6F 1 0.3S 1 0.3C # 21 Material 3 F, S, C $ 0 Using Excel, we obtain an optimal solution consisting of 27.5 kilos of fuel additive, 0 kilos of solvent base and 15 kilos of carpet cleaning "uid, with a pro#t contribution of $1850, as shown in Figure 15.5. However, this linear programming formulation of the RMC problem does not in- clude a #xed cost for production setup of the products. Assume that there is a setup cost involved for each of the three products. So, for example, if we decide to manu- facture the fuel additive we will incur a setup cost of $200 (a #xed cost regardless of whether we produce one kilo of additive, or 10, or 20). Clearly, if we decide not to produce fuel additive then we will not incur this cost. The comparable #gures for the solvent base are $50 and $400 for carpet cleaning "uid. In addition, there are limits now placed on the maximum production of the three products (this may be because each setup will only allow us to produce a certain quantity of a product before we incur the setup costs again). For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 18 CHAPTER 15 INTEGER LINEAR PROGRAMMING Figure 15.5 The Excel Solution to the RMC Problem Product Setup Cost Maximum Production Fuel additive !200 50 kilos Solvent base ! 50 25 kilos Carpet cleaning fluid !400 40 kilos The modelling "exibility provided by 0–1 variables can now be used to incorpo- rate the #xed setup costs into the production model. The 0–1 variables are de#ned as follows: SF 5 1 if the fuel additive is produced; 0 if not SS 5 1 if the solvent base is produced; 0 if not SC 5 1 if the carpet cleaning fluid is produced; 0 if not Using these setup variables, the total setup cost is: 200SF 1 50SS 1 400SC Again, it is worthwhile re"ecting what we have here. Given that these variables can only take 0–1 values, this expression allows us to quantify total setup costs for any combina- tion of binary values. We can now rewrite the objective function to include the setup cost. So, the net pro#t objective function becomes: Max 40F 1 30S 1 50C 2 200SF 2 50SS 2 400SC Next, we must add production capacity constraints so that if a setup variable equals!0, production of the corresponding product is not permitted and, if a setup variable equals!1, production is permitted up to the maximum quantity. This requires some explanation. What we have to build into the model is a trig- ger! point so that if we decide to produce fuel additive then it must be no more For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  APPLICATIONS INVOLVING 0–1 VARIABLES 19 than the 50 kilos allowed as a maximum. However, we cannot write the constraint simply!as: F # 50 as we would in a standard LP problem because this constraint will only apply if we decide to produce fuel additive (i.e., SF 5 1). If we decide not to produce fuel additive (SF!5 0) then we must force F 5 0 also. This is achieved by writing our constraint as: F # 50SF If SF 5 1 then the constraint becomes: F # 50 In other words, if we decide to produce fuel additive we allow the quantity produced (F) to be anything up to the allowed maximum. However, if we decide not to produce fuel additive then SF 5 0 and the constraint effectively becomes: F#0 which, given the non-negativity requirement effectively forces F 5 0. Similar production capacity constraints, using 021 variables, are added for the sol- vent base and carpet cleaning products: S # 25SS C # 40SC Moving all the variables to the left-hand side of the constraints provides the following #xed cost model for the RMC problem. Note that we have also added a requirement that SF, SS and SC are binary variables: Max 40F 1 30S 1 50C 2 200SF 2 50SS 2 400SC s.t. 0.4F 1 0.5S 1 0.6C # 20 Material 1 0.2S 1 0.1C # 5 Material 2 0.6F 1 0.3S 1 0.3C # 21 Material 3 F 2 50SF # 0 Maximum F S 2 25SS # 0 Maximum S C 2 40SC # 0 Maximum C F, S, C $ 0; SF, SS, SC 5 0, 1 We solved the RMC problem with setup costs using Excel. As shown in Figure 15.6, the optimal solution shows 25 kilos of fuel additive and 20 kilos of solvent base. The value of the objective function after deducting the setup cost is $1350. The setup cost for the fuel additive and the solvent base is $200 1 $50 5 $250. The optimal solution shows SC 5 0, which indicates that the more expensive $400 setup cost for the carpet cleaning "uid should be avoided. So the carpet cleaning "uid is not produced. The key to developing a #xed cost model is the introduction of a 021 variable for each #xed cost and the speci#cation of an upper bound for the corresponding produc- tion variable. For a production quantity x, a constraint of the for x # My can then be used to allow production when the setup variable y 5 1 and not to allow produc- tion when the setup variable y 5 0. The value of the maximum production quantity M should be large enough to allow for all reasonable levels of production although research has shown that choosing values of M that are excessively large will slow the solution procedure. For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 20 CHAPTER 15 INTEGER LINEAR PROGRAMMING Figure 15.6 The Excel Solution to the RMC Problem with setup costs EXCEL !le RMC SETUP Distribution System Design The MB Company operates a plant in St. Louis manufacturing solar energy pan- els! with an annual capacity of 30 000 units. Product is shipped to regional distri- bution centres located in Boston, Atlanta, and Houston. Because of an anticipated increase in demand, MB plans to increase capacity by constructing a new plant in one or more of the following cities: Detroit, Toledo, Denver or Kansas City. The estimated annual #xed cost and the annual capacity for the four proposed plants are as follows: Proposed Plant Annual Fixed Cost ($) Annual Capacity Detroit 175 000 10 000 Toledo 300 000 20 000 Denver 375 000 30 000 Kansas City 500 000 40 000 The company’s long-range planning group developed forecasts of the anticipated annual demand at the distribution centres as follows: Distribution Center Annual Demand Boston 30 000 Atlanta 20 000 Houston 20 000 The shipping cost per unit from each plant to each distribution centre is shown in Table!15.2. A network representation of the potential MB distribution system is shown For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  APPLICATIONS INVOLVING 0–1 VARIABLES 21 in Figure 15.7. Each potential plant location is shown; capacities and demands are shown in thousands of units. This network representation is for a transportation problem with a plant at St. Louis and at all four proposed sites. However, the decision has not yet been made as to which new plant or plants will be constructed. Table 15.2 Shipping Cost per Unit for the MB Distribution System Distribution Centres Plant Site Boston Atlanta Houston Detroit 5 2 3 Toledo 4 3 4 Denver 9 7 5 Kansas City 10 4 2 St. Louis 8 4 3 Figure 15.7 The Network Representation of the MB Company Distribution System Problem Plants 1 10 Detroit 5 Distribution Centres 2 3 1 Boston 30 2 4 20 Toledo 3 4 9 3 7 30 Denver 2 5 20 Atlanta 10 4 4 2 40 Kansas City 8 3 4 Houston 20 3 5 30 St. Louis Capacities Distribution Routes Demands For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 22 CHAPTER 15 INTEGER LINEAR PROGRAMMING Let us now show how 0–1 variables can be used in this distribution system design problem to develop a model for choosing the best plant locations and for determin- ing how much to ship from each plant to each distribution centre. We can use the following 0–1 variables to represent the plant construction decision: y1 5 1 if a plant is constructed in Detroit; 0 if not y2 5 1 if a plant is constructed in Toledo; 0 if not y3 5 1 if a plant is constructed in Denver; 0 if not y4 5 1 if a plant is constructed in Kansas City; 0 if not The variables representing the amount shipped from each plant site to each distribu- tion centre are de#ned just as for a transportation problem: xij 5 the units shipped in thousands from plant i to distribution centre j i 5 1, 2, 3, 4, 5 and j 5 1, 2, 3 Using the shipping cost data in Table 15.2, the annual transportation cost in thousands of dollars is written: 5x11 1 2x12 1 3x13 1 4x21 1 3x22 1 4x23 1 9x31 1 7x32 1 5x33 1 10x41 1 4x42 1 2x43 1 8x51 1 4x52 1 3x53 The annual #xed cost of operating the new plant or plants in thousands of dollars is written as: 175y1 1 300y2 1 375y3 1 500y4 Note that the 0–1 variables are de#ned so that the annual #xed cost of operating the new plants is only calculated for the plant or plants that are actually constructed (i.e., yi 5 1). If a plant is not constructed, yi 5 0 and the corresponding annual #xed cost is $0. The objective function is the sum of the annual transportation cost plus the annual #xed cost of operating the newly constructed plants. Now let us consider the capacity constraints at the four proposed plants. Using De- troit as an example, we write the following constraint: x11 1 x121 x13 # 10y1 If the Detroit plant is constructed, y1 5 1 the total amount shipped from Detroit!to the three distribution centres must be less than or equal to Detroit’s 10 000-unit capac- ity. If the Detroit plant is not constructed, y1 5 0 will result in a 0 capacity at Detroit. In this case, the variables corresponding to the shipments from Detroit!must!all equal zero: x11 5 0, x12 5 0 and x13 5 0. By placing all variables on the!left-hand side of the con- straints, we have the following Detroit capacity constraint: x11 1 x12 1 x13 2 10y1 # 0 Detroit capacity In a similar fashion, the capacity constraint for the proposed plant in Toledo can be written: x21 1 x22 1 x23 2 20y2 # 0 Toledo capacity Similar constraints can be written for the proposed plants in Denver and Kansas City. Note that because a plant already exists in St. Louis, we do not de#ne a 0–1 variable for this plant. Its capacity constraint can be written as follows: x51 1 x52 1 x53 # 30 St. Louis capacity For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  APPLICATIONS INVOLVING 0–1 VARIABLES 23 Three demand constraints will be needed, one for each of the three distribution cen- tres. The demand constraint for the Boston distribution centre with units in thousands is written as: x11 1 x21 1 x31 1 x41 1 x51 5 30 Boston demand Similar constraints appear for the Atlanta and Houston distribution centres. The complete model for the distribution system design problem is as follows: Min 5x11 1 2x12 1 3x13 1 4x21 1 3x22 1 4x23 1 9x31 1 7x32 1 5x33 1 10x41 1 4x42 1 2x43 1 8x51 1 4x52 1 3x53 1 175y1 1 300y2 1 375y3 1 500y4 s.t. x11 1 x12 1 x13 2 10y1 #0 Detroit capacity x21 1 x22 1 x23 2 20y2 #0 Toledo capacity x31 1 x32 1 x33 2 30y3 #0 Denver capacity x41 1 x42 1 x43 2 40y4 # 0 Kansas City capacity x51 1 x52 1 x53 # 30 St. Louis capacity x11 1 x21 1 x31 1 x41 1 x51 5 30 Boston demand x12 1 x22 1 x32 1 x42 1 x52 5 20 Atlanta demand x13 1 x23 1 x33 1 x43 1 x53 5 20 Houston demand xij $ 0 for all i and j; y1, y2, y3, y4 5 0, 1 Using Excel, we obtained the solution shown in Figure 15.8. The optimal solution calls for the construction of a plant in Kansas City (y4 5 1); 20 000 units will be shipped from Kansas City to Atlanta (x42 5 20), 20 000 units will be shipped from Kansas City to Houston (x43 5 20), and 30 000 units will be shipped from St. Louis to Boston (x51 5 30). Note that the total cost of this solution including the #xed cost of $500 000 for the plant in Kansas City is $860 000. This basic model can be expanded to accommodate distribution systems involving direct shipments from plants to warehouses, from plants to retail outlets and multiple products.2 Using the special properties of 0–1 variables, the model can also be expanded to accommodate a variety of con#guration constraints on the plant locations. For example, suppose in another problem, site 1 was in Dallas and site 2 was in Fort Worth. A company might not want to locate plants in both Dallas and Fort Worth because the Problem 13, which cities are so close together. To prevent this result from happening, the following con- is based on the MB straint can be added to the model: distribution system problem, provides y1 1 y2 # 1 additional practice involving 0–1 variables. This constraint allows either y1 or y2 to equal 1, but not both. If we had written the con- straints as an equality, it would require that a plant be located in either Dallas or Fort Worth. Planning Location The Health Ministry in an East African country is trying to provide basic health care services for its people but has limited resources so careful planning is needed. The Min- istry wants to extend health care services in a 20 district region of the country (see Fig- ure! 15.9). The Ministry wants to establish a small, local health clinic in each district. For computational reasons, it is usually preferable to replace the m plant capacity constraints with mm shipping route 2 capacity constraints of the form xij # Min{si, dj} yi for i 5 1,... , m, and j 5 1,... , n. The coef#cient for yi in each of these constraints is the smaller of the origin capacity (si) or the destination demand (dj). These additional constraints often cause the solution of the LP Relaxation to be integer. For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 24 CHAPTER 15 INTEGER LINEAR PROGRAMMING Figure 15.8 The Excel Solution for the MB Company Distribution System Problem OPTIMAL SOLUTION EXCEL !le Objective Function Value = 860.000 MB Variable Value -------------- --------------- X11 0.000 X12 0.000 X13 0.000 X21 0.000 X22 0.000 X23 0.000 X31 0.000 X32 0.000 X33 0.000 X41 0.000 X42 20.000 X43 20.000 X51 30.000 X52 0.000 X53 0.000 Y1 0.000 Y2 0.000 Y3 0.000 Y4 1.000 Constraint Slack/Surplus -------------- --------------- 1 0.000 2 0.000 3 0.000 4 0.000 5 0.000 6 0.000 7 0.000 8 0.000 Each clinic will be staffed by a nurse who will provide advice and basic health care treatment to people living in that district. However, for this to be practical, each clinic needs to be located near to a large health centre (HC). Such health centres are larger and better resourced and can provide back-up and additional specialist support to the smaller clinics. The Ministry has decided that if a health centre is set up in a particular district then it is feasible to establish a local health clinic only in that district and in each adjacent district. Health centres, however, are expensive to setup and to maintain. The Ministry wants to know the minimum number of health centres it will need to set up so that each district can have a local health clinic. Figure 15.9 shows the 20 districts in the region. Table 15.3 shows the same districts and the adjacent districts. A 0–1 integer programming model can be used to solve this location planning problem. We de#ne the variables as: xi 5 1 if a HC is established in county i ; 0 otherwise For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  APPLICATIONS INVOLVING 0–1 VARIABLES 25 Figure 15.9 The 20-District Region 2 1 12 3 4 16 5 13 9 10 15 7 8 11 6 14 18 20 19 17 Districts 1. Ashtabula 6. Richland 11. Stark 16. Trumbull 2. Lake 7. Ashland 12. Geauga 17. Knox 3. Cuyahoga 8. Wetland 13. Portage 18. Holmes 4. Lorain 9. Medina 14. Oxbend 19. Tuscarawas 5. Highland 10. Summit 15. Mahoning 20. Kraal Table 15.3 Districts Under Consideration Adjacent Districts (by Number) 1. Ashtabula 2, 12, 16 2. Lake 1, 3, 12 3. Cuyahoga 2, 4, 9, 10, 12, 13 4. Lorain 3, 5, 7, 9 5. Highland 4, 6, 7 6. Richland 5, 7, 17 7. Ashland 4, 5, 6, 8, 9, 17, 18 8. Wetland 7, 9, 10, 11, 18 9. Medina 3, 4, 7, 8, 10 10. Summit 3, 8, 9, 11, 12, 13 11. Stark 8, 10, 13, 14, 15, 18, 19, 20 12. Geauga 1, 2, 3, 10, 13, 16 13. Portage 3, 10, 11, 12, 15, 16 14. Oxbend 11, 15, 20 15. Mahoning 11, 13, 14, 16 16. Trumbull 1, 12, 13, 15 17. Knox 6, 7, 18 18. Holmes 7, 8, 11, 17, 19 19. Tuscarawas 11, 18, 20 20. Kraal 11, 14, 19 For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017) 26 CHAPTER 15 INTEGER LINEAR PROGRAMMING To minimize the number of HCs needed, we write the objective function as: Min x1 1 x2 1... 1 x20 The Ministry may locate clinics in a district if the district contains an HC or is adjacent to another district with a health centre. As an example, let’s look at Ashtabula district which is adjacent to Lake district, Geauga district and Trumbull district. So, in order to have a local health clinic in Ashtabula dis- trict, the Ministry has to set up an HC in one of these four districts. This means that we can formulate a suitable constraint for Ashtabula district: x1 1 x2 1 x12 1 x16 $ 1 which requires at least one HC in these four districts (there may need to be more than one given the other districts are adjacent to more than just Ashtabula). The complete statement of the location problem is then: Min x1 1 x2 1... 1 x20 s.t. x1 1 x2 1 x12 1 x16 $ 1 Ashtabula x1 1 x2 1 x3 1 x12 $ 1 Lake x2 1 x3 1 x4 1 x9 1 x10 1 x12 1 x13 $ 1 Cuyahoga x3 1 x4 1 x5 1 x7 1 x9 $ 1 Lorain x41 x51 x61 x7 $ 1 Highland x51 x61 x71 x17 $ 1 Richland x4 1 x5 1 x6 1 x7 1 x8 1 x9 1 x17 1 x18 $ 1 Ashland x7 1 x8 1 x9 1 x10 1 x11 1x18 $ 1 Wetland x3 1 x4 1 x7 1 x8 1 x9 1 x10 $ 1 Medina x3 1 x8 1 x9 1 x10 1 x11 1 x12 1 x13 $ 1 Summit x8 1 x10 1 x11 1 x13 1 x14 1 x15 1 x18 1 x19 1 x20 $ 1 Stark x1 1 x2 1 x3 1 x10 1 x12 1 x13 1 x16 $ 1 Geauga x3 1 x10 1 x11 1 x12 1 x13 1 x15 1 x16 $ 1 Portage x11 1 x14 1 x15 1 x20 $ 1 Oxbend x11 1 x131 x141 x151 x 16 $ 1 Mahoning x1 1 x12 1 x131 x151 x16 $ 1 Trumbull x6 1 x7 1 x17 1 x18 $ 1 Knox x71 x81 x111 x171 x181 x19 $ 1 Holmes x11 1 x18 1 x19 1 x20 $ 1 Tuscawaras x11 1 x14 1 x19 1 x20 $ 1 Krall xi 5 0, 1 i 5 1, 2,... , 20 We used Excel to solve this 20-variable, 20-constraint problem formulation. In Figure!15.10 we show a portion of the computer output. Note that the variable names correspond to the #rst four letters in the name of each district. Using the output, we see that the optimal solution calls for health centres in Ashland, Stark and Geauga counties. With HCs in these three districts, the Ministry can place local clinics in all For use only with ‘An Introduction to Management Science’ 3e Anderson, Sweeney, Williams, Wisniewski, Pierron (Cengage Learning EMEA, 2017)  APPLICATIONS INVOLVING 0–1 VARIABLES 27 20 districts (see!Figure 15.11). All other decision variables have an optimal value of