In this chapter we found that simply rounding off non-integer simplex solution values for models requiring integer solutions is not always appropriate. Rounding can often lead to suboptimal results. Therefore, direct solution approaches using the computer are needed to solve the three forms of linear integer programming modelstotal integer models, 01 integer models, and mixed integer models.
Having analyzed integer problems and the computer techniques for solving them, we have now covered most of the basic forms of linear programming models and solution techniques. Two exceptions are the transportation model and a problem that contains more than one objective, goal programming. These special cases of linear programming are presented in the next two chapters.
Baumol, W. J. Economic Theory and Operations Analysis , 4th ed. Upper Saddle River, NJ: Prentice Hall, 1977.
Dantzig, G. B. "On the Significance of Solving Linear Programming Problems with Some Integer Variables." Econometrica 28 (1960): 3044.
Gomory, R. E. "An Algorithm for Integer Solutions to Linear Programs." In Recent Advances in Mathematical Programming , edited by R. L. Graves and P. Wolfe. New York: McGraw-Hill, 1963.
Lawler, E. L., and Wood, D. W. "Branch and Bound MethodsA Survey." Operations Research 14 (1966): 699719.
Little, J. D. C., et al. "An Algorithm for the Traveling Salesman Problem." Operations Research 11 (1963): 97289.
McMillan, C., Jr. Mathematical Programming . New York: John Wiley & Sons, 1970.
Mitten, L. G. "Branch-and-Bound Methods: General Formulation and Properties." Operations Research 18 (1970): 2434.
Plane, D. R., and McMillan, C., Jr. Discrete Optimization . Upper Saddle River, NJ: Prentice Hall, 1971.
Wagner, H. M. Principles of Operations Research , 2nd ed. Upper Saddle River, NJ: Prentice Hall, 1975.
Example Problem Solution
The following example problem demonstrates the model formulation and solution of a total integer programming problem.
The Problem Statement
A textbook publishing company has developed two new sales regions and is planning to transfer some of its existing sales force into these two regions . The company has 10 salespeople available for the transfer. Because of the different geographic configurations and the location of schools in each region, the average annual expenses for a salesperson differ in the two regions; the average is $10,000 per salesperson in region 1 and $7,000 per salesperson in region 2. The total annual expense budget for the new regions is $72,000. It is estimated that a salesperson in region 1 will generate an average of $85,000 in sales each year and a salesperson in region 2 will generate $60,000 annually in sales. The company wants to know how many salespeople to transfer into each region to maximize increased sales.
Formulate this problem and solve it by using QM for Windows.
Step 1: Formulate the Integer Programming Model
Step 2: Solve the Model Using QM for Windows
Consider the following linear programming model:
Demonstrate the graphical solution of this model.
Solve the following linear programming model by using the computer:
A tailor makes wool tweed sport coats and wool slacks. He is able to get a shipment of 150 square yards of wool cloth from Scotland each month to make coats and slacks, and he has 200 hours of his own labor to make them each month. A coat requires 3 square yards of wool and 10 hours to make, and a pair of slacks requires 5 square yards of wool and 4 hours to make. The tailor earns $50 in profit from each coat he makes and $40 from each pair of slacks. He wants to know how many coats and pairs of slacks to produce to maximize profit.
A jeweler and her apprentice make silver pins and necklaces by hand. Each week they have 80 hours of labor and 36 ounces of silver available. It requires 8 hours of labor and 2 ounces of silver to make a pin and 10 hours of labor and 6 ounces of silver to make a necklace. Each pin also contains a small gem of some kind. The demand for pins is no more than six per week. A pin earns the jeweler $400 in profit, and a necklace earns $100. The jeweler wants to know how many of each item to make each week to maximize profit.
A glassblower makes glass decanters and glass trays on a weekly basis. Each item requires 1 pound of glass, and the glassblower has 15 pounds of glass available each week. A glass decanter requires 4 hours of labor, a glass tray requires only 1 hour of labor, and the glassblower works 25 hours a week. The profit from a decanter is $50, and the profit from a tray is $10. The glassblower wants to determine the total number of decanters ( x 1 ) and trays ( x 2 ) that he needs to produce in order to maximize his profit.
The Livewright Medical Supplies Company has a total of 12 salespeople it wants to assign to three regionsthe South, the East, and the Midwest. A salesperson in the South earns $600 in profit per month for the company, a salesperson in the East earns $540, and a salesperson in the Midwest earns $375. The southern region can have a maximum assignment of 5 salespeople. The company has a total of $750 per day available for expenses for all 12 salespeople. A salesperson in the South has average expenses of $80 per day, a salesperson in the East has average expenses of $70 per day, and a salesperson in the Midwest has average daily expenses of $50. The company wants to determine the number of salespeople to assign to each region to maximize profit.
Helen Holmes makes pottery by hand in her basement . She has 20 hours available each week to make bowls and vases. A bowl requires 3 hours of labor, and a vase requires 2 hours of labor. It requires 2 pounds of special clay to make a bowl and 5 pounds to produce a vase; she is able to acquire 35 pounds of clay per week. Helen sells her bowls for $50 and her vases for $40. She wants to know how many of each item to make each week to maximize her revenue.
Lauren Moore has sold her business for $500,000 and wants to invest in condominium units (which she intends to rent) and land (which she will lease to a farmer). She estimates that she will receive an annual return of $8,000 for each condominium and $6,000 for each acre of land. A condominium unit costs $70,000, and land costs $30,000 per acre. A condominium will cost her $1,000 per unit, an acre of land will cost $2,000 for maintenance and upkeep, and $14,000 has been budgeted for these annual expenses. Lauren wants to know how much to invest in condominiums and land to maximize her annual return.
The owner of the Consolidated Machine Shop has $10,000 available to purchase a lathe, a press, a grinder, or some combination thereof. The following 01 integer linear programming model has been developed to determine which of the three machines (lathe, x 1 ; press, x 2 ; or grinder, x 3 ) should be purchased in order to maximize annual profit:
Solve this model by using the computer.
Solve the following mixed integer linear programming model by using the computer:
Northwoods Backpackers is a retail catalog store in Vermont that specializes in outdoor clothing and camping equipment. Phone orders are taken each day by a large pool of computer operators, some of whom are permanent and some temporary. A permanent operator can process an average of 76 orders per day, whereas a temporary operator can process an average of 53 orders per day. The company averages at least 600 orders per day. The store has 10 computer workstations. A permanent operator processes about 1.3 orders with errors each day, whereas a temporary operator averages 4.1 orders with errors daily. The store wants to limit errors to 24 per day. A permanent operator is paid $81 per day, including benefits, and a temporary operator is paid $50 per day. The company wants to know the number of permanent and temporary operators to hire to minimize costs.
Formulate an integer programming model for this problem and solve it by using the computer.
Consider the following linear programming model:
Solve this problem by using the computer.
In the example problem solution for this chapter on page 203, a textbook company was attempting to determine how many sales representatives to assign to each of two new regions . The company has now decided that if any sales representatives are assigned to region 1, a sales office must be established there, at an annual cost of $18,000. This altered problem is an example of a type of integer programming problem known as a "fixed charge" problem.
The Texas Consolidated Electronics Company is contemplating a research and development program encompassing eight research projects. The company is constrained from embarking on all projects by the number of available management scientists (40) and the budget available for R&D projects ($300,000). Further, if project 2 is selected, project 5 must also be selected (but not vice versa). Following are the resource requirements and the estimated profit for each project:
Formulate the integer programming model for this problem and solve it by using the computer.
Mazy's Department Store has decided to stay open for business on a 24-hour basis. The store manager has divided the 24-hour day into six 4-hour periods and has determined the following minimum personnel requirements for each period:
Store personnel must report to work at the beginning of one of these time periods and must work for 8 consecutive hours. The store manager wants to know the minimum number of employees to assign to each 4-hour segment to minimize the total number of employees . Formulate and solve this problem.
The athletic boosters club for Beaconville has planned a 2-day fund-raising drive to purchase uniforms for all the local high schools and to improve facilities. Donations will be solicited during the day and night by telephone and personal contact. The boosters club has arranged for local college students to donate their time to solicit donations. The average donation from each type of contact and the time for a volunteer to solicit each type of donation are as follows :
The boosters club has gotten several businesses and car dealers to donate gasoline and cars for the college students to use to make a maximum of 575 personal contacts daily during the fund-raising drive. The college students will donate a total of 22 hours during the day and 43 hours at night during the drive.
The president of the boosters club wants to know how many different types of donor contacts to schedule during the drive to maximize total donations. Formulate and solve an integer programming model for this problem. What is the difference in the total maximum value of donations between the integer and non-integer rounded-down solutions to this problem?
The Metropolitan Arts Council (MAC) wants to advertise its upcoming season of plays, concerts, and ballets. A television commercial that costs $25,000 will supposedly reach 53,000 potential arts customers. The breakdown of the audience is as follows:
A newspaper ad costs $7,000, and the newspaper claims that its ads will reach an audience of 30,000 potential arts customers, broken down as follows:
A radio ad costs $9,000, and it is estimated to reach an audience of 41,000 arts customers, with the following audience breakdown:
The arts council has established several marketing guidelines. It wants to reach at least 200,000 potential arts customers. It believes older people are more likely to buy tickets than younger people, so it wants to reach at least 1.5 times as many people over 35 as people under 35. The council also believes women are more likely to instigate ticket purchases to the arts than men, so it wants its advertising audience to be at least 60% female.
Juan Hernandez, a Cuban athlete who visits the United States and Europe frequently, is allowed to return with a limited number of consumer items not generally available in Cuba. The items, which are carried in a duffel bag, cannot exceed a weight of 5 pounds. Once Juan is in Cuba, he sells the items at highly inflated prices. The three most popular items in Cuba are denim jeans , CD players, and CDs of U.S. rock groups. The weight and profit (in U.S. dollars) of each item are as follows:
Juan wants to determine the combination of items he should pack in his duffel bag to maximize his profit. This problem is an example of a type of integer programming problem known as a "knapsack" problem. Formulate and solve this problem.
The Avalon Floor Cleaner Company is trying to determine the number of salespeople it should allocate to its three regionsthe East, the Midwest, and the West. The company has 100 salespeople that it wants to assign to the three regions. The annual average unit sales volume achieved by a salesperson in each region is as follows:
Because travel distances, costs of living, and other factors vary among the three regions, the annual cost of having a salesperson is $5,000 in the East, $11,000 in the Midwest, and $7,000 in the West. The company has $700,000 budgeted for expenses. To ensure nationwide exposure for its product, the company has decided that each region must have at least 10 salespeople. The company wants to know how many salespeople to allocate to each region to maximize total average units sold. Formulate an integer programming model for this problem and solve it by using the computer.
During the war with Iraq in 1991, the Terraco Motor Company produced a lightweight, all-terrain vehicle code-named "J99 Terra" for the military. The company is now planning to sell the Terra to the public. It has five plants that manufacture the vehicle and four regional distribution centers. The company is unsure of public demand for the Terra, so it is considering reducing its fixed operating costs by closing one or more plants, even though it would incur an increase in transportation costs. The relevant costs for the problem are provided in the following table. The transportation costs are per thousand vehicles shipped; for example, the cost of shipping 1,000 vehicles from plant 1 to warehouse C is $32,000.
Formulate and solve an integer programming model for this problem to assist the company in determining which plants should remain open and which should be closed and the number of vehicles that should be shipped from each plant to each warehouse to minimize total cost.
The Otter Creek Winery produces three kinds of table winea blush, a white, and a red. The winery has 30,000 pounds of grapes available to produce wine this season. A cask of blush requires 360 pounds of grapes, a cask of white requires 375 pounds, and a cask of red requires 410 pounds. The winery has enough storage space in its aging room to store 67 casks of wine. The winery has 2,200 hours of production capacity, and it requires 14 hours to produce a cask of blush, 10 hours to produce a cask of white, and 18 hours to produce a cask of red. From records of previous years ' sales, the winery knows it will sell at least twice as much blush as red and at least 1.5 times as much white as blush. The profit for a cask of blush is $12,100, the profit for a cask of white is $8,700, and the profit for a cask of red is $10,500. The winery wants to know the number of casks of each table wine to produce. Formulate and solve an integer programming model for this problem.
Brenda Last, an undergraduate business major at State University, is attempting to determine her course schedule for the fall semester. She is considering seven 3-credit-hour courses, which are shown in the following table. Also included are the average number of hours she expects to have to devote to each course each week (based on information from other students) and her minimum expected grade in each course, based on an analysis of the grading records of the teachers in each course:
An A in a course earns 4 quality credits per hour, a B earns 3 quality credits, a C earns 2 quality credits, a D earns 1 quality credit, and an F earns no quality credits per hour. Brenda wants to select a schedule that will provide at least a 2.0 grade point average. In order to remain a full-time student, which she must do to continue receiving financial aid, she must take at least 12 credit hours. Principles of Accounting, Corporate Finance, Quantitative Methods, and C Programming all require a lot of computing and mathematics, and Brenda would like to take no more than two of these courses. To remain on schedule and meet prerequisites, she needs to take at least three of the following courses: Management I, Principles of Accounting, C Programming, and English. Brenda wants to develop a course schedule that will minimize the number of hours she has to work each week.
The artisans at Jewelry Junction in Phoenix are preparing to make gold jewelry during a 2-month period for the Christmas season. They can make bracelets, necklaces, and pins. Each bracelet requires 6.3 ounces of gold and 17 hours of labor, each necklace requires 3.9 ounces of gold and 10 hours of labor, and each pin requires 3.1 ounces of gold and 7 hours of labor. Jewelry Junction has available 125 ounces of gold and 320 hours of labor. A bracelet sells for $1,650, a necklace for $850, and a pin for $790. The store wants to know how many of each item to produce to maximize revenue.
Harry and Melissa Jacobson produce handcrafted furniture in a workshop on their farm. They have obtained a load of 600 board feet of birch from a neighbor and are planning to produce round kitchen tables and ladder-back chairs during the next 3 months. Each table will require 30 hours of labor, each chair will require 18 hours, and between them they have a total of 480 hours of labor available. A table requires 40 board feet of wood to make, and a chair requires 15 board feet. A table earns the couple $575 in profit, and a chair earns $120 in profit. Most people who buy a table also want four chairs to go with it, so for every table that is produced, at least four chairs must also be made, although additional chairs can also be sold separately. Formulate and solve an integer programming model to determine the number of tables and chairs the Jacobsons should make to maximize profit.
The Jacobsons in Problem 24 have been approached by a home furnishings company that needs a wooden stool for its catalog. The company has asked the Jacobsons to produce a batch of 20 wooden stools, and the Jacobsons would realize a profit of $65 for each stool. A stool will require 4 board feet of wood and 5 hours to produce. Formulate and solve an integer programming model to help the Jacobsons determine whether they should produce the stools.
The Skimmer Boat Company manufactures three kinds of molded fiberglass recreational boatsa bass fishing boat, a ski boat, and a speedboat. The profit for a bass boat is $20,500, the profit for a ski boat is $12,000, and the profit for a speedboat is $22,300. The company believes it will sell more bass boats than the other two boats combined but no more than twice as many. The ski boat is its standard production model, and bass boats and speedboats are modifications. The company has production capacity to manufacture 210 standard (ski-type) boats; however, a bass boat requires 1.3 times the standard production capacity, and a speedboat requires 1.5 times the normal production capacity. In addition, only 160 of the high- powered engines that are installed in the bass boats and 2 of those installed in the speedboats are available. The company wants to know how many boats of each type to produce to maximize profit. Formulate and solve an integer programming model for this problem.
The Reliance Manufacturing Company produces an aircraft part. The company can produce the part entirely at a flexible work center with multiple computerized machines. The company has four work centers, all of which are different because they were purchased at different times. Each work center has a single operator; however, the company's operators have different skill levels, resulting in different levels of daily output and product quality. The following tables show the average daily output and average number of defects per day for each of the company's five operators who are capable of producing the aircraft part:
The company wants to determine which operator to assign to each machine to maximize daily output and keep the percentage of defects to less than 4%.
Corsouth Mortgage Associates is a large home mortgage firm in the Southeast. It has a pool of permanent and temporary computer operators who process mortgage accounts, including posting payments and updating escrow accounts for insurance and taxes. A permanent operator can process 220 accounts per day, and a temporary operator can process 140 accounts per day. On average, the firm must process and update at least 6,300 accounts daily. The company has 32 computer workstations available. Permanent and temporary operators work 8 hours per day. A permanent operator averages about 0.4 errors per day, whereas a temporary operator averages 0.9 errors per day. The company wants to limit errors to 15 per day. A permanent operator is paid $120 per day, whereas a temporary operator is paid $75 per day. Corsouth wants to determine the number of permanent and temporary operators it needs to minimize cost. Formulate and solve an integer programming model for this problem and compare this solution to the non-integer solution.
In Problem 28, Corsouth Mortgage Associates is considering hiring some hourly, part-time computer operators in addition to its permanent and temporary operators. A part-time operator can process 12 accounts per hour, averages 0.16 errors per hour, and is paid $4.50 per hour. Corsouth wants to know the number of permanent and temporary employees it should use, plus the number of part-time hours it should arrange for. Formulate and solve a mixed integer model for this problem.
Rowntown Cab Company has 70 drivers that it must schedule in three 8-hour shifts. However, the demand for cabs in the metropolitan area varies dramatically according to the time of day. The slowest period is between midnight and 4:00 A.M. The dispatcher receives few calls, and the calls that are received have the smallest fares of the day. Very few people are going to the airport at that time of night or taking other long-distance trips. It is estimated that a driver will average $80 in fares during that period. The largest fares result from the airport runs in the morning. Thus, the drivers who start their shift during the period from 4:00 A.M. to 8:00 A.M. average $500 in total fares, and drivers who start at 8:00 A.M . average $420. Drivers who start at noon average $300, while drivers who start at 4:00 P.M. average $270. Drivers who start at the beginning of the 8:00 P.M. to midnight period earn an average of $210 in fares during their 8-hour shift.
To retain customers and acquire new ones, Rowntown must maintain a high customer service level. To do so, it has determined the minimum number of drivers it needs working during every 4-hour time segment10 from midnight to 4:00 A.M. , 12 from 4:00 to 8:00 A.M. , 20 from 8:00 A.M. to noon, 25 from noon to 4:00 P.M. , 32 from 4:00 to 8:00 P.M. , and 18 from 8:00 P.M. to midnight.
Globex Investment Capital Corporation owns six companies that have the following estimated returns (in millions of dollars) if sold in 1 of the next 3 years:
To generate operating funds, the company must sell at least $20 million worth of assets in year 1, $25 million in year 2, and $35 million in year 3. Globex wants to develop a plan for selling these companies during the next 3 years to maximize return.
Formulate an integer programming model for this problem and solve it by using the computer.
The Heartland Distribution Company is a food warehouse and distributor that has a contract with a grocery store chain in several Midwest and Southeast cities. The company wants to construct new warehouses/distribution centers in some of the cities it services to serve the stores in those cities plus all the other stores in the other cities that don't have distribution centers. A distribution center can effectively service all stores within a 300-mile radius. The company also wants to limit its fixed annual costs to under $900,000. The company wants to build the minimum number of distribution centers possible.
The following table shows the cities within 300 miles of every city and the projected fixed annual charge for a distribution center in each city:
The Kreeger Grocery Store chain has bought out a competing grocery store chain. However, it now has too many stores in close proximity to each other in certain cities. In Roanoke the chain has 10 stores, and it does not want any stores closer than 2 miles to each other. Following are the monthly revenues ($1,000s) from each store and a map showing the general proximity of the stores. Stores within 2 miles of each other are circled:
Develop and solve an integer programming model to determine which stores the Kreeger chain should keep open in Roanoke.
A youth soccer club has contracted with Holiday Helpers, a local travel agency, to broker hotel rooms for out-of-town teams that have entered the club's Labor Day weekend soccer tournament . The agency has 12 teams it needs to arrange rooms for at 8 possible hotels. The following tables show the number of rooms each team needs, the number of rooms available at each hotel, the room rate at each hotel, and the maximum room rate each team wants to pay:
Determine a revised hotel room allocation to assign rooms to all teams while reflecting their preferences to the greatest possible extent.
The Tech Software School contracts to train employees of companies in the use of various software products and packages. The training programs are all delivered on 3 consecutive days but require different daily durations, depending on the software product. For a specific 7-day week (including weekends), the school has contracted with eight different companies for training sessions for different software products. The companies can send their employees to the Tech training facility only on certain days, as shown in the following table, with the hourly training requirements per day:
The school has 20 staff-hours per day available for these training sessions.
Each day Seacoast Food Services makes deliveries to four restaurants it supplies in the metro Atlanta area. The service uses one truck that starts at its warehouse, makes a delivery to each restaurant, and then returns to the warehouse. The mileage between the warehouse, 1, and each of the restaurants , 2, 3, 4, and 5, is shown in the following table:
Formulate and solve an integer programming model to determine the route (or tour) the truck should take to start at the warehouse, visit each restaurant once, and return to the warehouse with the minimum total distance traveled.
HTM Realty has a storefront rental property in downtown Draperton, a small college town next to the Tech campus. The property encompasses four business spaces that open onto College Avenue. HTM has a long- term tenant in each space, and their leases are all running out at approximately the same time. HTM wants to significantly increase the rent for each space, and the current tenants have all indicated that they will stay on at a slightly increased rent but not at the rental price that HTM wants. HTM has shopped the spaces around and has gotten commitments from four new tenants at the higher rent. However, HTM realizes that there is a very high likelihood that the current tenants will remain in business and pay their rent for a new 3-year lease, while there is a much smaller likelihood that the new tenants will be able to stay in business and fulfill their lease payments. The following table shows the current and prospective new tenant for each space, their monthly payments for a 3-year lease, and the probability that each will remain in business:
HTM wants to lease each space to businesses that will maximize their expected lease payments. It also wants a likelihood of at least 3 of the businesses staying in business. Formulate and solve an integer programming model for this problem.