Integer Programming

The linear-programming models that have been discussed thus far all have been continuous, in the sense that decision variables are allowed to be fractional. Often this is a realistic assumption. For instance, we might 3 easily produce 102 4 gallons of a divisible good such as wine. It also might be reasonable to accept a solution 1 giving an hourly production of automobiles at 58 2 if 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 optimization problem:

• Maximize j=1 cjxj, subject to: n j=1 ai j x j = bi xj ? 0 x j integer (i = 1, 2, . . . , m), ( j = 1, 2, . . . , n), (for some or all j = 1, 2, . . . , n).

Order custom essay Integer Programming with free plagiarism report

450+ experts on 30 subjects Starting from 3 hours delivery

Get Essay Help

This problem is called the (linear) integer-programming problem. It is said to be a mixed integer program when some, but not all, variables are restricted to be integer, and is called a pure integer program when all decision variables must be integers. As we saw in the preceding chapter, if the constraints are of a network nature, then an integer solution can be obtained by ignoring the integrality restrictions and solving the resulting linear program.

In general, though, variables will be fractional in the linear-programming solution, and further measures must be taken to determine the integer-programming solution. The purpose of this chapter is twofold. First, we will discuss integer-programming formulations. This should provide insight into the scope of integer-programming applications and give some indication of why many practitioners feel that the integer-programming model is one of the most important models in management science. Second, we consider basic approaches that have been developed for solving integer and mixed-integer programming problems.

Some integer-programming models

Integer-programming models arise in practically every area of application of mathematical programming. To develop a preliminary appreciation for the importance of these models, we introduce, in this section, three areas where integer programming has played an important role in supporting managerial decisions. We do not provide the most intricate available formulations in each case, but rather give basic models and suggest possible extensions.

Capital Budgeting

In a typical capital-budgeting problem, decisions involve the selection of a number of potential investments. The investment decisions might be to choose among possible plant locations, to select a configuration of capital equipment, or to settle upon a set of research-and-development projects. Often it makes no sense to consider partial investments in these activities, and so the problem becomes a go–no-go integer program, where the decision variables are taken to be x j = 0 or 1, indicating that the jth investment is rejected or accepted.

Assuming that c j is the contribution resulting from the jth investment and that ai j is the amount of resource i, such as cash or manpower, used on the jth investment, we can state the problem formally as: Maximize j=1 cjxj, subject to: n j=1 ai j x j bi xj = 0 or (i = 1, 2, . . . , m), 1 ( j = 1, 2, . . . , n). The objective is to maximize total contribution from all investments without exceeding the limited availability bi of any resource. One important special scenario for the capital-budgeting problem involves cash-flow constraints.

These constraints state that the funds required for investment must be less than or equal to the funds generated from prior investments plus exogenous funds made available (or minus exogenous funds withdrawn). The capital-budgeting model can be made much richer by including logical considerations. Suppose, for example, that investment in a new product line is contingent upon previous investment in a new plant. This contingency is modeled simply by the constraint x j xi , which states that if xi = 1 and project i (new product development) is accepted, then necessarily x j = 1 and project j (construction of a new plant) must be accepted.

Another example of this nature concerns conflicting projects. The constraint x1 + x2 + x3 + x4 1, for example, states that only one of the first four investments can be accepted. Constraints like this commonly are called multiple-choice constraints. By combining these logical constraints, the model can incorporate many 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 much attention in the management-science literature. It is stated as: n Maximize j=1 jxj, 274. 1 subject to: n j=1 a j x j 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 a hiker must decide which goods to include on his trip. Here c j is the ‘‘value’’ or utility of including good j, which weighs a j > 0 pounds; the objective is to maximize the ‘‘pleasure of the trip,’’ subject to the weight limitation that the hiker can carry no more than b pounds. The model is altered somewhat by allowing more than one unit of any good to be taken, by writing x j and x j -integer in place of the 0–1 restrictions on the variables. The knapsack model is important because a number of integer programs can be shown to be equivalent to it, and further, because solution procedures for knapsack models have motivated procedures for solving general integer programs.

Warehouse Location

In modeling distribution systems, decisions must be made about tradeoffs between transportation costs and costs for operating distribution centers. As an example, suppose that a manager must decide which of n warehouses to use for meeting the demands of m customers for a good.

The constraints indicate that each customer’s demand must be met. The summation over the shipment variables xi j in the ith constraint of (3) is the amount of the good shipped from warehouse i. When the warehouse is not opened, yi = 0 and the constraint specifies that nothing can be shipped from the warehouse. On the other hand, when the warehouse is opened and yi = 1, the constraint simply states that the amount to be shipped from warehouse i can be no larger than the total demand, which is always true. Consequently, constraints imply restriction as proposed above.

Although oversimplified, this model forms the core for sophisticated and realistic distribution models incorporating such features as:

