Assignment - Integer Programming
Part A - Formulating Integer Programming Problems
Q1. Coach Night is trying to choose the starting lineup for the basketball team. The team consists of seven players who have been rated (on a scale of 1 = poor to 3 = excellent) according to their ball-handling, shooting, rebounding, and defensive abilities. The positions that each player is allowed to play and the player's abilities are listed in Table 9.
The five-player starting lineup must satisfy the following restrictions:
1. At least 4 members must be able to play guard, at least 2 members must be able to play forward, and at least 1 member must be able to play center.
2. The average ball-handling, shooting, and rebounding level of the starting lineup must be at least 2.
3. If player 3 starts, then player 6 cannot start.
4. If player 1 starts, then players 4 and 5 must both start.
5. Either player 2 or player 3 must start.
Given these constraints, Coach Night wants to maximize the total defensive ability of the starting team. Formulate an IP that will help him choose his starting team.
Q2. Because of excessive pollution on the Momiss River, the state of Momiss is going to build pollution control stations. Three sites (1, 2, and 3) are under consideration. Momiss is interested in controlling the pollution levels of two pollutants (1 and 2). The state legislature requires that at least 80,000 tons of pollutant 1 and at least 50,000 tons of pollutant 2 be removed from the river. The relevant data for this problem are shown in Table 10. Formulate an IP to minimize the cost of meeting the state legislature's goals.
Q3. A manufacturer can sell product 1 at a profit of $2/unit and product 2 at a profit of $5/unit. Three units of raw material are needed to manufacture 1 unit of product 1, and 6 units of raw material are needed to manufacture 1 unit of product 2. A total of 120 units of raw material are available. If any of product 1 is produced, a setup cost of $10 is incurred, and if any of product 2 is produced, a setup cost of $20 is incurred. Formulate an IP to maximize profits.
Q4. Suppose we add the following restriction to Example 1 (Stockco): If investments 2 and 3 are chosen, then investment 4 must be chosen. What constraints would be added to the formulation given in the text?
Q5. How would the following restrictions modify the formulation of Example 6 (Dorian car sizes)? (Do each part separately.)
a. If midsize cars are produced, then compacts must also be produced.
b. Either compacts or large cars must be manufactured.
Q6. To graduate from Basketweavers University with a major in operations research, a student must complete at least two math courses, at least two OR courses, and at least two computer courses. Some courses can be used to fulfill more than one requirement: Calculus can fulfill the math requirement; operations research, math and OR requirements; data structures, computer and math requirements; business statistics, math and OR requirements; computer simulation, OR and computer requirements; introduction to computer programming, computer requirement; and forecasting, OR and math requirements.
Some courses are prerequisites for others: Calculus is a prerequisite for business statistics; introduction to computer programming is a prerequisite for computer simulation and for data structures; and business statistics is a prerequisite for forecasting. Formulate an IP that minimizes the number of courses needed to satisfy the major requirements.
Q7. In Example 7 (Euing Gas), suppose that x = 300. What would be the values of y1, y2, y3, z1, z2, z3, and z4? How about if x = 1,200?
Q8. Formulate an IP to solve the Dorian Auto problem for the advertising data that exhibit increasing returns as more ads are placed in a magazine.
Q9. How can integer programming be used to ensure that the variable x can assume only the values 1, 2, 3, and 4?
Q10. If x and y are integers, how could you ensure that x + y ≤ 3, 2x + 5y ≤ 12, or both are satisfied by x and y?
Q11. If x and y are both integers, how would you ensure that whenever x ≤ 2, then y ≤ 3?
Q12. A company is considering opening warehouses in four cities: New York, Los Angeles, Chicago, and Atlanta. Each warehouse can ship 100 units per week. The weekly fixed cost of keeping each warehouse open is $400 for New York, $500 for Los Angeles, $300 for Chicago, and $150 for Atlanta.
Region 1 of the country requires 80 units per week, region 2 requires 70 units per week, and region 3 requires 40 units per week. The costs (including production and shipping costs) of sending one unit from a plant to a region are shown in Table 11. We want to meet weekly demands at minimum cost, subject to the preceding information and the following restrictions:
1. If the New York warehouse is opened, then the Los Angeles warehouse must be opened.
2. At most two warehouses can be opened.
3. Either the Atlanta or the Los Angeles warehouse must be opened.
Formulate an IP that can be used to minimize the weekly costs of meeting demand.
Q13. Glueco produces three types of glue on two different production lines. Each line can be utilized by up to seven workers at a time. Workers are paid $500 per week on production line 1, and $900 per week on production line 2. A week of production costs $1,000 to set up production line 1 and $2,000 to set up production line 2. During a week on a production line, each worker produces the number of units of glue shown in Table 12. Each week, at least 120 units of glue 1, at least 150 units of glue 2, and at least 200 units of glue 3 must be produced. Formulate an IP to minimize the total cost of meeting weekly demands.
Q14. The manager of State University's DED computer wants to be able to access five different files. These files are scattered on 10 disks as shown in Table 13. The amount of storage required by each disk is as follows: disk 1, 3K; disk 2, 5K; disk 3, 1K; disk 4, 2K; disk 5, 1K; disk 6, 4K; disk 7, 3K; disk 8, 1K; disk 9, 2K; disk 10, 2K.
a. Formulate an IP that determines a set of disks requiring the minimum amount of storage such that each file is on at least one of the disks. For a given disk, we must either store the entire disk or store none of the disk; we cannot store part of a disk.
b. Modify your formulation so that if disk 3 or disk 5 is used, then disk 2 must also be used.
Q15. Fruit Computer produces two types of computers: Pear computers and Apricot computers. Relevant data are given in Table 14. A total of 3,000 chips and 1,200 hours of labor are available. Formulate an IP to help Fruit maximize profits.
Q16. The Lotus Point Condo Project will contain both homes and apartments. The site can accommodate up to 10,000 dwelling units. The project must contain a recreation project: either a swimming-tennis complex or a sailboat marina, but not both. If a marina is built, then the number of homes in the project must be at least triple the number of apartments in the project. A marina will cost $1.2 million, and a swimming-tennis complex will cost $2.8 million. The developers believe that each apartment will yield revenues with an NPV of $48,000, and each home will yield revenues with an NPV of $46,000. Each home (or apartment) costs $40,000 to build. Formulate an IP to help Lotus Point maximize profits.
Q17. A product can be produced on four different machines. Each machine has a fixed setup cost, variable production costs per-unit-processed, and a production capacity given in Table 15. A total of 2,000 units of the product must be produced. Formulate an IP whose solution will tell us how to minimize total costs.
Q18. Use LINDO, LINGO, or Excel Solver to find the optimal solution to the following IP: Bookco Publishers is considering publishing five textbooks. The maximum number of copies of each textbook that can be sold, the variable cost of producing each textbook, the sales price of each textbook, and the fixed cost of a production run for each book are given in Table 16.
Thus, for example, producing 2,000 copies of book 1 brings in a revenue of 2,000(50) = $100,000 but costs 80,000 + 25(2,000) = $130,000. Bookco can produce at most 10,000 books if it wants to maximize profit.
Q19. Comquat owns four production plants at which personal computers are produced. Comquat can sell up to 20,000 computers per year at a price of $3,500 per computer. For each plant the production capacity, the production cost per computer, and the fixed cost of operating a plant for a year are given in Table 17. Determine how Comquat can maximize its yearly profit from computer production.
Q20. WSP Publishing sells textbooks to college students. WSP has two sales reps available to assign to the A-G state area. The number of college students (in thousands) in each state is given in Figure 9. Each sales rep must be assigned to two adjacent states. For example, a sales rep could be assigned to A and B, but not A and D. WSP's goal is to maximize the number of total students in the states assigned to the sales reps. Formulate an IP whose solution will tell you where to assign the sales reps. Then use LINDO to solve your IP.
Q21. Eastinghouse sells air conditioners. The annual demand for air conditioners in each region of the country is as follows: East, 100,000; South, 150,000; Midwest, 110,000; West, 90,000. Eastinghouse is considering building the air conditioners in four different cities: New York, Atlanta, Chicago, and Los Angeles. The cost of producing an air conditioner in a city and shipping it to a region of the country is given in Table 18. Any factory can produce as many as 150,000 air conditioners per year. The annual fixed cost of operating a factory in each city is given in Table 19.
At least 50,000 units of the Midwest demand for air conditioners must come from New York, or at least 50,000 units of the Midwest demand must come from Atlanta. Formulate an IP whose solution will tell Eastinghouse how to minimize the annual cost of meeting demand for air conditioners.
Q22. Consider the following puzzle. You are to pick out 4 three-letter "words" from the following list:
DBA DEG ADI FFD GHI BCD FDF BAI
For each word, you earn a score equal to the position that the word's third letter appears in the alphabet. For example, DBA earns a score of 1, DEG earns a score of 7, and so on. Your goal is to choose the four words that maximize your total score, subject to the following constraint: The sum of the positions in the alphabet for the first letter of each word chosen must be at least as large as the sum of the positions in the alphabet for the second letter of each word chosen.
Formulate an IP to solve this problem.
Q23. At a machine tool plant, five jobs must be completed each day. The time it takes to do each job depends on the machine used to do the job. If a machine is used at all, there is a setup time required. The relevant times are given in Table 20. The company's goal is to minimize the sum of the setup and machine operation times needed to complete all jobs. Formulate and solve (with LINDO, LINGO, or Excel Solver) an IP whose solution will do this.
Q24. Breadco Bakeries is a new bakery chain that sells bread to customers throughout the state of Indiana. Breadco is considering building bakeries in three locations: Evansville, Indianapolis, and South Bend. Each bakery can bake as many as 900,000 loaves of bread each year. The cost of building a bakery at each site is $5 million in Evansville, $4 million in Indianapolis, and $4.5 million in South Bend. To simplify the problem, we assume that Breadco has only three customers, whose demands each year are 700,000 loaves (customer 1); 400,000 loaves (customer 2); and 300,000 loaves (customer 3). The total cost of baking and shipping a loaf of bread to a customer is given in Table 21. Assume that future shipping and production costs are discounted at a rate of 11(1/9) % per year. Assume that once built, a bakery lasts forever. Formulate an IP to minimize Breadco's total cost of meeting demand (present and future). (Hint: You will need the fact that for x < 1, a + ax + ax2 + ax3 + ... = a/(1 - x).) How would you modify the formulation if either Evansville or South Bend must produce at least 800,000 loaves per year?
Q25. Speaker's Clearinghouse must disburse sweepstakes checks to winners in four different regions of the country: Southeast (SE), Northeast (NE), Far West (FW), and Midwest (MW). The average daily amount of the checks written to winners in each region of the country is as follows: SE, $40,000; NE, $60,000; FW, $30,000; MW, $50,000. Speaker's must issue the checks the day they find out a customer has won. They can delay winners from quickly cashing their checks by giving a winner a check drawn on an out-of-the-way bank (this will cause the check to clear slowly). Four bank sites are under consideration: Frosbite Falls, Montana (FF), Redville, South Carolina (R), Painted Forest, Arizona (PF), and Beanville, Maine (B). The annual cost of maintaining an account at each bank is as follows: FF, $50,000; R, $40,000; PF, $30,000; B, $20,000. Each bank has a requirement that the average daily amount of checks written cannot exceed $90,000. The average number of days it takes a check to clear is given in Table 22. Assuming that money invested by Speaker's earns 15% per year, where should the company have bank accounts, and from which bank should a given customer's check be written?
Q26. Governor Blue of the state of Berry is attempting to get the state legislature to gerrymander Berry's congressional districts. The state consists of 10 cities, and the numbers of registered Republicans and Democrats (in thousands) in each city are shown in Table 23. Berry has five congressional representatives. To form congressional districts, cities must be grouped according to the following restrictions:
1. All voters in a city must be in the same district.
2. Each district must contain between 150,000 and 250,000 voters (there are no independent voters).
Governor Blue is a Democrat. Assume that each voter always votes a straight party ticket. Formulate an IP to help Governor Blue maximize the number of Democrats who will win congressional seats.
Q27. The Father Domino Company sells copying machines. A major factor in making a sale is Domino's quick service.
Domino sells copiers in six cities: Boston, New York, Philadelphia, Washington, Providence, and Atlantic City. The annual sales of copiers projected depend on whether a service representative is within 150 miles of a city (see Table 24).
Each copier costs $500 to produce and sells for $1,000. The annual cost per service representative is $80,000. Domino must determine in which of its markets to base a service representative. Only Boston, New York, Philadelphia, and Washington are under consideration as bases for service representative. The distance (in miles) between the cities is shown in Table 25. Formulate an IP that will help Domino maximize annual profits.
Q28. Thailand inducts naval draftees at three drafting centers. Then the draftees must each be sent to one of three naval bases for training. The cost of transporting a draftee from a drafting center to a base is given in Table 26. Each year, 1,000 men are inducted at center 1; 600 at center 2; and 700 at center 3. Base 1 can train 1,000 men a year, base 2, 800 men; and base 3, 700 men. After the inductees are trained, they are sent to Thailand's main naval base (B).
They may be transported on either a small ship or a large ship. It costs $5,000 plus $2 per mile to use a small ship. A small ship can transport up to 200 men to the main base and may visit up to two bases on its way to the main base. Seven small and five large ships are available. It costs $10,000 plus $3 per mile to use a large ship. A large ship may visit up to three bases on its way to the main base and may transport up to 500 men. The possible "tours" for each type of ship are given in Table 27.
Assume that the assignment of draftees to training bases is done using the transportation method. Then formulate an IP that will minimize the total cost incurred in sending the men from the training bases to the main base. (Hint: Let yij = number of men sent by tour i from base j to main base (B) on a small ship, xij = number of men sent by tour i from base j to B on a large ship, Si = number of times tour i is used by a small ship, and Li = number of times tour i is used by a large ship.)
Q29. You have been assigned to arrange the songs on the cassette version of Madonna's latest album. A cassette tape has two sides (1 and 2). The songs on each side of the cassette must total between 14 and 16 minutes in length. The length and type of each song are given in Table 28. The assignment of songs to the tape must satisfy the following conditions:
1. Each side must have exactly two ballads.
2. Side 1 must have at least three hit songs.
3. Either song 5 or song 6 must be on side 1.
4. If songs 2 and 4 are on side 1, then song 5 must be on side 2.
Explain how you could use an integer programming formulation to determine whether there is an arrangement of songs satisfying these restrictions.
Q30. Cousin Bruzie of radio station WABC schedules radio commercials in 60-second blocks. This hour, the station has sold commercial time for commercials of 15, 16, 20, 25, 30, 35, 40, and 50 seconds. Formulate an integer programming model that can be used to determine the minimum number of 60-second blocks of commercials that must be scheduled to fit in all the current hour's commercials. (Hint: Certainly no more than eight blocks of time are needed. Let yi = 1 if block i is used and yi = 0 otherwise).
Q31. A Sunco oil delivery truck contains five compartments, holding up to 2,700, 2,800, 1,100, 1,800, and 3,400 gallons of fuel, respectively. The company must deliver three types of fuel (super, regular, and unleaded) to a customer. The demands, penalty per gallon short, and the maximum allowed shortage are given in Table 29. Each compartment of the truck can carry only one type of gasoline. Formulate an IP whose solution will tell Sunco how to load the truck in a way that minimizes shortage costs.
Q32. Simon's Mall has 10,000 sq ft of space to rent and wants to determine the types of stores that should occupy the mall. The minimum number and maximum number of each type of store (along with the square footage of each type) is given in Table 30. The annual profit made by each type of store will, of course, depend on how many stores of that type are in the mall. This dependence is given in Table 31 (all profits are in units of $10,000). Thus, if there are two department stores in the mall, each department store earns $210,000 profit per year. Each store pays 5% of its annual profit as rent to Simon's. Formulate an IP whose solution will tell Simon's how to maximize rental income from the mall.
Q33. Boris Milkem's financial firm owns six assets. The expected sales price (in millions of dollars) for each asset is given in Table 32. If asset 1 is sold in year 2, the firm receives $20 million. To maintain a regular cash flow, Milkem must sell at least $20 million of assets during year 1, at least $30 million worth during year 2, and at least $35 million worth during year 3. Set up an IP that Milkem can use to determine how to maximize total revenue from assets sold during the next three years. In implementing this model, how could the idea of a rolling planning horizon be used?
Q34. The Smalltown Fire Department currently has seven conventional ladder companies and seven alarm boxes. The two closest ladder companies to each alarm box are given in Table 33. The city fathers want to maximize the number of conventional ladder companies that can be replaced with tower ladder companies. Unfortunately, political considerations dictate that a conventional company can be replaced only if, after replacement, at least one of the two closest companies to each alarm box is still a conventional company.
a. Formulate an IP that can be used to maximize the number of conventional companies that can be replaced by tower companies.
b. Suppose yk = 1 if conventional company k is replaced. Show that if we let zk = 1 yk, the answer in part (a) is equivalent to a set-covering problem.
Q35. A power plant has three boilers. If a given boiler is operated, it can be used to produce a quantity of steam (in tons) between the minimum and maximum given in Table 34. The cost of producing a ton of steam on each boiler is also given. Steam from the boilers is used to produce power on three turbines. If operated, each turbine can process an amount of steam (in tons) between the minimum and maximum given in Table 35. The cost of processing a ton of steam and the power produced by each turbine is also given. Formulate an IP that can be used to minimize the cost of producing 8,000 kwh of power.
Q36. An Ohio company, Clevcinn, consists of three subsidiaries. Each has the respective average payroll, unemployment reserve fund, and estimated payroll given in Table 36. (All figures are in millions of dollars.) Any employer in the state of Ohio whose reserve/average payroll ratio is less than 1 must pay 20% of its estimated payroll in unemployment insurance premiums or 10% if the ratio is at least 1. Clevcinn can aggregate its subsidiaries and label them as separate employers. For instance, if subsidiaries 2 and 3 are aggregated, they must pay 20% of their combined payroll in unemployment insurance premiums. Formulate an IP that can be used to determine which subsidiaries should be aggregated.
Q37. The Indiana University Business School has two rooms that each seat 50 students, one room that seats 100 students, and one room that seats 150 students. Classes are held five hours a day. The four types of requests for rooms are listed in Table 37. The business school must decide how many requests of each type should be assigned to each type of room. Penalties for each type of assignment are given in Table 38. An X means that a request must be satisfied by a room of adequate size. Formulate an IP whose solution will tell the business school how to assign classes to rooms in a way that minimizes total penalties.
Q38. A company sells seven types of boxes, ranging in volume from 17 to 33 cubic feet. The demand and size of each box are given in Table 39. The variable cost (in dollars) of producing each box is equal to the box's volume. A fixed cost of $1,000 is incurred to produce any of a particular box. If the company desires, demand for a box may be satisfied by a box of larger size. Formulate and solve (with LINDO, LINGO, or Excel Solver) an IP whose solution will minimize the cost of meeting the demand for boxes.
Q39. Huntco produces tomato sauce at five different plants. The capacity (in tons) of each plant is given in Table 40. The tomato sauce is stored at one of three warehouses. The per-ton cost (in hundreds of dollars) of producing tomato sauce at each plant and shipping it to each warehouse is given in Table 41. Huntco has four customers. The cost of shipping a ton of sauce from each warehouse to each customer is as given in Table 42. Each customer must be delivered the amount (in tons) of sauce given in Table 43.
a. Formulate a balanced transportation problem whose solution will tell us how to minimize the cost of meeting the customer demands.
b. Modify this problem if these are annual demands and there is a fixed annual cost of operating each plant and warehouse. These costs (in thousands) are given in Table 44.
Q40. To satisfy telecommunication needs for the next 20 years, Telstar Corporation estimates that the number of circuits required between the United States and Germany, France, Switzerland, and the United Kingdom will be as given in Table 45. Two types of circuits may be created: cable and satellite. Two types of cable circuits (TA7 and TA8) are available. The fixed cost of building each type of cable and the circuit capacity of each type are as given in Table 46.
TA7 and TA8 cable go underseas from the United States to the English Channel. Thus, it costs an additional amount to extend these circuits to other European countries. The annual variable cost per circuit is given in Table 47.
To create and use a satellite circuit, Telstar must launch a satellite, and each country using the satellite must have an earth station(s) to receive the signal. It costs $3 billion to launch a satellite. Each launched satellite can handle up to 140,000 circuits. All earth stations have a maximum capacity of 190 circuits and cost $6,000 per year to operate. Formulate an integer programming model to help determine how to supply the needed circuits and minimize total cost incurred during the next 20 years.
Then use LINDO (or LINGO) to find a near optimal solution. LINDO after 300 pivots did not think it had an optimal solution! By the way, do not require that the number of cable or satellite circuits in a country be integers, or your model will never get solved! For some variables, however, the integer requirement is vital!
Q41. A large drug company must determine how many sales representatives to assign to each of four sales districts. The cost of having n representatives in a district is ($88,000 + $80,000n) per year. If a rep is based in a given district, the time it takes to complete a call on a doctor is given in Table 48 (times are in hours).
Each sales rep can work up to 160 hours per month. Each month the number of calls given in Table 49 must be made in each district. A fractional number of representatives in a district is not permissible. Determine how many representatives should be assigned to each district.
Q42. In this assignment, we will use integer programming and the concept of bond duration to show how Wall Street firms can select an optimal bond portfolio. The duration of a bond (or any stream of payments) is defined as follows: Let C(t) be the payment of the bond at time t (t = 1, 2,..., n).
Let r = market interest rate. If the time-weighted average of the bond's payments is given by:
t=1∑t=n tC(t)/(1+r)t
and the market price P of the bond is given by:
t=1∑t=n C(t)/(1+r)t
then the duration of the bond D is given by:
D = (1/P) t=1∑n tC(t)
Thus, the duration of a bond measures the "average" time (in years) at which a randomly chosen $1 of NPV is received. Suppose an insurance company needs to make payments of $20,000 every six months for the next 10 years. If the market rate of interest is 10% per year, then this stream of payments has an NPV of $251,780 and a duration of 4.47 years. If we want to minimize the sensitivity of our bond portfolio to interest risk and still meet our payment obligations, then it has been shown that we should invest $251,780 at the beginning of year 1 in a bond portfolio having a duration equal to the duration of the payment stream.
Suppose the only cost of owning a bond portfolio is the transaction cost associated with the cost of purchasing the bonds. Let's suppose six bonds are available. The payment streams for these six bonds are given in Table 50. The transaction cost of purchasing any units of bond i equals $500 + $5 per bond purchased. Thus, purchasing one unit of bond 1 costs $505 and purchasing 10 units of bond 1 costs $550. Assume that a fractional number of bond i unit purchases is permissible, but in the interests of diversification at most 100 units of any bond can be purchased. Treasury bonds may also be purchased (with no transaction cost). A treasury bond costs $980 and has a duration of .25 year (90 days).
After computing the price and duration for each bond, use integer programming to determine the immunized bond portfolio that incurs the smallest transaction costs. You may assume the duration of your portfolio is a weighted average of the durations of the bonds included in the portfolio, where the weight associated with each bond is equal to the money invested in that bond.
Q43. Ford has four automobile plants. Each is capable of producing the Taurus, Lincoln, or Escort, but it can only produce one of these cars. The fixed cost of operating each plant for a year and the variable cost of producing a car of each type at each plant are given in Table 51.
Ford faces the following restrictions:
a. Each plant can produce only one type of car.
b. The total production of each type of car must be at a single plant; that is, for example, if any Tauruses are made at plant 1, then all Tauruses must be made there.
c. If plants 3 and 4 are used, then plant 1 must also be used.
Each year, Ford must produce 500,000 of each type of car. Formulate an IP whose solution will tell Ford how to minimize the annual cost of producing cars.
Q44. Venture capital firm JD is trying to determine in which of 10 projects it should invest. It knows how much money is available for investment each of the next N years, the NPV of each project, and the cash required by each project during each of the next N years (see Table 52).
a. Write a LINGO program to determine the projects in which JD should invest.
b. Use your LINGO program to determine which of the 10 projects should be selected. Each project requires cash investment during the next three years. During year 1, $80 million is available for investment. During year 2, $60 million is available for investment. During year 3, $70 million is available for investment. (All figures are in millions of dollars.)
Q45. Write a LINGO program that can solve a fixed-charge problem of the type described in Example 3. Assume there is a limited demand for each product. Then use your program to solve a four-product, three-resource fixed-charge problem with the parameters shown in Tables 53, 54, and 55.
Part B - The Branch-and-Bound Method for Solving
Use branch-and-bound to solve the following IPs:
Q1. max z 5x1 + 2x2
s.t. 3x1 + x2 ≤ 12
x1 + x2 ≤ 5
x1, x2 ≥ 0; x1, x2 integer
Q2. The Dorian Auto example of Section 3.2.
Q3 max z = 2x1 + 3x2
s.t. x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 25
x1, x2 ≥ 0; x1, x2 integer
Q4. max z = 4x1 + 3x2
s.t. 4x1 + 9x2 ≤ 26
8x1 + 5x2 ≤ 17
x1, x2 ≥ 0; x1, x2 integer
Q5. max z = 4x1 + 5x2
s.t. x1 + 4x2 ≥ 5
3x1 + 2x2 ≥ 7
x1, x2 ≥ 0; x1, x2 integer
Q6. max z = 4x1 + 5x2
s.t. 3x1 + 2x2 ≤ 10
x1 + 4x2 ≤ 11
3x1 + 3x2 ≤ 13
x1, x2 ≥ 0; x1, x2 integer
Q7. Use the branch-and-bound method to find the optimal solution to the following IP:
max z = 7x1 + 3x2
s.t. 2x1 + x2 ≤ 9
3x1 + 2x2 ≤ 13
x1, x2 ≥ 0; x1, x2 integer
Q8. Suppose we have branched on a subproblem (call it subproblem 0, having optimal solution SOL0) and have obtained the following two subproblems:
Subproblem 1 Subproblem 0 + Constraint x1 ≤ i.
Subproblem 2 Subproblem 0 + Constraint x1 ≥ i + 1 (i is some integer).
Prove that there will exist at least one optimal solution to subproblem 1 having x1 = i and at least one optimal solution to subproblem 2 having x1 = i + 1. [Hint: Suppose an optimal solution to subproblem 1 (call it SOL1) has x1 = x-1, where x-1 < i. For some number c (0 < c < 1), c(SOL0) + (1 - c)SOL1 will have the following three properties:
a. The value of x1 in c(SOL0) + (1 - c)SOL1 will equal i.
b. c(SOL0) + (1 - c)SOL1 will be feasible in sub-problem 1.
c. The z-value for c(SOL0) + (1 - c)SOL1 will be at least as good as the z-value for SOL1.
Explain how this result can help when we graphically solve branch-and-bound problems.]
Q9. During the next five periods, the demands in Table 58 must be met on time. At the beginning of period 1, the inventory level is 0. Each period that production occurs a setup cost of $250 and a per-unit production cost of $2 are incurred. At the end of each period a per-unit holding cost of $1 is incurred.
|
Table 58
|
|
|
Period
|
|
|
1
|
2
|
3
|
4
|
5
|
|
Demand
|
220
|
280
|
360
|
140
|
270
|
a. Solve for the cost-minimizing production schedule using the following decision variables: xt = units produced during month t and yt = 1 if any units are produced during period t, yt = 0 otherwise.
b. Solve for the cost-minimizing production schedule using the following variables: yt's defined in part (a) and xit = number of units produced during period i to satisfy period t demand.
c. Which formulation took LINDO or LINGO less time to solve?
d. Give an intuitive explanation of why the part (b) formulation is solved faster than the part (a) formulation.
Part C - The Branch-and-Bound Method for Solving Mixed Integer Programming Problems
Use the branch-and-bound method to solve the following IPs:
Q1. max z = 3x1 + x2
s.t. 5x1 + 2x2 ≤ 10
4x1 + x2 ≤ 7
x1, x2 ≥ 0; x2 integer
Q2. min z = 3x1 + x2
s.t. x1 + 5x2 ≥ 8
x1 + 2x2 ≥ 4
x1, x2 ≥ 0; x1 integer
Q3. max z = 4x1 + 3x2 + x3
s.t. 3x1 + 2x2 + x3 ≤ 7
2x1 + x2 + 2x3 ≤ 11
x2, x3 integer, x1, x2, x3 ≥ 0
Part D - Solving Knapsack Problems by the Branch-and-Bound Method
Q1. Show how the following problem can be expressed as a knapsack problem in which all variables must equal 0 or 1. NASA is determining how many of three types of objects should be brought on board the space shuttle. The weight and benefit of each of the items are given in Table 60. If the space shuttle can carry a maximum of 26 lb of items 1-3, which items should be taken on the space shuttle?
Q2. I am moving from New Jersey to Indiana and have rented a truck that can haul up to 1,100 cu ft of furniture. The volume and value of each item I am considering moving on the truck are given in Table 61. Which items should I bring to Indiana? To solve this problem as a knapsack problem, what unrealistic assumptions must we make?
Q3. Four projects are available for investment. The projects require the cash flows and yield the net present values (NPV) (in millions) shown in Table 62. If $6 million is available for investment at time 0, find the investment plan that maximizes NPV.
Part E - Implicit Enumeration
Use implicit enumeration to solve the following 0-1 IPs:
Q1. max z = 3x1 + x2 + 2x3 - x4 + x5
2x1 + x2 - 3x3 ≤ 1
x1 + 2x2 - 3x3 - x4 + 2x5 ≥ 2
xi = 0 or 1
Q2. max z = 2x1 - x2 + x3
x1 + 2x2 - x3 ≤ 1
x1 + x2 + x3 ≤ 2
xi = 0 or 1
Q3. Finco is considering investing in five projects. Each requires a cash outflow at time 0 and yields an NPV as described in Table 82 (all dollars in millions). At time 0, $10 million is available for investment. Projects 1 and 2 are mutually exclusive (that is, Finco cannot undertake both). Similarly, projects 3 and 4 are mutually exclusive. Also, project 2 cannot be undertaken unless project 5 is undertaken. Use implicit enumeration to determine which projects should be undertaken to maximize NPV.
|
Table 82
|
|
Project
|
Time 0 Cash Outflows ($)
|
NPV ($)
|
|
1
|
4
|
5
|
|
2
|
6
|
9
|
|
3
|
5
|
6
|
|
4
|
4
|
3
|
|
5
|
3
|
2
|
Q4. Use implicit enumeration to find the optimal solution to Example 5 (the set-covering problem).
Q5. Use implicit enumeration to solve Problem 1 of Section 9.2.
Q6. Why are the values of u0, u1, . . . , un in (44) unique?
Textbook - Operations Research APPLICATIONS AND ALGORITHMS, FOURTH EDITION by Wayne L. Winston WITH CASES BY Jeffrey B. Goldberg.
Chapter 9 - Integer Programming
Attachment:- Assignment Files.rar