Integer Programming Models | Introduction to Management Science (10th Edition)

[Page 181 ( continued )]

There are three basic types of integer linear programming modelsa total integer model, a 01 integer model, and a mixed integer model. In a total integer model , all the decision variables are required to have integer solution values. In a 01 integer model , all the decision variables have integer values of zero or one. Finally, in a mixed integer model , some of the decision variables (but not all) are required to have integer solutions. The following three examples demonstrate each of these types of integer programming models.

The three types of integer programming models are total, 01, and mixed.

A Total Integer Model Example

The owner of a machine shop is planning to expand by purchasing some new machinespresses and lathes. The owner has estimated that each press purchased will increase profit by $100 per day and each lathe will increase profit by $150 daily. The number of machines the owner can purchase is limited by the cost of the machines and the available floor space in the shop. The machine purchase prices and space requirements are as follows :

Machine	Required Floor Space (ft. ² )	Purchase Price
Press	15	$8,000
Lathe	30	4,000

In a total integer model , all decision variables have integer solution values .

The owner has a budget of $40,000 for purchasing machines and 200 square feet of available floor space. The owner wants to know how many of each type of machine to purchase to maximize the daily increase in profit.

The linear programming model for an integer programming problem is formulated in exactly the same way as the linear programming examples in Chapters 2, 3, and 4. The only difference is that in this problem, the decision variables are restricted to integer values because the owner cannot purchase a fraction, or portion, of a machine. The linear programming model follows:

[Page 182]

The decision variables in this model are restricted to whole machines. The fact that both decision variables, x ₁ and x ₂ , can assume any integer value greater than or equal to zero is what gives this model its designation as a total integer model.

A 01 Integer Model Example

A community council must decide which recreation facilities to construct in its community. Four new recreation facilities have been proposeda swimming pool, a tennis center, an athletic field, and a gymnasium. The council wants to construct facilities that will maximize the expected daily usage by the residents of the community, subject to land and cost limitations. The expected daily usage and cost and land requirements for each facility follow:

Recreation Facility	Expected Usage (people/day)	Cost	Land Requirements (acres)
Swimming pool	300	$35,000	4
Tennis center	90	10,000	2
Athletic field	400	25,000	7
Gymnasium	150	90,000	3

In a 01 integer model , the solution values of the decision variables are zero or one .

The community has a $120,000 construction budget and 12 acres of land. Because the swimming pool and tennis center must be built on the same part of the land parcel , however, only one of these two facilities can be constructed . The council wants to know which of the recreation facilities to construct to maximize the expected daily usage. The model for this problem is formulated as follows:

where

x ₁ = construction of a swimming pool

x ₂ = construction of a tennis center

x ₃ = construction of an athletic field

x ₄ = construction of a gymnasium

In this model, the decision variables can have a solution value of either zero or one . If a facility is not selected for construction, the decision variable representing it will have a value of zero. If a facility is selected, its decision variable will have a value of one.

The last constraint, x ₁ + x ₂ 1, reflects the contingency that either the swimming pool ( x ₁ ) or the tennis center ( x ₂ ) can be constructed, but not both. In order for the sum of x ₁ and x ₂ to be less than or equal to one, either of the variables can have a value of one, or both variables can equal zero. This is also referred to as a mutually exclusive constraint .

If the community had specified that either the swimming pool ( x ₁ ) or the tennis center ( x ₂ ) must be built, but not both, then the last constraint would become an equation, x ₁ + x ₂ = 1. This would result in a solution that would include x ₁ = 1 or x ₂ = 1, but both would not equal one (nor would both equal zero). In this manner, the model forces a choice between the two facilities. For this reason, it is often called a multiple-choice constraint .

[Page 183]

A variation of the multiple-choice constraint can be used to formulate a situation where some specific number of facilities out of the total must be constructed. For example, if the community council had specified that exactly two of the four facilities must be built, this constraint would be formulated as

x ₁ + x ₂ + x ₃ + x ₄ = 2

If, alternatively, the council had specified that no more than two facilities must be constructed, the constraint would be

x ₁ + x ₂ + x ₃ + x ₄ 2

Another type of 01 model constraint is a conditional constraint . In a conditional constraint, the construction of one facility would be conditional upon the construction of another. Suppose, for example, that the pet project of the head of the community council is the swimming pool, and she also believes the tennis center is frivolous. The council head is very influential, so the rest of the council knows that the tennis center has no chance of being selected if the pool is not selected first. However, even if the pool is selected, there is no guarantee that the tennis center will also be selected. Thus, the tennis center ( x ₂ ) is conditional upon construction of the swimming pool ( x ₁ ). This condition is formulated as

