Integer Programming Problems  

Problem 1

The following questions refer to a capital budgeting problem with six projects represented by 0 - 1 variables x1, x2, x3, x4, x5, and x6.

a. Write a constraint modeling a situation in which two of the projects 1, 3, 5, and 6 must be undertaken.

b. Write a constraint modeling a situation in which projects 3 and 5 must be undertaken simultaneously.

c. Write a constraint modeling a situation in which projects 1 or 4 must be undertaken, but not both.

d. Write constraints modeling a situation where project 4 cannot be undertaken unless projects 1 and 3 also are undertaken.

e. Revise the requirement in part (d) to accommodate the case in which, when projects 1 and 3 are undertaken, project 4 must also be undertaken.

Problem 2

Spencer Enterprises is attempting to choose among a series of new investment alternatives. The potential investment alternatives, the net present value of the future stream of returns, the capital requirements, and the available capital funds over the next 3 years are summarized as follows:

Alternative Net present
Value ($)
Capital Requirements ($)
    Year 1 Year 2 Year 3
Limited warehouse expansion 4,000 3,000 1,000 4,000
Extensive warehouse expansion 6,000 2,500 3,500 3,500
Test market new product 10,500 6,000 4,000 5,000
Advertising campaign 4,000 2,000 1,500 1,800
Basic research 8,000 5,000 1,000 4,000
Purchase new equipment 3,000 1,000 500 900
Capital funds available   10,500 7,000 8,750

a. Develop and solve an integer programming model for maximizing the net present value.

b. Assume that only one of the warehouse expansion projects can be implemented. Modify your model of part (a).

c. Suppose that, if the test marketing of the new product is carried out, the advertising campaign must also be conducted. Modify your formulation of part (b) to reflect this new situation.

Problem 3.

Hart Manufacturing makes three products. Each product requires manufacturing operations in three departments: A, B, and C. The labor-hour requirements, by department, are

Department Product 1 Product 2 Product 3
A 1.50 3.00 2.00
B 2.00 1.00 2.50
C 0.25 0.25 0.25

During the next production period, the labor-hours available are 450 in department A, 350 in department B, and 50 in department C. The profit contributions per unit are $25 for product 1, $28 for product 2, and $30 for product 3.

a. Formulate a linear programming model for maximizing total profit contribution.

b. Solve the linear program formulated in part (a). How much of each product should be produced and what is the projected profit contribution?

c. After evaluating the solution obtained in part (b), one of the production supervisors noted that production setup costs had not been taken into account. She noted that setup costs are $400 for product 1, $550 for product 2, and $600 for product 3. If the solution developed in part (b) is to be used, what is the total profit contribution after taking into account the setup costs?

d. Management realized that the optimal product mix, taking setup costs into account, might be different from the one recommended in part (b). Formulate a mixed-integer linear program that takes setup costs into account.

e. Use a computer code to solve the mixed-integer linear program formulated in part (d). How much of each product should be produced and what is the projected total profit contribution? Compare this profit contribution to that obtained in part (c).

Problem 4.

The Northshore Bank is working to develop an efficient work schedule for full-time and part-time tellers. The schedule must provide for efficient operation of the bank including adequate customer service, employee breaks, and so on. On Fridays the bank is open from 9:00 a.m. to 7:00 p.m. The number of tellers necessary to provide adequate service during each hour of operation is summarized below.

Time 9-10 10-11 11-12 12-1 1-2 2-3 3-4 4-5 5-6 6-7
Number of Tellers 6 4 8 10 9 6 4 7 6 6

Each full-time employee starts on the hour and works a four-hour shift, followed by one hour for lunch and then a three-hour shift. Part-time employees work one four-hour shift beginning on the hour. Considering salary and fringe benefits, full-time employees cost the bank $15 per hour ($105 per day), and part-time employees cost the bank $8 per hour ($32 per day).

a. Formulate an integer programming model that can be used to develop a schedule that will satisfy customer service needs at a minimum employee cost. (Hint: Let xi = number of full-time employees coming on duty at the beginning of hour i and yi = number of part-time employees coming on duty at the beginning of hour i.)

b. Solve the LP Relaxation of your model in part (a).

c. Solve the optimal schedule of tellers. Comment on the solution.

d. After reviewing the solution to part (c), the bank manager has realized that some additional requirements must be specified. Specifically, she wants to ensure that one full-time employee is on duty at all times and that there is a staff of at least five full-time employees. Revise your model to incorporate these additional requirements and solve for the optimal solution.