1. multi-echelon distribution systems from plant to warehouse to customer;
2. capacity constraints on both plant production and warehouse throughput;
3. economies of scale in transportation and operating costs;
4. service considerations such as maximum distribution time from warehouses to customers;
5. multiple products;
6. conditions preventing splitting of orders (in the model above, the demand for any customer can be supplied from several warehouses).

These features can be included in the model by changing it in several ways. For example, warehouse capacities are incorporated by replacing the term involving yi in constraint (3) with yi K i , where K i is the throughput capacity of warehouse i; multi-echelon distribution may require triple-subscripted variables xi jk denoting the amount to be shipped, from plant i to customer k through warehouse j. Further examples of how the simple warehousing model described here can be modified to incorporate the remaining features mentioned in this list are given in the exercises at the end of the chapter.

Scheduling

The entire class of problems referred to as sequencing, scheduling, and routing are inherently integer programs. Consider, for example, the scheduling of students, faculty, and classrooms in such a way that the number of students who cannot take their first choice of classes is minimized. There are constraints on the number and size of classrooms available at any one time, the availability of faculty members at particular times, and the preferences of the students for particular schedules. Clearly, then, the ith student is scheduled for the jth class during the nth time period or not; hence, such a variable is either zero or one.

Other examples of this class of problems include line-balancing, critical-path scheduling with resource constraints, and vehicle dispatching. As a specfic example, consider the scheduling of airline flight personnel. The airline has a number of routing ‘‘legs’’ to be ? own, such as 10 A. M. New York to Chicago, or 6 P. M. Chicago to Los Angeles. The airline must schedule its personnel crews on routes to cover these ? ights. One crew, for example, might be scheduled to y a route containing the two legs just mentioned.

In general, if a constraint of this form is included for each way in which the cities can be divided into two groups, then subtours will be eliminated. The problem with this and related approaches is that, with n cities, constraints of this nature must be added, so that the formulation becomes a very large integer-programming problem. For this reason the traveling salesman problem generally is regarded as dif? cult when there are many cities. The traveling salesman model is used as a central component of many vehicular routing and scheduling models. It also arises in production scheduling.

For example, suppose that we wish to sequence jobs on a single machine, and that ci j is the cost for setting up the machine for job j, given that job i has just been completed. What scheduling sequence for the jobs gives the lowest total setup costs? The problem can be interpreted as a traveling salesman problem, in which the ‘‘salesman’’ corresponds to the machine which must ‘‘visit’’ or perform each of the jobs. ‘‘Home’’ is the initial setup of the machine, and, in some applications, the machine will have to be returned to this initial setup after completing all of the jobs.

That is, the ‘‘salesman’’ must return to ‘‘home’’ after visiting the ‘‘cities. ’’

Formulating integer programs

The illustrations in the previous section not only have indicated specific integer-programming applications, but also have suggested how integer variables can be used to provide broad modeling capabilities beyond those available in linear programming. In many applications, integrality restrictions reflect natural indivisibilities of the problem under study. For example, when deciding how many nuclear aircraft carriers to have in the U. S.

Navy, fractional solutions clearly are meaningless, since the optimal number is on the order of one or two. In these situations, the decision variables are inherently integral by the nature of the decision-making problem. This is not necessarily the case in every integer-programming application, as illustrated by the capitalbudgeting and the warehouse-location models from the last section. In these models, integer variables arise from (i) logical conditions, such as if a new product is developed, then a new plant must be constructed, and from (ii) non-linearities such as field costs for opening a warehouse. Considerations of this nature are so important for modeling that we devote this section to analyzing and consolidating specific integerprogramming formulation techniques, which can be used as tools for a broad range of applications. Binary (0–1) Variables Suppose that we are to determine whether or not to engage in the following activities: (i) to build a new plant, (ii) to undertake an advertising campaign, or (iii) to develop a new product. In each case, we must make a yes–no or so-called go–no–go decision.

These choices are modeled easily by letting x j = 1 if we engage in the jth activity and x j = 0 otherwise. Variables that are restricted to 0 or 1 in this way are termed binary, bivalent, logical, or 0–1 variables. Binary variables are of great importance because they occur regularly in many model formulations, particularly in problems addressing long-range and high-cost strategic decisions associated with capital-investment planning. If, further, management had decided that at most one of the above three activities can be pursued, the 782 following constraint is appropriate: 3 j=1 x j ? 1. As we have indicated in the capital-budgeting example in the previous section, this restriction usually is referred to as a multiple-choice constraint, since it limits our choice of investments to be at most one of the three available alternatives. Binary variables are useful whenever variables can assume one of two values, as in batch processing. For example, suppose that a drug manufacturer must decide whether or not to use a fermentation tank.

Don't let plagiarism ruin your grade

Run a free check or have your essay done for you

Check my essay Hire Writer