x ₂ x ₁

Notice that the tennis center ( x ₂ ) cannot equal one (i.e., be selected) unless the pool ( x ₁ ) equals one. If the pool ( x ₁ ) equals zero (i.e., it is not selected), then the tennis center ( x ₂ ) must also equal zero. However, this condition does allow the pool ( x ₁ ) to equal one and be selected and the tennis center to equal zero and not be selected.

A variation of this type of conditional constraint is the corequisite constraint , wherein if one facility is constructed, the other one would also be constructed and vice versa. For example, suppose the council worked out a political deal among themselves , wherein if the pool is accepted, the tennis center must also be selected and vice versa. This constraint is written as

x ₂ = x ₁

This constraint makes x ₁ and x ₂ equal the same value, either zero or one.

A Mixed Integer Model Example

Nancy Smith has $250,000 to invest in three alternative investmentscondominiums, land, and municipal bonds . She wants to invest in the alternatives that will result in the greatest return on investment after 1 year.

In a mixed integer model , some solution values for decision variables are integers and others can be nonintegers .

Each condominium costs $50,000 and will return a profit of $9,000 if sold at the end of 1 year; each acre of land costs $12,000 and will return a profit of $1,500 at the end of 1 year; and each municipal bond costs $8,000 and will result in a return of $1,000 if sold at the end of 1 year. In addition, there are only 4 condominiums, 15 acres of land, and 20 municipal bonds available for purchase.

[Page 184]

The linear programming model for this problem is formulated as follows:

where

x ₁ = condominiums purchased

x ₂ = acres of land purchased

x ₃ = bonds purchased

Management Science Application: Allocating Operating Room Time at Toronto's Mount Sinai Hospital

Mount Sinai Hospital in Toronto has 14 operating rooms that serve 5 surgical departments, including surgery, gynecology, ophthalmology, otolaryngology, and oral surgery. The largest of these departments, surgery, consists of 5 subareas, including orthopedics, general surgery, plastic surgery, vascular surgery, and urology . The hospital has 397.50 operating room hours available per week, and it employs an integer programming model to develop a master surgical schedule that allocates operating room time to its 5 primary surgical departments. A daily operating room schedule includes the actual cases to be performed, start and end times, attending physicians, and anesthetists, and it is similar to a production schedule in a manufacturing plant. Operating room times are assigned as blocks; whenever possible, only one department is assigned to an operating room on a single day, thus constituting a block. It is possible to split blocks into morning and afternoon sessions and to alternate the same block between departments in different weeks, although the hospital attempts to minimize these types of allocations and keep the schedule as consistent as possible from week to week.

In the integer programming model, the decision variables, x _ijk , equal the number of time blocks of operating room i , assigned to department j , on day k . The objective is to minimize the sum of the differences, or shortfalls, between the assigned operating room times and target times, represented as penalty functions, for all departments. A primary constraint is that the sum of all times allocated to a department, j , over all days, k , be (as nearly as possible) equal to a target number of hours. Additional constraints include daily and weekly bounds on the number of rooms assigned to a department, limits on the amount of under- or overallocation of time to any particular department, and daily room availability. The model solution provides an allocation of time blocks to departments that minimizes the shortage of time to each. Since its implementation, the model has reduced the clerical time for producing a schedule from days (using a manual approach) to 1 or 2 hours, and has resulted in roughly $20,000 per year in savings derived from the reduced time required by the operating room manager for schedule development. In addition, the model has provided hospital management with greater flexibility, increased ability to explore creative scheduling options, and generally improved quality schedules. However, perhaps the model's greatest benefit has been to provide unbiased , equitable schedules through a consistent, identifiable process, thus reducing conflict between departments and surgeons.

Source: J. T. Blake and J. Donald, "Mount Sinai Hospital Uses Integer Programming to Allocate Operating Room Time," Interfaces 32, no. 2 (MarchApril 2002): 6373.

[Page 185]

Notice that in this model the solution values for condominiums ( x ₁ ) and municipal bonds ( x ₃ ) must be integers. It is not possible to invest in a fraction of a condominium or to purchase part of a bond. However, it is possible to purchase less than an acre of land (i.e., a portion of an acre). Thus, two of the decision variables ( x ₁ and x ₃ ) are restricted to integer values, whereas the other variable ( x ₄ ) can take on any real value greater than or equal to zero.