Integer Programming9The linear-programming models that have been discussed thus far all have been continuous, in the sense thatdecision variables are allowed to be fractional. Often this is a realistic assumption. For instance, we mighteasily produce 10234gallons of a divisible good such as wine. It also might be reasonable to accept a solutiongiving an hourly production of automobiles at 5812if the model were based upon average hourly production,and the production had the interpretation of production rates.At other times, however, fractional solutions are not realistic, and we must consider the optimizationproblem:MaximizenXj=1cjxj,subject to:nXj=1aijxj= bi(i = 1, 2, . . . , m),xj≥ 0 ( j = 1, 2, . . . , n),xjinteger (for some or all j = 1, 2, . . . , n).This problem is called the (linear) integer-programming problem. It is said to be a mixed integer programwhen some, but not all, variables are restricted to be integer, and is called a pure integer program when alldecision variables must be integers. As we saw in the preceding chapter, if the constraints are of a networknature, thenan integersolution can beobtained by ignoringthe integrality restrictions andsolving the resultinglinearprogram. In general, though, variableswill be fractionalin the linear-programming solution, and furthermeasures must be taken to determine the integer-programming solution.The purpose of this chapter is twofold. First, we will discuss integer-programming formulations. Thisshould provide insight into the scope of integer-programming applications and give some indication ofwhy many practitioners feel that the integer-programming model is one of the most important models inmanagement science. Second, we consider basic approaches that have been developed for solving integerand mixed-integer programming problems.9.1 SOME INTEGER-PROGRAMMING MODELSInteger-programming models arise in practically every area of application of mathematical programming. Todevelop a preliminary appreciation for the importance of these models, we introduce, in this section, threeareas where integer programming has played an important role in supporting managerial decisions. We donot provide the most intricate available formulations in each case, but rather give basic models and suggestpossible extensions.2729.1 Some Integer-Programming Models 273Capital Budgeting In a typical capital-budgeting problem, decisions involve the selection of a number ofpotential investments. The investment decisions might be to choose among possible plant locations, to selecta configuration of capital equipment, or to settle upon a set of research-and-development projects. Often itmakes no sense to consider partial investments in these activities, and so the problem becomes a go–no-gointeger program, where the decision variables are taken to be xj= 0 or 1, indicating that the jth investmentis rejected or accepted. Assuming that cjis the contribution resulting from the jth investment and that aijisthe amount of resource i, such as cash or manpower, used on the jth investment, we can state the problemformally as:MaximizenXj=1cjxj,subject to:nXj=1aijxj≤ bi(i = 1, 2, . . . , m),xj= 0 or 1 ( j = 1, 2, . . . , n).The objective is to maximize total contributionfrom all investments without exceedingthe limited availabilitybiof any resource.One important special scenario for the capital-budgeting problem involves cash-flow constraints. In thiscase, the constraintsnXj=1aijxi≤ bireflect incremental cash balance in each period. The coefficients aijrepresent the net cash flow from in-vestment j in period i. If the investment requires additional cash in period i, then aij> 0, while if theinvestment generates cash in period i, then aij< 0. The righthand-side coefficients birepresent the incre-mental exogenous cash flows. If additional funds are made available in period i, then bi> 0, while if fundsare withdrawn in period i, then bi< 0. These constraints state that the funds required for investment mustbe less than or equal to the funds generated from prior investments plus exogenous funds made available (orminus exogenous funds withdrawn).The capital-budgeting model can be made much richer by including logical considerations. Suppose, forexample, that investment in a new product line is contingent upon previous investment in a new plant. Thiscontingency is modeled simply by the constraintxj≥ xi,which states that if xi= 1 and project i (new product development) is accepted, then necessarily xj= 1 andproject j (construction of a new plant) must be accepted. Another example of this nature concerns conflictingprojects. The constraintx1+ x2+ x3+ x4≤ 1,for example, states that only one of the first four investments can be accepted. Constraints like this commonlyare called multiple-choice constraints. By combining these logical constraints, the model can incorporatemany complex interactions between projects, in addition to issues of resource allocation.The simplest of all capital-budgeting models has just one resource constraint, but has attracted muchattention in the management-science literature. It is stated as:MaximizenXj=1cjxj,274 Integer Programming 9.1subject to:nXj=1ajxj≤ b,xj= 0 or 1 ( j = 1, 2, . . . , n).Usually, this problem is called the 0–1 knapsack problem, since it is analogous to a situation in which ahiker must decide which goods to include on his trip. Here cjis the ‘‘value’’ or utility of including good j,which weighs aj> 0 pounds; the objective is to maximize the ‘‘pleasure of the trip,’’ subject to the weightlimitation that the hiker can carry no more than b pounds. The model is altered somewhat by allowing morethan one unit of any good to be taken, by writing xj≥ 0 and xj-integer in place of the 0–1 restrictions onthe variables. The knapsack model is important because a number of integer programs can be shown to beequivalent to it, and further, because solution procedures for knapsack models have motivated procedures forsolving general integer programs.Warehouse Location In modeling distribution systems, decisions must be made about tradeoffs betweentransportation costs and costs for operating distribution centers. As an example, suppose that a manager mustdecide which of n warehouses to use for meeting the demands of m customers for a good. The decisions tobe made are which warehouses to operate and how much to ship from any warehouse to any customer. Letyi=1 if warehouse i is opened,0 if warehouse i is not